* Monday:     maximum flow algorithms.
* Wednesday:  string matching.
* Today:      max flow, string matching, my exit survey.

"THE BELLS"
Edgar Allan Poe (1849)

    Hear the sledges with the bells-
    Silver bells!
    What a world of merriment their melody foretells!
    How they tinkle, tinkle, tinkle,
    In the icy air of night!
    While the stars that oversprinkle
    All the heavens, seem to twinkle
    With a crystalline delight;
    Keeping time, time, time,
    In a sort of Runic rhyme,
    To the tintinnabulation that so musically wells
    From the bells, bells, bells, bells,
    Bells, bells, bells-
    From the jingling and the tinkling of the bells. 

---------------------
PART I:  BIPARTITE MATCHING VIA LPS AND NETWORK FLOW.

a MATCHING in a graph is a subset of the edges so that no single node
is matched twice (= is incident to more than one edge).

a MAXIMUM MATCHING is one containing a maximum number of edges.

Let's write this as a linear program.

Let x_{u,v} be a variable denoting that we match nodes u and v.

Then we can write this as:

     max \sum_{u,v} x_{u,v}
     
     for all u,v   x_{u,v} = x_{v,u}          // I match yours, you match mine.

     for all u     \sum_{v} x_{u,v} <= 1      // match at most one neighbor.

     for all u,v   x_{u,v} <= 1 if (u,v) in E
                              0 otherwise     // only match on edges.

     for all u,v   0 <= x_{u,v}               // never negative match.


We can solve linear programs in polynomial time.  (That is, efficiently.)
So, does this solve the maximum-matching problem?
NO!
The result of the linear program will be feasible settings of the variables.
But what does x_{u,v} = 0.5 mean?
The result is not necessarily integral. 

If you add the constraint x_{u,v} \in {0,1}, then the problem becomes
very difficult to solve.  (Nobody knows how to solve it in polynomial
time.)
     

Can still solve the matching problem efficiently, but let's look 
at a special case:  BIPARTITE MATCHING.

a BIPARTITE GRAPH G=(U \cup V, E) has
    U and V are disjoint  
    E \subseteq U \times V.

how do you write bipartite matching as a max flow problem?

want to route max possible flow from left nodes to right nodes.


add supersource, edge to each left node with capacity one.
add supersink, edge from each right node with capacity one.
put capacity one on all the edges.

run your favorite max flow algorithm.

[very similar to homework.]
---------------------------------------------------------------------

---------------------------------------------------------------------
PART II:  STRING MATCHING

In lecture, we talked about a randomized algorithm to do string
matching in a text in linear time.  There's Knuth/Morris/Pratt to do
the same thing in deterministic linear time.

Here:  some ideas to get O(poly(m) + n) time.
       read the book for O(m + n).


Suppose you want to find the string 
  TINTINNABULATION
in a very long text.

Idea:  scan along the text.  
       keep track of how much of the pattern you've matched so far.

You see:   TIN                  so far so good.
           ^^^
	   TINTIN		so far so good.
	   ^^^^^^
	   TINTINT		no good.  but still off to a good start!
	      ^^^^

Move linearly along the text.  
Track how much we've matched at any point.
If we've matched everything, note as a match.

How do we track how much we've matched at any point?

Let's build a table:

  if we've matched        
  this many 
  characters ...      ... and this is the next character we see

                 A  ...  I  J  K  L  M  N ... T  U  V  W  X  Y  Z
     0 []        0  ...                       1   
     1 [T]               2                    1
     2 [TI]                             3     1
     3 [TIN]                                  4
     4 [TINT]            5                    1
     5 [TINTI]                          6     1
     6 [TINTIN]                         7     4
     7 [TINTINN] 8                            1 

Can build this table in time O(m^3 |sigma|) time.
  for each entry in the table,
    for each left shift of the pattern,
      check if the shift is consistent.

Can use this basic idea and improve.
Knuth/Morris/Pratt:  Table is of size m, not m*sigma.
		     can build in time linear in m.		   
basic idea:
  -- don't eat up the next character of the text.
  -- use table to tell you previous index to try.

BTW, what you're building here is a finite state machine (or
deterministic finite automaton).