Uge 21

Forelæsninger

Mandag den 21/5-2007, kl 14-16

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

Fredag den 25/5-2007, kl. 12-14

• Repetition
  Diskusion af eksamen

Øvelser

[CLRS] Exercises 25.2-4, 25.2-6, 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 14/5-2007, kl 14-16

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

Fredag den 18/5-2007, kl. 12-14

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

Øvelser

[CLRS] Exercises 24.1-3, 24.2-3, 24.2-4, 24.3-2, 24.3-6, 25.1-2, 25.1-6, 25.1-9, 25.1-10, Problems 24-1, 24-3

Obligatorisk afleveringsopgave

Opgave 21

Uge 19

Forelæsninger

Mandag den 7/5-2007, kl 14-16

• Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24.1-24.3, 24.5
  Forelæsning ved Peter Bro Miltersen
  Forelæsningen den 7. maj er flyttet til Auditorium F i Ny Munkegade

Fredag den 11/5-2007, kl. 12-14

• Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2
  Forelæsning ved Peter Bro Miltersen

Øvelser

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

Obligatorisk afleveringsopgave

Opgave 23

Uge 18

Forelæsninger

Mandag den 30/4-2007, kl 14-16

• Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5
  

Fredag den 4/5-2007, kl. 12-14

• Store Bededag - ingen forelæsning (Hold 1 aftaler med instruktoren tidspunkt for øvelser)

Øvelser

[CLRS] Exercise 15.4-5, 15.4-6, 15.5-3, 15.5-4, 16.1-3, 22.1-1, 22.1-5, 22.1-6, 22.2.-1, Problem 15.4

Obligatorisk afleveringsopgave

Opgave 18

Uge 17

Forelæsninger

Mandag den 23/4-2007, kl 14-16

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

Fredag den 274-2007, kl. 12-14

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

Øvelser

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

Obligatorisk afleveringsopgave

dADS2 eksamesopgave: August 2005, Opgave 3

Uge 16

Forelæsninger

Mandag den 16/4-2007, kl 14-16

• Dynamisk programmering [CLRS] Kap. 15 (Slides)

Fredag den 20/4-2007, kl. 12-14

• Dynamisk programmering [CLRS] Kap. 15

Øvelser

[CLRS] Exercise 4.1-1, Problem 4.1, Exercises 28.2-2, 28.2-4, 30.1-1, 30.1-2, 30.1-7

Obligatorisk afleveringsopgave

[CLRS] Problem 4.2

Uge 14-15

Forelæsninger

Mandag den 2/4-2007, kl 14-16

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

Fredag den 13/4-2007, kl. 12-14

• Del-og-kombiner: Fast Fourier Transform (FFT) [CLRS] Kap. 30.1-30.2 (ikke side 826 og 837) (Slides)

Øvelser

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

Obligatorisk afleveringsopgave

Opgave 16

---