Homework 3
Algorithms and Data
Spring 2012
Karl Lieberherr
Due date:
Feb. 2, 2012, beginning of class.
Read Chapter 3 in the text book.
By now you should have covered chapters 1 through 3.
We are going to put the proposer of a claim into the claim:
claim XYZ(Name, ... )
where Name is the name of the team, e.g.,
Griffin-Schneider+Christopher-Souvey or if you work by yourself,
Kevin-Castaglia.
PART 1:
Proposed by Ahmed Abdelmeged
=======
In this homework, we study an existing algorithm, the Gale-Shapley
algorithm, and we want to find out how slow or how fast
it runs depending on the input.
Given an algorithm A:X -> Y and some input size n, our goal is to find the worst
input x so that some resource function: A-resource(x): X -> PositiveRational
is maximum over all inputs of the same size n.
Below we consider a decision variant of this optimization question.
We consider claims of this form:
Given an algorithm A: X -> Y and an input size n,
there exists an input x of size n
so that A-resource(x) is >= c.
A-resource is defined by an instrumentation of the algorithm
and we assume that it returns a value in [0,1].
We abbreviate this claim as MAX-RES(Name,A,n,c).
Similarly, we define claim MIN-RES(Name,A,n,c).
Example:
A = Gale-Shapley:
Gale-Shapley-resource(p) is
the number of iterations of the while loop for preference p / n^2,
where n is the number of men = number of women.
Gale-Shapley-resource(p) is a rational number between 0 and 1.
We define the JSON notation for defining a preference p as follows:
{"n":3,
"manPref" : [[2,1,0],[1,0,2],[0,1,2]],
"womanPref : [[2,1,0],[1,3,2],[3,1,2]]
}
This notation is matching Ahmed's Java program presented in class and here:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/lectures/GaleShapley%282%29.pdf
Claims are of the form:
MAX-RES(Name, Gale-Shapley, n, 0.8)
or MIN-RES(Name,Gale-Shapley, n, 0.1),
where n is the number of men = number of women and Name is the student/team name.
What are the optimum claims? About 5 teams should post an
optimum claim on Piazza. When a claim is challenged,
the preference (i.e., the input) must be given.
Each proposed claim on Piazza must be either agreed, refuted or strengthened.
What to turn in:
The protocols of the quantifier games you played with your partner.
A description of your approach to find optimum claims
and a description of your defense strategy for your
optimum claims.
PART 2:
This homework part is about determining the asymptotic behavior of the
functions we computed in hw 2: HSR(n,k) = q and M(k,q) = n.
We define HSR(n,k) to be the smallest number of questions needed in the worst-case for a ladder with rungs 0..n-1 and a jar budget of k.
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:
Landau(Name, HSR(n,k), O(exp)) meaning
HSR(n,k) in O(exp).
Landau(Name, M(k,q), O(exp)) meaning
M(k,q) in O(exp).
Landau(Name, NOT, HSR(n,k), O(exp)) meaning
HSR(n,k) !in O(exp) (negative claim)
Landau(Name, NOT, M(k,q), O(exp)) meaning
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))
or
Landau(Karl,HSR(n,2), O(n^(1/2)))
HSR(n,2) in O(n)
Landau(Karl,HSR(n,2), O(n))
HSR(n,2) in O(n)
or
Landau(Karl,HSR(n,2),O(n))
M(k,q) in O(q^k)
or
Landau(Karl,M(k,q), O(q^k))
etc.
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))
Which would you refute?
The refutation protocol is derived from the mathematical formulation
of the O notation.
What to turn in:
1. Game history: List all claims proposed, refuted and strengthened in the
order they happened in the quantifier game with your partner.
The class should put about 5 claims on Piazza to illustrate how
refutations and defenses work in this case.
2. Your asymptotic bounds for HSR(n,k) and M(k,q).