CSE 417 Assignment #2
Winter 2001

Due: Friday, January 26, 2001.

1. Skiena's text page 51, Problem 2-13. Explain your answers.

2. Skiena's text page 50, Problem 2-5.

3. Skiena's text page 78, Problem 3-6.

4. An alignment of two strings A=a₁a₂...a_n and B=b₁b₂...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.

5. 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.)

6. (Bonus) Skiena's text pages 78-79, Problem 3-7.