Algorithms and Data CS 4800
Karl Lieberherr

Due: Thursday, April 7, 2010

Still doing the Scientific Community Game but now with hypotheses related to
Network Flow.

We turn exercise 7.12 (Chapter 7) into a hypothesis:
I claim that I have a polynomial-time algorithm to solve 7.12.

We turn exercise 7.23 (Chapter 7) into a hypothesis:
I claim I have an algorithm whose running time is within a constant factor of 
the time required to compute a single maximum flow.

Please take turns: if Bob proposes first the hypothesis for problem 7.12
then Alice first proposes the other hypothesis.

The refutation protocol is about finding a bug in the algorithm by giving it
an input where it produces the wrong result or by showing that it runs too slow.



What to turn in:
A text file containing the protocols which should describe a solution to 7.12 and 7.23.