-------------------------- * Monday: dynamic programming. * Wednesday: greedy algorithms. * Today: dynamic programming and greedy algorithms. DYNAMIC PROGRAMMING I: MATRIX MULTIPLICATION. First: A m-by-n B n-by-p AB? m-by-p. How much time to compute AB? Well, mnp multiplications naively. (can do a little better using Strassen-like ideas). Second: ABC = (AB)C = A(BC). Multiply 1 x 10, 10 x 1000, 1000 x 10. (AB)C --> need 1 10 1000 multiplications for (AB), then 1 1000 10 for (AB)C. 20000 total. A(BC) --> need 10 1000 10 for (BC) then 1 10 10 for A(BC). 100100 total. Given: Matrices M_1, M_2, \ldots, M_k. Matrix M_i is n_i by n_{i+1}. Output: parenthesize matrices so that the cost of multiplying like that is minimized. How many different ways of doing this are there? It's the same as the number of binary trees with k nodes. The kth CATALAN NUMBER C(k) = (2n choose n)/(n+1). Exponential. PAREN-DUMB(n[1..k]) // there's some pair that we multiply together first // say M[j],M[j+1] pick the cheapest for j=1..k-1 cost[j] = n_j n_{j+1} n_{j+2} + PAREN-DUMB(with n_j, n_{j+1} merged). How dumb is this? Very! Its running time is even more than C(k)! Why? (Tries 1-2 then 5-6, and also 5-6 and then 1-2!) PAREN-NOT-SO-DUMB(n[1..k]) // look at _last_ multiplication M[j], M[j+1]. pick the cheapest for j=1..k-1 cost[j] = PAREN(n[1..j]) + n_1 n_{j+1} n_{k+1} + PAREN(n[j+1..k]). Memoize! How many different distinct subproblems are there? PAREN(n[i ... j]). --> k^2. For a dynamic program, define OPT(i,j) := cheapest way of multiplying M[i..j] together. = min_{i <= x < j} OPT(i,x) + n_i n_x n_{j+1} + OPT(x+1,j). OPT(i,i) = 0. Lemma (optimal substructure): The optimal multiplication has the form (optimal multiplication of 1..i) * (optimal multiplication of i+1..n) for some i. proof: Surely must look like that sans "optimal" since you have to do some last multiplication. If not optimal on the left, then replace the left by optimal, and you just made the whole thing better. Similarly on the right. So runs in time O(n^3). --------------------------- --------------------------- DYNAMIC PROGRAMMING II: OPTIMAL BINARY SEARCH TREES Suppose that you know in advance the distribution of searches in a static set. You want to build a BST that minimizes the average case search time in this setting. E.g., my 6.046 emails: extension 25% regrade 10% clarification 40% happy 5% stress 20% happy 5% clarification regrade 50% extension stress 45% so average search time = average depth of node = 1(0.05) + 2(0.50) + 3(0.45) = 2.4 better: put the more frequent words at the root: extension 25% clarification regrade 50% happy stress 25% 1(0.25) + 2(0.50) + 3(0.25) = 2.0 Given the probabilities of a search p[1..n], find the optimal BST. P(i,j) = \sum_{k=i}^j p[k] probability that the search will be for a word with index between i and j. OPT(i,j) = min_{i <= r <= j} [ OPT(i,r-1) + OPT(r+1,j) + P(i,j) ]. ^^^^^^ deepens each elmt by 1 OPT(i,i) = p[i]. --------------------------- --------------------------- GREEDY I: MINIMUM SPANNING TREES (AGAIN) Recall the mininum spanning tree (MST) problem: given a (connected) graph G, find a tree T that *spans* all of the vertices of G and minimize the weight of the tree you find. Here's a reasonable algorithm ... Kruskal's algorithm: 0. T := empty. 1. sort the edges by weight in increasing order. 2. for each edge e (taken in sorted order), if the endpoints of the edge aren't connected by T, add e to T. 3. return T. Does this return an MST? WHY? well, recall the theorem from class: Let A \subseteq T be any subset of the nodes of G, for any MST T. Let (S, V-S) partition V, s.t. all edges of A are within S or within V-S. Let e be any lightest edge from S to V-S. Then there is an MST T* so that A \cup {e} \subseteq T*. Immediate from the the above theorem! When we add edge e, it's always lightest edge connecting two components, so it's safe. How do you implement this? Use the union/find disjoint set data structure. Running time? Sort in O(m log m) time. Each "are we connected?" check is O(alpha(m)) amortized. Total: O(m (log m + alpha(m)) = O(m log m). Note that if the edge weights are small integers <= m^2 or something, can do better: -- use radix sort, say. -- running time now O(m + m alpha(m)) = O(m alpha(m)). --------------------------------------- --------------------------------------- GREEDY II: HUFFMAN CODES (probably no time to cover this one) [Similar to optimal BSTs] Suppose you have probabilities p[1...n] on, say, all letters in the English language. ("e" is frequent, "q" is rare.) Want to encode each word a possibly different-length sequence of bits, minimizing the number of bits used on average. special property: want our encoding to be PREFIX-FREE. for any two letters x, y, encoding(x) cannot be a prefix of encoding(y). why? this allows us to decode on the fly (just keep reading until you see an encoded letter; then output it and continue.) e.g., frequencies in my notes so far: A 149 B 49 C 66 D 63 E 217 F 41 G 44 H 72 can think of this as a tree: Left == 0 Right == 1 prefix-free == only leaves can represent encodings. not necessarily a BST! any thoughts on how to build this? greedily. take two least frequent letters & join them. think of combined "FG" as a new symbol. repeat FG /\ F G A 149 B 49 C 66 D 63 E 217 FG 85 H 72 B,D FG BD /\ /\ F G B D A 149 BD 112 C 66 E 217 FG 85 H 72 C,H FG BD CH /\ /\ /\ F G B D C H A 149 BD 112 CH 138 E 217 FG 85 FG, BD BDFG / \ FG BD CH /\ /\ /\ F G B D C H A 149 BDFG 197 CH 138 E 217 A, CH BDFG ACH / \ / \ FG BD CH A /\ /\ /\ F G B D C H ACH 287 BDFG 197 E 217 BDFG,E BDEFG / \ E BDFG ACH / \ / \ FG BD CH A /\ /\ /\ F G B D C H ACH, BDEFG ___ABCDEFGH___ / \ BDEFG ACH / \ / \ E BDFG CH A 00 / \ /\ 11 FG BD C H /\ /\ 100 101 F G B D 0100 0101 0110 0111 Note that we'd need log_2(8) = 3 bits per letter with a fixed-length encoding. Thanks to Steve for: 01110011011110100110111 0111 00 11 0111 101 00 11 0111 D E A D H E A D Thus would have been 8*3=24; we managed 23. In bigger examples, it's an even bigger difference. Why is this optimal? LEMMA: There is an optimal prefix code with the two lowest frequency letters as siblings at the lowest level of the tree. proof: an _exchange argument_. take the two minimum frequency nodes. take any two lowest-depth siblings. trade. the cost of the new tree is no bigger than the cost of the old tree! (should calculate details ...)