The problems are from Jeff Erickson's notes. They are all worth the same number of points.
  1. Exercise 2 of Lecture 9 (Randomized Algorithms).
  2. Exercise 6 of Lecture 9.
  3. Exercise 8 of Lecture 9.
  4. Exercise 11 of Lecture 9 -- parts (a), (b), and (c).
  5. Exercise 12 of Lecture 9.
  6. Exercise 16 of Lecture 9 -- parts (a) and (b).

The homework is due in class on Tuesday, April 8.

A note on grading: You will receive 37.5 percent of the grade for convincing us that you made a serious attempt at solving the problem. 25 percent of the grade is for the quality of the writing. The remaining 37.5 percent depends on how close your attempts are to a correct solution.