Uge 21

Forelæsninger

Mandag den 22/5-2006, kl 14-16

• Repetition ved gamle eksamensopgaver. Gennemgang af eksamenspensum.

Fredag den 26/5-2006:

• Ingen forelæsning

Øvelser

[CLRS] Exercises 32.1-2, 32.1-4, 32.2-1, 32.2-3, 32.4-5
[GT] R-9.10: Draw the compact representation of the suffix trie for the string "minimize minime".
[GT] C-9.10: Give an efficient algorithm for deleting a string from a compressed trie and analyze its running time.
[GT] C-9.13: Describe an efficient algorithm to find the longest palindrome that is a suffix of a string T of length n. Recall that a palindrome is a string that is equal to its reversal. What is the running time of your method?
[GT] C-9.18: Let A, B, and C be three length-n character strings taken over the same constant sized alphabet. Design and O(n³)-time algorithm for finding a longest substring that is common to all three of A, B, and C.

Ekstra opgaver: Opgave 25, 26 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 27, 28 (gamle dADS eksamensopgaver).