A&DS S01E13. DP on subsets, DP on profiles
HTML-код
- Опубликовано: 2 окт 2024
- Algorithms and data structures. Semester 1. Lecture 13.
In the thirteenth lecture, we finish talking about dynamic programming. Discussed the method of dynamic programming on subsets and on profiles.
ITMO University, 2020
In this lecture:
1. Solving Travelling Salesman problem by bitDP
2. DP on profiles (full profile vs broken profile approaches)
Thanks for the great lectures! I have just 2 improvement requests:
1. Could you upload home task discussion sessions as well? I can’t catch them live so it would be nice to view them on-demand.
2. Could you link your Twitch channel in the description to improve visibility for new viewers?
we considered the case when we have two consecutive 0's in both profile p and q (at same positions) then we are placing a vertical rectangle. but similar to that when we will have 2 consecutive 1's in both profile pand q (at same positions) then also we can plave vertical tile am i right
?
بحبك
anyone has problems link?
At 1:08:45 you wrote q[j+1]=1 but the tile is not sticking out , why?
You are awesome!
simply awesome
@pavel in the profiles question. when two 0-1 are there we only considered horizontal placement of tiles. what about the two vertical tiles? how to add those?
For two vertical tiles the profiles will be 0-0
@@pavelmavrin But don't we have to do additional calculation for that?
Hi Pavel,
About the "DP on broken profiles" O(m*n*2ⁿ) algo...
I guess it can be done even more simply.
at any of the n bit positions, we have only these transitions feasible from profile p to profile q :
(1) 00 -> 00 (put vertical tile)
(2) 0 -> 1 (this automatically covers 00 -> 11) (put horizontal tile)
(3) 1 -> 0 (put no tile)
These transitions aren't feasible :
(1) 1 -> 1 (since column i+1 already got a tile at current bit position)
(2) 0 -> 0 (because we need 0 bit pair to place a vertical tile. 0 bit doesn't help to put any tile shape)
So, we can do the following :
(1) If profile p has no 0 bit pairs, q = ~p
(2) if profile p has atleast 1 0 bit pair, check all n bits in profile p for the 3 rules above, and accordingly set the bits in q
And finally do :
d[i+1, q] += q[i, p]
In practical situation (real time) the algo actually runs faster than O(m*n*2ⁿ) coz we check all n bits in profile p only in very few situations -- whenever it has atleast 1 0 bit pair
How to check if p has 0 bit pair?
(U already spoke about this in a previous algo of this lecture)
(~p & (~p >> 1)) ≠ 0
Please comment/correct?
- Madhukiran
man I learned much more about bit manipulation than dp today