CSC373 Week 3: Dynamic Programming 373F21 – Nisarg Shah 1 Nisarg Shah Recap 373F21 – Nisarg Shah 2 Greedy Algorithms Interval scheduling Interval partitioning Minimizing lateness Huffman encoding … 373F21 – Nisarg Shah 3 Jeff Erickson on greedy algorithms… 373F21 – Nisarg Shah 4 The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was secretary of Defense, and he actually had a pathological fear and hatred of the word ‘research’. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term ‘research’ in his presence. You can imagine how he felt, then, about the term ‘mathematical’. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose — Richard Bellman, on the origin of his term ‘dynamic programming’ (1984) Richard Bellman’s quote from Jeff Erickson’s book Dynamic Programming 373F21 – Nisarg Shah 5 Outline Breaking the problem down into simpler subproblems, solve each subproblem just once, and store their solutions. The next time the same subproblem occurs, instead of recomputing its solution, simply look up its previously computed solution. Hopefully, we save a lot of computation at the expense of modest increase in storage space. Also called “memoization” How is this different from divide & conquer Problem Job starts at time and finishes at time Each job has a weight Two jobs are compatible if they don’t overlap Goal: find a set of mutually compatible jobs with highest total weight σ∈ Recall: If all = 1, then this is simply the interval scheduling problem from last week Greedy algorithm based on earliest finish time ordering was optimal for this case Weighted Interval Scheduling 373F21 – Nisarg Shah 6 Recall: Interval Scheduling 373F21 – Nisarg Shah 7 What if we simply try to use it again Fails spectacularly! Weighted Interval Scheduling 373F21 – Nisarg Shah 8 What if we use other orderings By weight: choose jobs with highest first Maximum weight per time: choose jobs with highest /( ) first … None of them work! They’re arbitrarily worse than the optimal solution In fact, under a certain formalization, “no greedy algorithm” can produce any “decent approximation” in the worst case (beyond this course!) Weighted Interval Scheduling 373F21 – Nisarg Shah 9 Convention Jobs are sorted by finish time: 1 ≤ 2 ≤ ≤ = largest < such that job is compatible with job (i.e., < ) o Jobs 1, … , are compatible with , but jobs + 1, … , 1 aren’t o [] can be computed via binary search E.g., [8] = 1, [7] = 3, [2] = 0, … Weighted Interval Scheduling 373F21 - Nisarg Shah 10 The DP approach Let OPT be an optimal solution Two options regarding job : o Option 1: Job is in OPT Can’t use incompatible jobs + 1, … , 1 Must select optimal subset of jobs from {1, … , } o Option 2: Job is not in OPT Must select optimal subset of jobs from {1, … , 1} OPT is best of both options Notice that in both options, we need to solve the problem on a prefix of our ordering Weighted Interval Scheduling 373F21 - Nisarg Shah 11 The DP approach () = max total weight of compatible jobs from 1, … , Base case: 0 = 0 Two cases regarding job : o Job is selected: optimal weight is + ( ) o Job is not selected: optimal weight is ( 1) Bellman equation: = 0 if = 0 max 1 , + if > 0 Brute Force Solution 373F21 – Nisarg Shah 12 Brute Force Solution 373F21 – Nisarg Shah 13 Q: Worst-case running time of COMPUTE-OPT() a) Θ() b) Θ log c) Θ 1.618 d) Θ(2) Dynamic Programming 373F21 – Nisarg Shah 15 Why is the runtime high Some solutions are being computed many, many times o E.g., if [5] = 3, then Compute-OPT(5) calls Compute-OPT(4) and Compute-OPT(3) o But Compute-OPT(4) in turn calls Compute-OPT(3) again Memoization trick Simply remember what you’ve already computed, and re-use the answer if needed in future Dynamic Program: Top-Down 373F21 – Nisarg Shah 16 Let’s store COMPUTE-OPT(j) in [] Dynamic Program: Top-Down 373F21 – Nisarg Shah 17 Claim: This memoized version takes log time Sorting by finish time: log Computing []-s: ( log ) For each , at most one of the calls to M-Compute-OPT() will make two recursive calls to M-Compute-OPT o At most () total calls to M-Compute-OPT o Each call takes (1) time, not considering the time spent in the recursive calls o Hence, the initial call, M-Compute-OPT(), finishes in time Overall time is log Dynamic Program: Bottom-Up 373F21 – Nisarg Shah 18 Find an order in which to call the functions so that the sub- solutions are ready when needed Top-Down vs Bottom-Up 373F21 – Nisarg Shah 19 Top-Down may be preferred… …when not all sub-solutions need to be computed on some inputs …because one does not need to think of the “right order” in which to compute sub-solutions Bottom-Up may be preferred… …when all sub-solutions will anyway need to be computed …because it is faster as it prevents recursive call overheads and unnecessary random memory accesses …because sometimes we can free-up memory early Optimal Solution 373F21 – Nisarg Shah 20 This approach gave us the optimal value What about the actual solution (subset of jobs) Idea: Maintain the optimal value and an optimal solution So, we compute two quantities: = 0 if = 0 max 1 , + if > 0 = if = 0 ( 1) if > 0 ∧ 1 ≥ + ∪ ( ) if > 0 ∧ 1 < + Optimal Solution 373F21 - Nisarg Shah 21 = 0 if = 0 max 1 , + if > 0 = if = 0 ( 1) if > 0 ∧ 1 ≥ + ∪ ( ) if > 0 ∧ 1 < + This works with both top-down and bottom-up implementations. We can compute and simultaneously, or compute first and then compute . Optimal Solution 373F21 - Nisarg Shah 22 = 0 if = 0 max 1 , + if > 0 = ⊥ if = 0 if > 0 ∧ 1 ≥ + if > 0 ∧ 1 < + Save space by storing only one bit of information for each : which option yielded the maximum weight To reconstruct the optimal solution, start with = If = , update ← 1 If = , add to the solution and update ← [] If =⊥, stop Optimal Substructure Property 373F21 - Nisarg Shah 23 Dynamic programming applies well to problems that have optimal substructure property Optimal solution to a problem can be computed easily given optimal solution to subproblems Recall: divide-and-conquer also uses this property Divide-and-conquer is a special case in which the subproblems don’t “overlap” So, there’s no need for memoization In dynamic programming, two of the subproblems may in turn require access to solution to the same subproblem Knapsack Problem 373F21 - Nisarg Shah 24 Problem items: item provides value > 0 and has weight > 0 Knapsack has weight capacity Assumption: , -s, and -s are all integers Goal: pack the knapsack with a subset of items with highest total value subject to their total weight being at most A First Attempt 373F21 – Nisarg Shah 25 Let () = maximum value we can pack with a knapsack of capacity Goal: Compute () Claim: () must use at least one job with weight ≤ and then optimally pack the remaining capacity of Let = min = 0 if < max :≤ + if ≥ This is wrong! It might use an item more than once! A Refined Attempt 373F21 - Nisarg Shah 26 (, ) = maximum value we can pack using only items 1, … , in a knapsack of capacity Goal: Compute (, ) Consider item If > , then we can’t choose . Use ( 1, ) If ≤ , there are two cases: o If we choose , the best is + 1, o If we don’t choose , the best is ( 1, ) Running Time 373F21 – Nisarg Shah 27 Consider possible evaluations (, ) ∈ 1, … , ∈ {1, … , } (recall weights and capacity are integers) There are ( ) possible evaluations of Each is evaluated at most once (memoization / bottom-up) Each takes (1) time to evaluate The total running time is ( ) Q: Is this polynomial in the input size A: No! But it’s pseudo-polynomial. Recall the inputs: , 1, … , , 1, … , Time should be polynomial in log + σ=1 log + log What if… 373F21 – Nisarg Shah 28 If we were told that = … That is, the value of , and not its number of bits, is polynomially bounded in the input length Then, this algorithm would run in polynomial time Q: What if, instead of the weights being small integers, we are told that the values are small integers Then we can use a different dynamic programming approach! A Different DP 373F21 – Nisarg Shah 29 (, ) = minimum capacity needed to pack a total value of at least using items 1, … , Goal: Compute max ∶ , ≤ Consider item If we choose , we need capacity + ( 1, ) If we don’t choose , we need capacity 1, , = 0 if ≤ 0 ∞ if > 0, = 0 min + 1, , 1, if > 0, > 0 A Different DP 373F21 – Nisarg Shah 30 (, ) = minimum capacity needed to pack a total value of at least using items 1, … , Goal: Compute max ∶ , ≤ This approach has running time ( ), where = 1 + + So, we can get ( ) or ( ), whichever is small
er Can we remove the dependence on both and Not likely. Knapsack problem is NP-complete (we’ll see later). FPTAS 373F21 – Nisarg Shah 31 While we cannot hope to solve the problem exactly in time , log , log … For any > 0, we can get a value that is within 1 + multiplicative factor of the optimal value in time , log , log , 1 Such algorithms are known as fully polynomial-time approximation scheme (FPTAS) Core idea behind FPTAS for knapsack: o Approximate all weights and values up to the desired precision o Solve knapsack on approximate input using DP NOT IN SYLLABUS Single-Source Shortest Paths 373F21 – Nisarg Shah 32 Problem Input: A directed graph = (, ) with edge lengths on each edge (, ), and a source vertex Goal: Compute length of the shortest path from to every vertex When ≥ 0 for each (, )… Dijkstra’s algorithm can be used for this purpose But it fails when some edge lengths can be negative What do we do in this case Single-Source Shortest Paths 373F21 – Nisarg Shah 33 Cycle length = sum of lengths of edges in the cycle If there is a negative length cycle, shortest paths are not even well defined… You can traverse the cycle arbitrarily many times to get arbitrarily “short” paths Single-Source Shortest Paths 373F21 – Nisarg Shah 34 But if there are no negative cycles… Shortest paths are well-defined even when some of the edge lengths may be negative Claim: With no negative cycles, there is always a shortest path from any vertex to any other vertex that is simple Consider the shortest path with the fewest edges among all shortest paths If it has a cycle, removing the cycle creates a path with fewer edges that is no longer than the original path Optimal Substructure Property 373F21 – Nisarg Shah 35 Consider a simple shortest path It could be just a single edge But if has more than one edges, consider which immediately precedes in the path If is shortest, must be shortest as well and it must use one fewer edge than the path Optimal Substructure Property 373F21 – Nisarg Shah 36 (, ) = shortest path from to using at most edges Then: Either this path uses at most 1 edges (, 1) Or it uses edges min , 1 + Optimal Substructure Property 373F21 – Nisarg Shah 37 (, ) = shortest path from to using at most edges Then: Either this path uses at most 1 edges (, 1) Or it uses exactly edges min , 1 + , = 0 ∞ = 0 ∨ = = 0 ∧ ≠ min , 1 , min , 1 + otherwise Running time: (2) calls, each takes () time 3 Q: What do you need to store to also get the actual paths Side Notes 373F21 – Nisarg Shah 38 Bellman-Ford-Moore algorithm Improvement over this DP Running time () for vertices and edges Space complexity reduces to ( + ) Maximum Length Paths 373F21 – Nisarg Shah 39 Can we use a similar DP to compute maximum length paths from to all other vertices This is well defined when there are no positive cycles, in which case, yes. What if there are positive cycles, but we want maximum length simple paths Maximum Length Paths 373F21 – Nisarg Shah 40 What goes wrong Our DP doesn’t work because its path from to might use a path from to and edge from to But path from to might in turn go through The path may no longer remain simple In fact, maximum length simple path is NP-hard Hamiltonian path problem (i.e., “is there a path of length 1 in a given undirected graph ”) is a special case All-Pairs Shortest Paths 373F21 – Nisarg Shah 41 Problem Input: A directed graph = (, ) with edge lengths on each edge (, ) and no negative cycles Goal: Compute the length of the shortest path from all vertices to all other vertices Simple idea: Run single-source shortest paths from each source Running time is 4 Actually, we can do this in (3) as well All-Pairs Shortest Paths 373F21 – Nisarg Shah 42 Problem Input: A directed graph = (, ) with edge lengths on each edge (, ) and no negative cycles Goal: Compute the length of the shortest path from all vertices to all other vertices , , = length of shortest simple path from to in which intermediate nodes are from {1, … , } Exercise: Write down the Bellman equation for such that given all subsolutions, it requires (1) time to compute Running time: 3 calls, 1 per call 3 Chain Matrix Product 373F21 – Nisarg Shah 43 Problem Input: Matrices 1, … , where the dimension of is 1 × Goal: Compute 1 2 … But matrix multiplication is associative = So, isn’t the optimal solution going to call the algorithm for multiplying two matrices exactly 1 times Insight: the time it takes to multiply two matrices depends on their dimensions Chain Matrix Product 373F21 – Nisarg Shah 44 Assume We use the brute force approach for matrix multiplication So, multiplying × and × matrices requires operations Example: compute 1 2 3 1 is 5 X 10 2 is 10 X 100 3 is 100 X 50 1 2 3 → 5 10 100 + 5 100 50 = 30000 ops 1 2 3 → 10 100 50 + 5 10 50 = 52500 ops Chain Matrix Product 373F21 – Nisarg Shah 45 Note Our input is simply the dimensions 0, 1, … , (such that each is 1 × ) and not the actual matrices Why is DP right for this problem Optimal substructure property Think of the final product computed, say is the product of some prefix, is the product of the remaining suffix For the overall optimal computation, each of and should be computed optimally Chain Matrix Product 373F21 – Nisarg Shah 46 (, ) = min ops required to compute … Here, 1 ≤ ≤ ≤ Q: Why do we not just care about prefixes and suffices o 1 2 3 4 5 need to know optimal solution for 2 3 4 Running time: 2 calls, () time per call 3 , = 0 = min k:i≤k, + + 1, + 1 if < Chain Matrix Product 373F21 - Nisarg Shah 47 Can we do better Surprisingly, yes. But not by a DP algorithm (that I know of) Hu & Shing (1981) developed ( log ) time algorithm by reducing chain matrix product to the problem of “optimally” triangulating a regular polygon Source: Wikipedia Example is 10 × 30, is 30 × 5, is 5 × 60 The cost of each triangle is the product of its vertices Want to minimize total cost of all triangles NOT IN SYLLABUS Edit distance (aka sequence alignment) problem How similar are strings = 1, … , and = 1, … , Suppose we can delete or replace symbols We can do these operations on any symbol in either string How many deletions & replacements does it take to match the two strings Edit Distance 373F21 - Nisarg Shah 48 Example: ocurrance vs occurrence Edit Distance 373F21 - Nisarg Shah 49 6 replacements, 1 deletion 1 replacement, 1 deletion Edit distance problem Input o Strings = 1, … , and = 1, … , o Cost () of deleting symbol o Cost (, ) of replacing symbol with Assume , = (, ) and , = 0, for all , Goal o Compute the minimum total cost for matching the two strings Optimal substructure Want to delete/replace at one end and recurse Edit Distance 373F21 - Nisarg Shah 50 Optimal substructure Goal: match 1, … , and 1, … , Consider the last symbols and Three options: o Delete , and optimally match 1, … , 1 and 1, … , o Delete , and optimally match 1, … , and 1, … , 1 o Match and , and optimally match 1, … , 1 and 1, … , 1 We incur cost (, ) Recall: , = 0, so no cost if and already match Hence in the DP, we need to compute the optimal solutions for matching 1, … , with 1, … , for all (, ) Edit Distance 373F21 - Nisarg Shah 51 [, ] = edit distance between 1, … , and 1, … , Bellman equation , = 0 if = = 0 if = 0 ∧ > 0 if > 0 ∧ = 0 min{, , } otherwise where = + 1, , = + , 1 = , + [ 1, 1] ( ) time, ( ) space Edit Distance 373F21 – Nisarg Shah 52 Edit Distance 373F21 – Nisarg Shah 53 , = 0 if = = 0 + [, 1] if = 0 ∧ > 0 + [ 1, ] if > 0 ∧ = 0 min{, , } otherwise where = + 1, , = + , 1 = , + [ 1, 1] Space complexity can be reduced in bottom-up approach While computing [ , ], we only need to store [ , ] and , 1 , So, the additional space required is () By storing two rows at a time instead, we can make it Usually, we include the storage of inputs, so both are ( + ) But this is not enough if we want to compute the actual solution Hirschberg’s Algorithm 373F21 – Nisarg Shah 54 The optimal solution can be computed in time and ( + ) space too! NOT IN SYLLABUS Hirschberg’s Algorithm 373F21 – Nisarg Shah 55 Key idea nicely combines divide & conquer with DP Edit distance graph () () NOT IN SYLLABUS Hirschberg’s Algorithm 373F21 – Nisarg Shah 56 Observation (can be proved by induction) [, ] = length of shortest path from (0,0) to (, ) () () NOT IN SYLLABUS Hirschberg’s Algorithm 373F21 – Nisarg Shah 57 Lemma Shortest path from (0,0) to (, ) passes through (, Τ 2) where minimizes length of shortest path from (0,0) to (, Τ 2) + length of shortest path from (, Τ 2) to (, ) NOT IN SYLLABUS Hirschberg’s Algorithm 373F21 – Nisarg Shah 58 Idea Find using divide-and-conquer Find shortest paths from (0,0) to (, Τ 2) and (, Τ 2) to (, ) using DP NOT IN SYLLABUS 373F21 – Nisarg Shah 59 Application: Protein Matching