ISE 390 -- Programming Challenges -- Week 10 Notes
This Week's Goals:
To review the basic principles of dynamic programming.
Don't Be Greedy
Many problems call for finding the "best" solution satisfying
certain constraints. For example, the backtracking problems
often asked for the largest, smallest, or highest scoring
configuration. Backtracking searches all possible solutions,
picking the best one, and hence *has* to return the correct answer.
But this can be too slow for large problems.
For many important problems in graph algorithms, efficient procedures
are known to find the optimal solution, including shortest paths,
minimium spanning trees, and matchings. It is important to know
what these problems are so you can recognize when you can just plug
in an appropriate solution.
There is a temptation to use some intuitive or "greedy" procedure
to identify the best solution, such as making the best local
choice at each decision point. In the absence of a proof of
correctness, such algorithms are almost certainly wrong.
Dynamic programming is a way to design custom algorithms for
a wide variety of problems which systematically searches
all possibilties (hence guaranteeing correctness) but which
stores results to avoid recomputing (hence permitting efficiency)
Dynamic Programming:
Dynamic Programming is a technique for computing recurrence relations
efficiently by sorting partial results.
The first trick is to describe the solution to the entire problem in
terms of solutions to smaller problems. This defines a recursive algorithm.
The second trick is to see that the recursive algorithm tries to repeatedly
compute the same subproblems over and over and over again, so storing them
in a table can lead to an efficient algorithm.
How Do We Reconstruct the Path
The dynamic programming recurrence typically returns the cost of the
optimal solution, but how does one get the correct path?
To reconstruct the solution (instead of just the cost) we must keep
track of which decision we made at each local point, and then trace
backwards from the optimal solution to reconstruct the path.
Example: Multiplying a Sequence of Matrices
Suppose we want to multiply a long sequence of matrices
$A * B * C * D \ldots$.
Multiplying an $X * Y$ matrix by a $Y * Z$ matrix (using the
common algorithm) takes $X * Y * Z$ multiplications.
We would like to avoid big intermediate matrices, and since matrix
multiplication is {\em associative}, we can parenthesise however we want.
Matrix multiplication is {\em not communitive}, so we cannot permute the
order of the matrices without changing the result.
Consider $A * B * C * D$, where
$A$ is $30 * 1$, $B$ is $1 * 40$,
$C$ is $40 * 10$, and $D$ is $10 * 25$.
There are three possible parenthesizations:
((AB)C)D=30 * 1 * 40+30 * 40 * 10+30 * 10 * 25 = 20,700
(AB)(CD)=30 * 1 * 40+40 * 10 * 25+30 * 40 * 25 =41,200
A((BC)D)=1 * 40 * 10+1 * 10 * 25+30 * 1 * 25 = 1400
The order makes a big difference in real computation.
How do we find the best order?
Let $M(i,j)$ be the {\em minimum} number of multiplications
necessary to compute $\prod_{k=i}^{j}A_{k}$.
The key observations are:
(1) The outermost parentheses partition the chain of matricies $(i,j)$
at some $k$.
(2) The optimal parenthesization order has optimal ordering on
either side of $k$.
M(i,j) = Min_{i\leq k \leq j-1}[M(i, k)+M(k+1, j)+d_{i-1}d_{k}d_{j}]
M(i,i) = 0
The following code fragments have been lifted from Sedgewick's "Algorithms
in C++" book:
/* Matrix chain multiplication */
for (i = 1; i <= N; i++)
for (j = i+1; j <= N; j++) cost[i][j] = INT_MAX;
for (i = 1; i <= N; i++) cost[i][i] = 0;
for (j = 1; j < N; j++)
for (i = 1; i <= N-j; i++)
for (k = i+1; k <= i+j; k++)
{
t = cost[i][k-1]+cost[k][i+j]
+r[i]*r[k]*r[i+j+1];
if (t < cost[i][i+j])
{ cost[i][i+j] = t; best[i][i+j] = k; }
}
order(int i, int j)
{
if (i == j) cout >> name(i); else
{
cout >> '(';
order(i, best[i][j]-1); order(best[i][j], j);
cout >> ')';
}
}
Assigned Problems:
116 -- Find the shortest LR path across a weighted grid. Can this be done
with Dijkstra's algorithm? Is there a simpler algorithm because
the graph is a circular grid?
147 -- How many ways can you make change of a given value with a specific
set of denominations? This is a classic DP problem -- find a
recurrence relation to do the counting and use DP to implement it.
164 -- Find the minimum edit distance (or approximate string matching,
or Levenstein distance) between two strings, with the output
in a pecular format.
231 -- Find the longest decreasing subsequence of a stream of numbers.
Can you do this with a simple variation of string edit distance?
357 -- How many ways to make change again, with different denominations.
Can you easily reuse your program from problem 147?