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).

Uge 20

Forelæsninger

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

• Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4

Fredag den 19/5-2006, kl. 12-14

• Streng algoritmer: Suffix træer og suffix arrays [GT] 9.2 [Smyth] 5.3.2

Øvelser

[CLRS] Problems 24-1, 24-3, Exercises 25.1-2, 25.1-6, 25.1-9, 25.1-10, 25.2-4, 25.2-6, 25.2-8

Obligatorisk afleveringsopgave

Opgave 23

Uge 19

Forelæsninger

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

• Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2
  

Fredag den 12/5-2006, kl. 12-14

• Ingen forelæsning - Store Bededag

Øvelser

[CLRS] Exercises 23.1-3, 23.1-4, 23.1-11, 23.2-2, 23.2-4, 24.1-3, 24.2-3, 24.2-4, 24.3-2, 24.3-6

Obligatorisk afleveringsopgave

Opgave 21

Uge 18

Forelæsninger

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

• Graf algoritmer: Minimum udspændende træer [CLRS] Kap. 23
  

Fredag den 5/5-2006, kl. 12-14

• Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24.1-24.3
  

Øvelser

[CLRS] Exercise 22.1-1, 22.1-5, 22.1-6, 22.2.-1, 22.2-5, 22.2-7, 22.3-1, 22.3-8, 22.4-2, 22.4-3, Problem 22.3

Obligatorisk afleveringsopgave

Opgave 18

Uge 17

Forelæsninger

Mandag den 24/4-2006, kl 14-16

• Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3
  

Fredag den 28/4-2006, kl. 12-14

• Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 (ikke siderne 555-556)
  

Øvelser

[CLRS] Exercises 15.1-1, 15.1-4, 15.1-5, 15.5-3, 15.5-4, Problems 15.1, 15.2, 15.4

Obligatorisk afleveringsopgave

dADS2 eksamesopgave: August 2005, Opgave 3

Uge 15-16

Forelæsninger

Mandag den 10/4-2006, kl 14-16

• Dynamisk programmering [CLRS] Kap. 15.1, 15.5
  

Fredag den 21/4-2006, kl. 12-14

• Grådige algoritmer [CLRS] Kap. 16.1-16.3
  

Øvelser

[CLRS] Exercises 15.2-1, 15.2-4, 15.3-2, 15.3-5, 15.4-1, 15.4-2, 15.4-4, 15.4-5, 15.4-6

Obligatorisk afleveringsopgave

[CLRS] Problem 15.6

Uge 14

Forelæsninger

Mandag den 3/4-2006, kl 14-16

• Del-og-kombiner [CLRS] Kap. 2.3.1-2.3.2, 4.1-4.3, 28.2, Problem 30.1 (under forelæsningen bevises en simplere udgave af Master Theorem'et)

Fredag den 7/4-2006, kl. 12-14

• Dynamisk programmering [CLRS] Kap. 15.2-15.4
  

Øvelser

Opgaver 1-3 til uge 14
[CLRS] Problem 7.6

Obligatorisk afleveringsopgave

Opgave 16

---