In last recitation we went over using DFAs in code. DFAs have tremendous value in a theoretical sense too.
Consider the set of problems that are solvable using a DFA. We ask the following sort of question: How much space is used? How much time?
Well, say we have N states and a characters in our alphabet. Then we need log N space to store the state and Na space to store the transitition table: O(Na). Both N and a are fixed by the problem though: the space is independent of the size of the input. This means O(1) space!
For our time analysis, say we have M characters in our input. For each of these characters, we look up the transition for the current state and character and change the state. This, on most real computers, takes O(1) time, so the time required for all M characters is O(M).
In fact, it's possible to write any algorithm that truly uses constant space and linear time as a finite automaton. This means that if we have a problem and can show that it cannot be solved by a finite automaton, then there's no reason to attempt to get constant-space, linear-time performance.
Warshall's algorithm is yet another example of dynamic programming at work.
Say we have a directed graph as follows:
0->1 v v 3--2Then its adjacency matrix looks like the following:
0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0We have made the diagonal zero in this case, but this is just a matter of definition.
Our goal is to create a matrix B such that B[i][j] = TRUE if and only if there is a path from i to j in the graph specified by adjacency matrix A. In the above graph, the resulting value should be:
0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0
We use a dynamic programming idea to solve this problem: successively determine whether there is a path from every i to every j going only through vertices 0 through k-1 intermediately, and increase k to N.
On the example, after iteration 0, the graph looks like the original, because there are no paths through 0. After iteration 1, because there is a path from 0 to 2 through 1, the graph becomes:
0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0After iteration 2, the matrix becomes
0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0
On each iteration here, we're setting entry B[i][j] to one if either B[i][j] is already one or if B[i][k] is one and B[k][i] is one.
Here's the code:
// make a copy of the adjacency matrix
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
B[i][j] = A[i][j];
// after each iteration of the outside loop, B[i][j] = TRUE if
// there is a path from i to j that passes through only vertices
// in the set 0..k -- this is an example of dynamic programming
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
B[i][j] = B[i][j] || (B[i][k] && B[k][j]);
How much time does this algorithm take? O(N^3) time.
It's just like Warshall's algorithm for transitive closure, except that || is replaced with the min operator, and && is replaced with +.
Draw a picture to show where the following line of code comes from:
B[i][j] = min(B[i][j], B[i][k] + B[k][j]);