15-451 Algorithms 10/08/08 RECITATION NOTES * Maximum bottleneck path * Coupon-collectors problem ======================================================================= In class we saw a couple greedy tree-growing algorithms for different problems. *Dijkstra for computing shortest path tree* initialize: - tree = {start}. No edges. label start as having distance 0. [invariant: nodes in tree have correct distance to start.] repeat: - for each nbr x of tree compute (over)-estimate of distance to start: distance(x) = min [ distance(v) + length(e) ] edges e=(v,x) v in tree [by our invariant, this is the length of the shortest path to x whose only edge not in the tree is the very last edge.] - put x of minimum distance into tree, connecting it via the argmin (the edge e used to get distance(x)) *Prim for computing minimum spanning tree* - just like Dijkstra but remove "distance(v)" in the distance(x) calculation. I.e., it's just the length of the shortest edge connecting x to the tree. Here is a different problem, called the maximum bottleneck path problem. MAXIMUM BOTTLENECK PATH ----------------------- Suppose we think of edge weights as "widths" rather than "lengths" and we want to find the widest path from s to everwhere in the graph. Say we define the width of a path as the minimum width of all edges on the path and let's use widthto(v) to denote the width of the widest path from s to v. E.g., think of edge weights as capacities (number of megabits/second you can send on a link). How can we modify Dijkstra's algorithm to solve this problem? Initialization: set widthto(s) = infinity. general step: widthto(x) = max [ min [ widthto(v), length(e)] ] edges e=(v,x) v in tree and now put the node x of *maximum* widthto(x) into the tree. ------------------------------------------- Coupon-collector's problem ========================== This is a problem that's a good one for practice with probability and linearity of expectation. The problem is: suppose we have n boxes (let's label them 1,...,n) and we repeatedly throw balls into the boxes at random. What is the expected number of throws until every box has at least one ball in it? Answer: nH_n (where H_n = 1+1/2+1/3+...+1/n) The proof is as follows. Imagine a counter (starting at 0) that tells us how many boxes have at least one ball in it. Let X_1 denote the number of throws until the counter reaches 1 (so X_1 = 1). Let X_2 denote the number of throws from that point until the counter reaches 2. In general, let X_k denote the number of throws made from the time the counter hit k-1 up until the counter reaches k. So, the total number of throws is X_1 + ... + X_n, and by linearity of expectation, what we are looking for is E[X_1] + ... + E[X_n]. How to evaluate E[X_k]? Suppose the counter is currently at k-1. Each time we throw a ball, the probability it is something new is (n-(k-1))/n. So, another way to think about this question is as follows: Coin flipping: we have a coin that has probability p of coming up heads (in our case, p = (n-(k-1))/n). What is the expected number of flips until we get a heads? It turns out that the "intuitively obvious answer", 1/p, is correct. But why? Here is one way to see it: if the first flip is heads, then we are done; if not, then we are back where we started, except we've already paid for one flip. So the expected number of flips E satisfies: E = p*1 + (1-p)*(1 + E). You can then solve for E = 1/p. The above argument is a little tricky, so if you want, you can draw a picture of a tree like this, where what we are looking for is the sum, over all leaves, of the depth of the leaf times the probability of reaching that leaf. * p/ \(1-p) * * p/ \(1-p) * * ... And if we let T denote that tree, the argument is saying just that one simple way of analyzing T is to view T as: * p/ \(1-p) * T Putting this all together, let CC(n) be the expected number of throws until we have filled all the boxes. We then have: CC(n) = E[X_1] + ... + E[X_n] = n/n + n/(n-1) + n/(n-2) + ... + n/1 = n(1/n + 1/(n-1) + ... + 1/1) = n H_n. QED.