Fundamental Algorithms Homework #3 Set July 9, 2009 Due July 15, 2009 1. [15 pts] [Levitin, pp. 202-203] Question 8. Hint: Some hints are given in the book. For part b, pick any point as the radiant and sort the rest of the points by the angles of the rays from the radiant to them. Be careful with ordering the points that lie on the first and last rays. 2. [10 pts] [Levitin, p. 292] Question 7. You should illustrate your answer in a style similar to Figure 8.7 on page 291. 3. [10 pts] [Levitin, p. 327] Question 2(a). You should illustrate your answer in a style similar to Figure 9.10 on page 325. 4. [10 pts] Compute the prefix function pi for the pattern abaabab and show the comparisons made by the KMP algorithm on the pattern and text ababaabaababababaabab, using a diagram similar to the one in the Word file named kmp-example-03.doc 5. [10 pts] Fragment assembly is an important step in DNA sequencing. When assembling DNA fragments, we often need to solve the following special local alignment problem. Given sequences A and B, find a suffix A' of A and a prefix B' of B such that the (global) alignment score between A' and B' is maximized. Modify the local sequence alignment algorithm discussed in class to work for this restricted local sequence alignment problem. You only need to describe how to revise the recurrence relation, table filling algorithm, and/or backtracing algorithm.