Algorithms and Data						Karl Lieberherr
Fall 2010

Due date: September 22, 2010 at beginning of lecture.

Reading:
At the end of the week you should have completed reading chapter 2
of the textbook.

An independent set, or a stable set, in a graph is a set of mutually nonadjacent
vertices. The problem of finding a maximum independent set in a graph,
IndSet, is one of most fundamental combinatorial NP-hard problems.

Read what is in chapter 1 about the Independent Set problem.

What you learn by playing the IndSet game:
1. You learn about a fundamental optimization problem.
2. You learn to work with graphs: how to communicate them.
3. You learn about the difference between checking and searching algorithms.
3. You learn about hiding secrets.
4. You learn about searching for secrets.
   See http://parlab.eecs.berkeley.edu/wiki/patterns/backtrack_branch_and_bound
   for help with the Branch&Bound Pattern if you don't want to search
   the entire space.
5. You learn about the difference between polynomial-time and exponential algorithms.
6. You learn about how to communicate your algorithms to the machine. 

claim IndSet(n, 0.9, t(n)):
Alice can construct a graph G with at most
n vertices and she can construct a secret independent set I1 for G
so that Bob, given G, size(I1) and t(n) minutes only, 
cannot find an independent set I2 with size(I2) >= size(I1)*0.9.

We assume that n <= 100 and t(n) = 10 minutes: 
Our claim is IndSet(100, 0.9, 10).

The refutation protocol is:
Alice constructs graph G and deposits her secret independent set I1.
Alice gives G as well as the size of I1 to Bob.
Bob has 10 minutes to construct his independent set I2
which he gives to Alice. 
Alice reveals her secret set I1.
Bob wins iff size(I2) >= size(I1)*0.9

Example:
Alice constructs a graph G with 100 nodes.
She finds an independent set with 50 nodes.
She gives G and the number 50 to Bob.
Bob finds within 10 minutes an independent set with 43 nodes.
Alice gives to Bob her independent set so that Bob can check.
Alice checks that Bob's set is an independent set.
Alice has won because 43 < 50 * 0.9.

Bob does not have to completely reproduce Alice' secret.
He only has to get close to it to win.
Alice and Bob may use computers for their tasks.

The game is about hiding and rediscovering secrets
in the context of independent sets.
Hiding and rediscovering secrets is the key to modern cryptography.
Consider the following claim:
Alice can construct a number n with k binary digits
which is the product of two secret primes p1 and p2
so that Bob, given n and 1 hour, cannot find the two
primes. If k is big enough, Bob will not succeed.
If he could, he could decipher all of Alice' messages.

Disclaimer: I don't know whether the factor 0.9 is right.
It might make the game too easy. You will find out and you are
encouraged to make it higher.
If you use graphs that are small, you have to set the factor 0.9 to 
1 because it is easy to find the secret by enumerating all subsets.

Play the game:
Alice-Bob
Bob-Alice
and repeat three times.

Turn in the history of your games and the tools you developed to win.
If you used programs, turn them in too.

Don't spend too much time on this homework by trying to find the best
secret hider and the best solver.