Admin:

Recall hw5 program is due 9pm Thursday.  I have not enabled
turnin yet, but that should be soon.

For hw5 written: I do not have it ready yet, so expect an email
announcement when it is ready.  Unlike previous homeworks, it will be
mostly short "exam style" problems, so that it will also serve as
review for our final (which is 4:30pm Friday 5/4).  Examples of such
problems (for recent topics): 1. given a pattern string, show its KMP
DFA, and its KMP NFA 2. given symbol frequencies, derive their Huffman
code, and then encode some message using that code 3. given a sequence
of LZW codes, decode them 4. given a flow network: find a max flow,
its residual network, and a min-cut.

Today:

Finishing LZW decoding, including the "tricky case", and also
  what we might do when the table fills up, and to end the file.
  See: slides starting around page 38
       55DemoLZW.mov (animated example)
       ../book/LZW.java  (note they use code=R to mark EOF)

A remark on BWT+Huffman: you would definitely need *adaptive* Huffman
(or something similar, not the fixed Huffman in the book code) to take
advantage of the local repetitions in the BWT output.

Finally, introducing our last "big" topic:

Section 6.4, MinCut/MaxFlow (and a brief intro to linear programming)

I'll introduce the basic problems, and we'll get started towards the
Ford-Fulkerson algorithm (and concepts like the residual graph).

See: 64MaxFlow.pdf