[Cs4800] Hw 6 game

[Karl Lieberherr]

To have a fun learning experience you should again
engage your partner to "test" your algorithm.

Play the (scientific community) game with your partner
by making claims of the form:
I have a polynomial-time algorithm for FLeafCovering(k) and
its running-time is O(f(n)).

The refutation protocol is:
Alice makes the above claim.
Alice provides her algorithm in source form to Bob.
Bob analyzes the algorithm.
He wins, if he finds an input where the algorithm
gives the wrong result or if he shows that Alice'
analysis of the algorithm is incorrect (it
is NOT O(f(n)).

Note that this refutation protocol is rather informal.
The refutation protocol for Highest Safe Rung
or Big O Notation was very precise.
Also note that in this refutation protocol the
players have to reveal their algorithms.
This was not the case for Highest Safe Rung.

After the Alice against Bob game you have
a Bob against Alice game.
-------------- next part --------------
HTML attachment scrubbed and removed