CSE 417 Assignment #3
Winter 2000

Due: Friday, February 11, 2000.

Read Chapter 7. Problems from Manber's text:

1. An alignment of two strings A=a₁a₂...a_n and B=b₁b₂...b_m is a pair of strings C and D of equal length that each have an extra kind of character * that doesn't appear in either A or B. If you removed all of the *'s from C you would get A and if you removed all the *'s from D you would get B. The cost of the alignment is the number of positions where strings C and D differ. Design an algorithm to find a minimal cost alignment of A and B -- not just its cost. Try to use as little space as you can.

2. page 249, Problem 7.5

3. page 252, Problem 7.32

4. page 253, Problem 7.38

5. page 254, Problem 7.44

6. (Bonus) page 182, Problem 6.53