Chapter 13
Dynamic Programming
1 Potholes
Sunaya just moved to Doha, the land of eternal construction. He wants to know how many ways he can
get to CMUQ from his house, and fortunately the roads in Doha form a nice grid1 without any weird
diagonal roads whatsoever. However, some intersections have potholes so he cannot drive through
them.
Given a n × m grid A where A[i][j] = 0 if there is a pothole on the coordinate (i, j) and A[i][j] = 1
otherwise. Sunaya wants to figure out how many ways he can go from coordinate (1, 1) to coordinate
(n, m), such that he only moves down (increase y coordinate) or right (increase x coordinate).
Task (Recursive solution). Write a recursive PH(n,m) to the potholes problem, assuming there is a func-
tion hole : N × N → B which has O(1) work and span and returns true only if the specified coordinates
have a pothole.
.
Solution.
1 PH (n, m) =
2 if n <= 0 or m <= 0 then 0 else
3 if hole(n, m) then 0 else
4 if n = 1 and m = 1 then 1 else
5 PH (n − 1, m) + PH (n, m − 1)
Task (Counting subproblems). Determine how many unique subproblems are there for PH(n, m).
.
Solution. There are n × m unique subproblems.
Task (Top-down solution). Write the (pseudo)-code for a top-down solution for the potholes problems
using the memoization library from DPLab.
.
Solution.
1 PH ′ f (n, m) =
2 if n <= 0 or m <= 0 then 0 else
3 if hole(n, m) then 0 else
4 if n = 1 and m = 1 then 1 else
5 m(n − 1, m) + m(n, m − 1)
6
7 valPH = [Link] ′
1 After Ashghal decided to get rid of all roundabouts.
53
54 CHAPTER 13. DYNAMIC PROGRAMMING
Task (Dependency graph). Draw the dependency graph for the potholes problem for n = 4 and m = 3.
Solution. To do.
Task (Bottom-up solution). Describe a bottom-up solution for the pothole problem.
Solution. For the bottom-up implementation, we need to traverse the dependency graph in a topological
order. A valid topological ordering which is easily parallelizable is to proceed diagonal-wise in the grid:
we compute PH (1, 1), the first diagonal. Then PH (1, 2), and PH (2, 1) in parallel, which is the second
diagonal. Then PH (1, 3) and PH (2, 2) and PH (3, 1) in parallel, which is the third diagonal, and so on.
This has an advantage of only using O(min(n, m)) memory (the maximum length of any diagonal),
since the topological ordering allows us to overwrite the memo values of the locations in the previous
diagonal, since we need the entries in the ith diagonal only to compute the entries in the i+1th diagonal.
2 Matrix Chain Product
Matrix Chain Product (MCP). In the matrix chain product problem, we are attempting to find the cheap-
est way to multiply a chain of n matrices. I.e., determine a parenthesization of the expression
A1 × A2 × . . . × An
such that cost of evaluating the expression is minimized.
Task (Recursive solution). Write a recursive solution to the matrix chain problem, assuming there is a
function cost : N × N × N → R that returns the cost of multiplying two matrices with dimension (a, b)
and (b, c).
Write a function
MCP : (N × N) seq → R
which takes a sequence of pairs (hi , wi ) (the dimensions of the ith matrix) and returns the cheapest cost
of multiplying those matrices.
Solution.
1 MCP (D) = let
2 n = |D|
3 h(i) = let (x, ) = D[i] in x end
4 w(i) = let ( , x) = D[i] in x end
5
6 MCP ′ (i, j) =
7 if j − i ≤ 1 then 0
8 else min (MCP ′ (i, k) + cost(h(i), h(k), w(j − 1)) + MCP ′ (k, j))
i<k<j
9 in MCP ′ (0, n) end
In this code, functions w and h are helpers for getting the width and height of the ith matrix.
Task (Counting subproblems). Determine how many unique subproblems are there for MCP(n, m).
.
2. MATRIX CHAIN PRODUCT 55
Solution. Subproblems: Each subproblem MCP ′ (i, j) where i ≤ j is the cheapest cost of multiplying
matrices i through j (exclusive at j).
Work: There are O(n2 ) distinct subproblems (n = |D|). At each subproblem (i, j), we require O(j −
i) ⊆ O(n) work, and therefore the total work required is O(n3 ).
Task (Dependency graph). Draw the dependency graph for the matrix chain problem for:
A1 (4, 2) × A2 (2, 3) × A3 (3, 5) × A4 (5, 1)
Solution. To do.
Task (Bottom-up solution). Describe a bottom-up solution for the matrix chain problem.
.
Solution. In the DAG, we notice that
1. subproblems of length 1 have no dependencies,
2. subproblems of length 2 depend upon subproblems of length 1,
3. subproblems of length 3 depend upon subproblems of length 1 and 2,
4. etc.
In general, subproblems of length k depend upon other subproblems which have lengths strictly less
than k. So, our bottom-up ordering should be to compute subproblems in increasing order of their
length.
We can implement line 8 of the given algorithm using ‘reduce min ∞’ after a ‘tabulate’. For a sub-
problem of length k, this requires O(log k) ⊆ O(log n) span. The longest chain of dependencies in the
DAG is length n, and therefore the total span of the bottom-up approach is O(n log n).