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.