Homework 2 for Algorithms in Bioinformatics
- Out: Oct. 31, 2001
- Due: 1 week
- Problem 1
At the end of Lecture 3 we traced the algorithm of Ukkonen
for 'bbabbaab'. Now it's your turn to trace the algorithm for
'baabbabb'.
- Problem 2
Exercise 1.6.4 of Gusfield, page 13. Although this problem
can be solved by fundamental preprocessing, you are only allowed to
use suffix trees.
- Problem 3
In Lecture 4 we showed how to compute a longest common
subsequence of A and B. Suppose |A|=min(|A|,|B|). We gave an algorithm
for this problem using A's suffix tree and its suffix links. It is
clear that the required space is only O(|A|). Now, you are asked to
prove that the required time is indeed O(|B|).
This set of webpages is maintained by Hsueh-I Lu
Number of accesses since August 11, 2001.
FastCounter by bCentral