Algorithms and Data						Karl Lieberherr
Fall 2011

Homework 3

Due date: September 28, 2011 at beginning of lecture.

Reading:
At the end of the week you should have completed reading chapter 1-3
of the textbook.

PART 1:

This homework part is about determining the asymptotic behavior of the 
functions we computed in hw 1: HSR(n,k) = q and M(k,q) = n.
M(k,q) is the maximum number of rungs we can handle
with k jars to break and q questions.

We play again the quantifier game.

The scholars make claims of the form:

HSR(n,k) in O(exp) (positive claim)
M(k,q) in O(exp)
HSR(n,k) !in O(exp) (negative claim)
M(k,q) !in O(exp)

where exp is an expression using powers (including fractional exponents),
logarithms and exponential functions.

The same for Big Omega and Big Theta in addition to Big O.

Example claims:
HSR(n,2) in O(n^(1/2)) (positive claim)
HSR(n,2) in O(n)
M(k,q) in O(q^k)
M(q,q) in O(2^q)
HSR(n,2) in Theta(n^(1/2))
HSR(n,2) !in O(n^(1/3))
HSR(n,2) !in O(log(n)) (negative claim)

Which would you refute?

Alice proposes 5 claims
Some of the claims must be positive and some negative.
Bob refutes or strengthens or agrees

The refutation protocol is derived from the mathematical formulation
of the O notation.

It is used for refutation.
It is used for strengthening: The strengthened claim is subjected to a refutation.

If both Alice and Bob agree that a claim is optimum, it is declared as an optimum claim.
For such optimum claims you should prove that they are indeed optimum but this
proving is outside the game.

PART 2:
===================================================
Answer exercise 8, chapter 3 by turning it into a game.

Refutation protocol:
Alice makes the claim shown on page 110.
Bob tries to refute.

Alice gives c to Bob.
Bob constructs a graph G so that diam(G)/apd(G) > c.
Bob wins if he succeeds.

In the second game, Bob makes the claim which is the negation
of the claim that Alice made.
What is the refutation protocol now?

Turn in your game history.
And jointly come up with the answer to question 3.8
based on the ideas you developed during the game.

Andrei Mackenzie (from last semester)
wrote about his experience with SCG and this homework:

The SCG is most useful when the validity of the initial claims isn't known or
strongly suspected. For the diameter/average-point-distance problem concerning
graphs, for example, playing the game through several iterations with different
values provides not only a hint about the probable validity of the claim, but
more importantly also provides insight in to how to construct a counter-example
for the general case.

Keep this in mind as you play the game.

What to turn in:

1. Game history: List all claims proposed, refuted and strengthened in the
order they happened in the game.

E.g.
Alice proposes C1, Bob refutes C1, Bob provides instance ..., Alice provides solution, ...
Alice proposes C1, Bob strengthens C1 to C2, Alice refutes C2, Alice provides instance ..., Bob provides solution, ...
Alice proposes C1, Bob agrees with C1, Alice agrees with C1: C1 is declared optimum.

2. Your asymptotic bounds for HSR(n,k) and M(k,q). Assume k is a constant.

3. Solution to problem 3.8.