Contents 1 Longest Common Subsequence 1 1 1 Problem Definition 1 1 2 Top Down Dynamic Programming 1 1 3 Bottom Up Dynamic Programming 2 2 Bottom Up Dynamic Programming 2 2 1 Ordering Subproblems 2 2 2 Knapsack Problem 2 2 3 Bottom Up Dynamic Programming to the Oh FAIL 3 3 Example Problems 4 3 1 Making Change 4 3 2 Box Stacking 4 1 Longest Common Subsequence 1 1 Problem Definition Given a sequence s hs1 s2 sn i a subsequence is any sequence hsi1 si2 sim i with ij strictly increasing Applications document compare DNA analysis NOTE This is to find one longest subsequence not all So mostly we focus on finding the size 1 2 Top Down Dynamic Programming Optimal substructure Assume x hx1 xm i and y hy1 yn i Let z hz zk i be an LCS of x and y Then If xm yn then we must have zk xm yn and hz1 zk 1 i is an LCS of hx1 xm 1 i and hy1 yn 1 i If xm 6 yn then z uses at most one of them Specifically If zk 6 xm then z is an LCS of hx1 xm 1 i and y If zk 6 yn then z is an LCS of x and hy1 yn 1 i 1 Now we can define a recursion relation that tells us the length of the LCS Let c i j be the length of the LCS of hx1 xi i and hy1 yj i We want c n m if i 0 or j 0 0 c i 1 j 1 1 if i j 0 and xi yj c i j 1 max c i 1 j c i j 1 if i j 0 and xi 6 yj So now we can do it recurisively We ll analyze the running time when we talk about it bottom up 1 3 Bottom Up Dynamic Programming Recursion is easy to write but hard to think about bottom up is much more natural to think about So let s think about it another way If the problem is really small we can do it quickly What does really small mean If both sequences are size 1 But if we know the answer where both subsequences are size 1 then we can in constant time figure out most of the cases where both subsequences are size 2 Specifically we draw a diagram that looks like the one from lecture Go look at it It is an nXm box and we can see that at box r c if we know all squares rs cs with rs r or cs c then we can fill in r c in constant time Running Time Now this is easy We have to fill up the matrix Filling in each square given all squares below is constant time There are O nm squares This was exactly how we analyzed the recursive running time this diagram is just our memo but it s much easier to see 2 2 1 Bottom Up Dynamic Programming Ordering Subproblems We want to order subproblems such that we never have to backtrack and solve a smaller problem in order to solve a larger problem This sounds like Topological Sort If problem u depends on v draw a directed edge from v to u If this graph isn t acyclic then we can t use DP If it is we topologically sort it Note that we can t sort longest simple path for example because the subproblems are inter dependent 2 2 Knapsack Problem Given a set O of objects each object has size and value Want to maximize the value in a knapsack of finite size NP Hard in general Solvable by DP when sizes and values are upper bounded integers sort of Stupid Algorithm O 2 O Greedy Algorithms Greedy on values or greedy on value size Doesn t give the optimal solution Pretty clear if just greedy on values For greedy on value size consider the following instance 2 Knapsack size 50 Item 1 size 10 value 60 Item 2 size 20 value 100 Item 3 size 30 value 120 Item 1 has the highest value size but the correct solution is actually items 2 and 3 Recurrence So given the best value we can obtain for items ik 1 in what is the best value for items ik in That doesn t quite work Think about the dependency graph The best value for ik 1 in that can be used with ik depends on the size of ik but ik depends on ik 1 in So that s not going to work To decouple the problems we need another dimension Namely the space So we use V k X the maximum value for items ik in given X space We want V 0 S where S is the size of the knapsack So in order for this to work X must have a finite number of values Then if i 0orX 0orX S 0 V k 1 X if Size ik X V k X 2 max V k 1 X Value ik V k 1 X Size ik Running Time Size of memo is nS Filling in each square takes constant time so O nS Sadly this isn t polynomial in the size of the input S takes only O log S bits to specify 2 3 Bottom Up Dynamic Programming to the Oh FAIL For any problem we can always create a memo where we can fill in each square in polynomial time The problem is that the size of the memo may not be polynomial Longest Simple Paths Again Consider the function d s t W that stores the longest path from s to t using only vertices in W We can use DP I think to calculate this but there are an exponential number of them 3 3 1 Example Problems Making Change Problem You are given n types of coins with values v1 vn and a cost C You may assume v1 1 so that it is always possible to make any cost What is the smallest number of coins required to sum to C exactly For example assume you coins of values 1 5 and 10 Then the smallest number of coins to make 26 is 4 2 coins of value 10 1 coin of value 5 and 1 coin of value 1 Give a recurrence relation show how you solve this recurrence bottom up and analyze the runtime Note the runtime should be polynomial in the value of C but may not be polynomial in log C Solution cost j Recursion We recurse on M j the minimum number of coins required to make change for M j 0 minvi n M j vi 1 3 if j 0 else 3 Running Time M has C elements and computing each element takes O n time so the total running time is O nC 3 2 Box Stacking Problem You are given a set of boxes b1 bn Each box bj has an associated width wj height hj and depth …
View Full Document
Unlocking...