15-451 Algorithms 11/20/13 recitation notes * Do the list-update from last time if you want * Randomized Weighted Majority & network flows * FFT [you can decide what you want to cover from this - it's probably too much to do all of it] ================================================================= List-update ----------- See notes from last time Randomized Weighted Majority & network flows -------------------------------------------- In class, we presented an algorithm (called "randomized weighted majority" or "multiplicative weights") that we showed you could use to repeatedly play a game and do nearly as well as the best fixed-strategy in hindsight. Now remember that for the max s-t flow problem, in the case where all edges have capacity 1, we had a way of viewing it as a 2-player game we called the "smuggler and border guard game". Recall the setup: we have a graph G, and nodes s,t. - The smuggler chooses a path P from s to t. - The border guard chooses an edge e in G. If e \in P, then the border guard wins, else the smuggler wins. The border-guard's minimax optimal strategy is to find a minimum s-t cut (say it is k edges) and then to choose uniformly at random from those k edges. This ensures that whatever path P the smuggler chooses, there is at least a 1/k chance the border guard wins. The smuggler's minimax optimal strategy is to find a maximum s-t flow (which will have value k if the min-cut has size k) and then to divide all flow values by k (so we now have 1 unit of flow from s to t, with at most 1/k units flowing on any given edge) and then to choose a path P probabilistically s.t. the probability of using any given edge e is at most the flow value f_e. This guarantees there is at *most* a 1/k chance that the border guard wins. Hmm - can we really do this? This is interesting to think about. There is a total of 1 unit of flow leaving s, so for sure we can pick an initial edge to take so that the probability of choosing any given edge (s,v) equals the flow on that edge f_{sv}. When we get to the endpoint v, we will then just choose our next edge with probability proportional to the flow on it. It's easiest to see why this works by drawing out a small example. We are basically just "flowing probability mass" through the graph. (What are we flowing? probability!) You can also prove this by induction. OK, now how can we use randomized weighted majority in this game? In this game, the smuggler has too many choices (there may be exponentially many different paths from s to t). But the border-guard has only m choices (m = number of edges). So, lets use RWM for the border guard: we start with equal probability on all the edges, and then for the smuggler we find the path where the smuggler has the least chance of getting caught. How can you find it? This is just a shortest path, using the probabilities as lengths. Then we update the border-guard's distribution using RWM's updates based on this path. Then we repeat. The argument from class says that RWM's strategy will approach minimax optimal, so this is another way of solving for an (approximately) minimum cut. Is it faster? Not as stated. But the current fastest approximate-min cut algorithms do use this idea, but with a variant on this game based on connections to the electrical flows you saw on your homework. FFT === The most important thing to know about FFT is that it gives you an algorithm that runs in time O(n log n) for computing the convolution of two vectors of length n. Say A,B are vectors of length n. The convolution C is defined as: C_i = A_0*B_i + A_1*B_{i-1} + ... + A_i*B_0. for i between 0 and 2n-2. Note that for i>n we view A_i = 0 and B_i = 0. Here is an interesting application. Say you have a file filled with 0's and 1's. e.g., 011101111110100101011010101001 and you want to look up all instances of a pattern "11*1" in this file. The "*" is a wildcard that can match a 0 or 1. (To make this easier, we will assume the pattern has just 1's and *'s, but no 0's. If you want you can think at home how to handle 0's too). Here's a way we can do it. Let A be the vector for the file. I.e., A = 011101111110100101011010101001 Let B be a vector where the *'s in the pattern are replaced with 0's, and then the pattern is reversed and padded with 0's. E.g., in this case it would be B = 101100000000000000000000000000 Now do a convolution: A = 011101111110100101011010101001 B = 101100000000000000000000000000 C = 01122322333... The 3's in C (or more generally, the entries equal to the number of 1's in the pattern) are the places where the pattern matches.