There are five problems in this homework. Each is worth 10 points. The problems are from Jeff Erickson's notes.
  1. Exercise 2 of Lecture 0.
  2. Exercise 3 of Lecture 0.
  3. Exercise 3 of Lecture 1.
  4. Exercise 4 of Lecture 1. Here, it suffices if you solve a variant: Design an algorithm which performs a number of flips that is asymptotically small. For example, is it possible to sort in subproblem (a) using O(n) flips?
  5. Exercise 7 of Lecture 1, parts (a) and (b).

The homework is due in class on Tuesday, February 7.