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.
- [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.
- [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.
- [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
- [Sparse Cell Phones] Do Problem 5 in Chapter 4 of the text.
- [Bottlenecks] Do Problem 9 in Chapter 4 of the text. [Hint: The Cycle
Property (p. 147 in text) might be useful.]