CSE 421 Assignment #5
Winter 2005
Due: Friday, February 18, 2005.
Reading Assignment: Kleinberg and Tardos Chapter 6
Problems:
For all problems on this homework prove that your algorithm is correct
and analyze its worst-case running time.
- Kleinberg and Tardos, Section 5.10, Problem 7, page 218.
- Kleinberg and Tardos, Section 5.10, Problem 26, page 232.
- Kleinberg and Tardos, Section 6.7, Problem 4, page 267.
- Extra credit: When people type they are much more likely to
transpose two adjacent characters rather than insert, delete, or change them.
Suppose that there is a cost d< 1 per transposition, cost 1
for either an
insertion or deletion and cost eab with 1< eab<2
for typing an a instead of a b. (The likelihood of a mistyped
character depends on how far apart the characters are on the keyboard.)
Design an algorithm to compute the edit distance
between two strings under this measure and determine the sequence of
errors needed to achieve this distance. Make sure
that the transposition errors you consider do not involve the same letter
twice.