Scribd
Upload
2 views2 pages

Rec11 Dynamic Programming

Chapter 13 discusses dynamic programming with a focus on two problems: the potholes problem and the matrix chain product problem. For the potholes problem, it covers recursive solutions, counting unique subproblems, top-down and bottom-up approaches, and dependency graphs. The matrix chain product section similarly addresses recursive solutions, unique subproblems, dependency graphs, and bottom-up solutions for minimizing multiplication costs of matrices.

Uploaded by

jhussien
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Rec11 Dynamic Programming

Chapter 13 discusses dynamic programming with a focus on two problems: the potholes problem and the matrix chain product problem. For the potholes problem, it covers recursive solutions, counting unique subproblems, top-down and bottom-up approaches, and dependency graphs. The matrix chain product section similarly addresses recursive solutions, unique subproblems, dependency graphs, and bottom-up solutions for minimizing multiplication costs of matrices.

Uploaded by

jhussien
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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.
Task (Counting subproblems). Determine how many unique subproblems are there for PH(n, m).
Task (Top-down solution). Write the (pseudo)-code for a top-down solution for the potholes problems
using the memoization library from DPLab.
Task (Dependency graph). Draw the dependency graph for the potholes problem for n = 4 and m = 3.
Task (Bottom-up solution). Describe a bottom-up solution for the pothole problem.

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.
1 After Ashghal decided to get rid of all roundabouts.

53
54 CHAPTER 13. DYNAMIC PROGRAMMING

Task (Counting subproblems). Determine how many unique subproblems are there for MCP(n, m).
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)

Task (Bottom-up solution). Describe a bottom-up solution for the matrix chain problem.

You might also like