CS 5984 Fall 2000 Homework Assignment 6

50 Points
Due: 10/9/00 at 5:00PM

The point value of each problem is shown in square brackets [ ]. Your solutions must be prepared with LaTeX or other word processing system and submitted as a stapled printout to a box outside the instructor's office (McBryde 638). This homework is due at 5:00PM on October 9, 2000. No late homework will be accepted. Be certain to write your solutions in COMPLETE SENTENCES.

  1. [25] Let P={ACCTC,CTGCTA,TCCTCGTA,TGCTATCCTC}. Build a generalized suffix tree for P. List all suffix links in a table or draw them in the tree.

    Explain how you can use your suffix tree to find every occurrence of string CTC in strings in P. What occurrences did you find?

    Explain how you can use your suffix tree to find the longest common substring of TCCTCGTA and TGCTATCCTC. What longest common substring did you find?

  2. [25] Gusfield, Section 7.20, Exercise 1.

Please report any problems found in these pages to:

CS5984 Class Account (algnbio@courses.cs.vt.edu)