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