CS 5984 Fall 2000 Homework Assignment 4
50 Points
Due: 9/25/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 September 25, 2000.
No late homework will be accepted.
Be certain to write your solutions in COMPLETE SENTENCES.
-
[15]
Gusfield, Section 3.7, Exercise 4.
-
[15]
Gusfield, Section 3.7, Exercise 6.
-
[5]
Let P=axaxaxacaaxacaxaxaxaxacax.
Compute the Zj,
sp'j, and F'
values for P.
Report your results in a single table,
as was done in class.
-
[15]
Let S be the set of patterns containing these 16 English words:
| area |
arsenic |
bleed |
blood |
dorsal |
| earthen |
ferrous |
ladder |
marble |
mars |
| odors |
odoriferous |
roses |
rouses |
salad |
| thinker |
Build the keyword tree for S.
Also, compute the failure links for S,
and collect all failure links that do not go to the root
into a table.
Please report any problems found in these pages to:
CS5984 Class Account (algnbio@courses.cs.vt.edu)