Algorithms and Data
Fall 2010

Due date: October 20, 2010
At beginning of lecture


Problem 6:

Decision Problems versus Search Problems

This is a continuation of the LeafCovering homework.
In the earlier homework we came up with a yes/no answer
for a given LeafCovering problem.
Now we want to find an uncovered leaf if one exists.

For satisfiability, if we have a polynomial-time algorithm for deciding satisfiable/unsatisfiable,
we have a polynomial-time algorithm to find a witness.
We choose a variable x and consider the Shannon cofactors F[x] and F[!x]. If F is satisfiable, one of them
must be satisfiable which tells us how to set x.
We iterate through all variables.

A similar idea works for LeafCovering. 
The algorithm can be viewed as a greedy algorithm.

We know there is a polynomial-time algorithm to solve LeafCovering(k),
where k, a constant, is the number of elements that are covering the leaves.

LeafCovering(k):
Input: A set of trees and M, where |M|=k.
Output: yes or no.

FLeafCovering(k):
Input: A set of trees and M, where |M|=k.
Output: An uncovered leaf or no, if none exists.

Give a polynomial algorithm for FLeafCovering(k).

Let's assume that each tree has max outdegree of c and 
let's assume the trees are of at most depth d.

=================
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.