Homework 7

Handed out: Th Nov 10 
Due: Th Nov 17 at beg. of class

1. 15.4-1 p355

2. 16.2-4 p384

3. 16.3-6 p392
You only need to give the algorithm.
No need to prove that it produces optimal ternary codes.
How do you implement your algorithm and what is its time bound.

4. 15.5-2 p363
Construct the tables as given in figure 15.8
Note that the setup is slightly more envolved than
the one given in class (where we discussed the case when
all q_i were 0)

5. Two character strings may have many common substrings.
Substrings are required to be contiguous in the original
string. For example, "photograph"
and "tomography" have several common substrings of
length one (i.e. single letters) and common substrings
"ph", "to", and "ograph" (as well as all the
substrings of "ograph"). The maximum common substring
length is 6.
   Let X=x_1 x_2 ... x_n and Y=y_1 y_2 ... y_m be two
character strings. Give an algorithm to find the maximum
common substring length for X and Y. Analyze the worst-case
running time and space requirements of your algorithm as a
function of n and m.

Note: There is a Theta(nm) dynamic programming algorithm,
and there are other Theta(nm) non-dynamic programming
algorithms. Try to find two solutions.


6. EC 15.7, p 369