# CSE 417 Assignment #3

Winter 2000

### Due: Friday, February 11, 2000.

Read Chapter 7.
Problems from Manber's text:

- An
**alignment** of two strings
A=a_{1}a_{2}...a_{n} and
B=b_{1}b_{2}...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.
- page 249, Problem 7.5
- page 252, Problem 7.32
- page 253, Problem 7.38
- page 254, Problem 7.44
- (Bonus) page 182, Problem 6.53