# CSE 417 Assignment #2

Winter 2001

### Due: Friday, January 26, 2001.

- Skiena's text page 51, Problem 2-13. Explain your answers.
- Skiena's text page 50, Problem 2-5.
- Skiena's text page 78, Problem 3-6.
- 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 E and F of equal length that contain all the characters in
A and B respectively but also may have interspersed extra copies of
a special character * that doesn't appear in either A or B.
If you removed all of the *'s from E you would get A and if you removed
all the *'s from F you would get B.
The cost of the alignment is the number of positions where strings E and F
differ. Design an algorithm to find a minimal cost alignment given two
strings A and B -- not just its cost.
Analyze your run-time and try to use as little space as you can.
- Skiena's text page 80, Problem 3-12. (You really do need to use the
three facts that the numbers are (1) sorted, (2) integers, and (3)
there are no repeated elements.)
- (Bonus) Skiena's text pages 78-79, Problem 3-7.