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 smaller • 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 <