Homework 3

CS 482 - Spring 2007

Due: Wednesday, Feb 21

Note (added Feb 15): This assignment was altered somewhat from the original posting on Feb 14.  The original posting was a bit rushed because Cornell had just decided to close for the day.  One problem was removed and one problem was moved from Part B to Part C.  Also, a couple of hints were added.

Note: Please include your Cornell NetID on your each part of your homework.

Another Note: Our first prelim takes place on Thursday, Feb 22, at 7:30pm.  It won't be possible to grade and return this assignment in time for the prelim, but the sample solutions for this assignment will be made available online soon after the homework is collected.

Part A

String R is a common subsequence for strings S and T if the characters of R appear in order, but not necessarily contiguously, in both S and T.  For example, given strings ALGORITHM and GREAT, the string GRT is a common subsequence.

String R is a common supersequence for strings S and T if the characters of S and the characters of T appear in order, but not necessarily contiguously in R.  Here's a very simple common supersequence for ALGORITHM and GREAT: GREATALGORITHM.  Here's a shorter string that is also a common supersequence: ALGOREAITHM.

  1. [LCS] Give an algorithm for finding the longest common subsequence for two strings.  Your algorithm should run in time O(mn) where m and n are the lengths of the two input strings.
     
  2. [SCS] Give an algorithm for finding the shortest common supersequence for two strings.  Your algorithm should run in time O(mn) where m and n are the lengths of the two input strings.
     
  3. [Sums] Show that the length of the longest common subsequence plus the length of the shortest common supersequence is exactly equal to the sum of the lengths of the two input strings.  In more mathematical notation, |lcs(S,T)| + |scs(S,T)| = |S| + |T|.  There is a simple proof that does not involve induction.

Part B

[Phone Tree] Do Problem 16 in Chapter 6 of the text. [Hint: There is a Divide & Conquer algorithm that is relatively easy, but it doesn't achieve the optimum runtime.]
 

Part C

  1. [Sparse Cell Phones] Do Problem 5 in Chapter 4 of the text.
     
  2. [Bottlenecks] Do Problem 9 in Chapter 4 of the text. [Hint: The Cycle Property (p. 147 in text) might be useful.]