There are five problems in this homework. They are from Jeff Erickson's notes. For all questions, aim for polynomial running time as the first step, and later do further optimizations such as improving the running time from O(n^2) to O(n). Most of the credit will be for the first step.
  1. Exercise 3 (b) -- on shortest common supersequence -- and 3 (d) -- longest oscillating subsequence -- of Lecture 5. (10 points)
  2. Exercise 5 of Lecture 5 (on the game with Elmo). (10 points)
  3. Exercise 10 (a) and 10 (c) of Lecture 5. (10 points)
  4. Exercise 12 of Lecture 5, on determining if C is a shuffle of A and B. (10 points)
  5. Exericse 35 of Lecture 5, on the minimum number of rounds for message delivery. (10 points)

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