The problems in this homework are from Lecture 9 (Nuts and Bolts/Randomized Algorithms) and Lecture 14 (Randomized Minimum Cut) of Jeff Erickson's notes. Each of the five exercises is worth 10 points.
  1. Exercise 6 of Lecture 9.
  2. Exercise 8 of Lecture 9.
  3. Exercise 15 of Lecture 9. There is a typo. The correct reading is: `if X[i] is the largest element of X, then X[N[i]] is the smallest element of X; otherwise, X[N[i]] is the smallest among the set of elements in X larger than X[i].'
  4. Exericse 17 of Lecture 9.
  5. Exercise 2 of Lecture 14 on Randomized Minimum Cut.

The homework is due in class on Tuesday, March 27.