Algorithms and Data						Karl Lieberherr
Spring 2011

Homework 2

Due date: January 26, 2011 at beginning of lecture.

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

This homework is about determining the asymptotic behavior of the 
functions we computed in hw 1: HSR(n,k) = q and MR(k,q) = n.

We play the same game as in hw 1:

The scholars make claims of the form:

HSR(n,k) in O(exp) (positive claim)
MR(k,q) in O(exp)
HSR(n,k) !in O(exp) (negative claim)
MR(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)
MR(k,q) in O(q^k)
MR(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?

The game from hw 1:
mega-move: Alice - Bob
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.

Play:
(mega-move Alice - Bob    mega-move Bob - Alice) - repeat 3 times

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 problem ..., Alice provides solution, ...
Alice proposes C1, Bob strengthens C1 to C2, Alice refutes C2, Alice provides problem ..., 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 MR(k,q). Assume k is a constant.