CSE 417 Homework 1, Winter 2011

Do this assignment independently, without the use of online resources or collaboration. Submit your answers to items 2-7 on paper at the beginning of class on January 12.
  1. (10 points). Complete the online background survey.
  2. (10 points). In Kleinberg and Tardos, Chapter 1, Exercise 1. Either prove it to be true or prove it to be false (e.g., by giving a counterexample).
  3. (20 points). In Kleinberg and Tardos, Chapter 1, Exercise 2. Either prove it to be true or prove it to be false.
  4. (20 points). Solve the "Countess's Conundrum".
  5. (20 points). Suppose you have the five running times given below (and assume they are exact). Suppose you have a computer than performs 10 to the 11 power operations per second, and that you will need to compute the answer to your problem in at most 5 minutes. For each algorithm, give the largest input size n for which you would be able to get the result within five minutes. 
    a.  n^2
b.  n^3
c.  n log n
d.  2^n
e.  2^(2^n)
  6. (10 points). In Kleinberg and Tardos, Chapter 2, Exercise 4.
  7. (10 points). In Kleinberg and Tardos, Chapter 2, Exercise 8a.