There are four problems in this homework. Each is worth 10 points. The
problems are from
Jeff
Erickson's notes.
- Exercise 3 of Lecture 0.
- Exercise 3 of Lecture 1.
- 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?
- Exercise 7 of Lecture 1, parts (a) and (b).
The homework is due in class on Thursday, Februrary 6.
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.