Algoritmer og Datastrukturer 2 (Q4, 2014)

Meddelelser

Formål

Deltagerne vil efter kurset have indsigt i konstruktionen af graf- og streng-algoritmer til løsning af konkrete algoritmiske problemer, og detaljeret kendskab til anvendelsen af fundamentale algoritmiske paradigmer til design af algoritmer.

Indhold

Algoritmeparadigmer: Del-og-kombiner, dynamisk programmering, grådighed. Grafalgoritmer: Grafgennemløb, sammenhængsegenskaber, topologisk sortering, udspændende træer, korteste veje, transitiv lukning. Tekstprocessering: Mønstergenkendelse, trier, tekstkomprimering, tekstsimilaritet.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15-16.00 og torsdag 12.15-14.00 i Auditorium E (1533-103).

Første forelæsning er torsdag den 3. april 2014.

DatLab

Der afholdes DatLab i Algoritmer og Datastrukturer 2 i Ada-020/026 fredag 13-15 med følgende bemanding.

DatoBemanding
Mathias4/4
Casper11/4
Jakob T.24/5
Jade2/5
Jakob T.P.9/5
Edvin23/5

Spørgetime før eksamen

De enkelte hold aftaler selv med instruktoren hvornår der skal holdes spørgetime før eksamen.

20. juni 10.00, Ada-020, Edvin (DA4)
20. juni 13.00, Ada-020, Bryan (DA1)
23. juni 10.00, Ada-020, Jakob T (DA2)
23. juni 11.00, Ada-026, Casper (DA7)
24. juni 9.00, Ada-020, Jakob TP (DA6)
24. juni 10.00, Nygaard 298, Sarfraz (Hold 1)
24. juni 13.00, Lille Auditorium (INCUBA), Gerth
25. june 11.00, 1110-214 (BiRC), Jade (Hold 2)
25. juni 12.00, Ada-018, Mathias (DA5)

Kursusplan

Nedenstående er kursusplanen for kurset. For hver foreæsning er angivet opgaverne relateret til forelæsningen, som regnes til de efterfølgende øvelser. Slides med clicker spørgsmål findes under dokumenter efter forelæsningen. Opgaverne A1-A6 er de obligatoriske afleveringsopgaver. De obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.

Uge Dag Forelæsning Litteratur Slides Opgaver
14     (opgaverne antager dADS1 pensum)   Opgaver 1-3, [CLRS] Problem 7.6
3/4 Del-og-kombiner
(under forelæsningen bevises en simplere udgave af Master Theorem'et) 		[CLRS] Kap. 2.3, 4.2-4.5, Problem 30.1.c pptx
pdf 		[CLRS] Exercises 4.2-3, 4.2-5, 4.3-2, Problem 4.1
A1: Opgave 4
15 7/4 Dynamisk programmering [CLRS] Kap. 15.1-15.3 pptx
pdf 		[CLRS] Exercises 15.1-2, 15.1-3, 15.2-1, 15.2-4, 15.2-5, 15.3-4
A2: [CLRS] Problem 15-6
10/4 Dynamisk programmering
(Hirsberger's liniære plads LCS algoritme, CACM 1975, ikke pensum)		 [CLRS] Kap. 15.4-15.5 [CLRS] Exercises 15.4-1, 15.4-2, 15.4-4, 15.4-5, (15.4-6), 15.5-3, (15.5-4), Problem (15.3), (15.4)
A3: Opgave 5
16-17 14/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 pptx
pdf 		[CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
16-22/4 Påskeferie
24/4 Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3 pptx
pdf 		[CLRS] Exercises 22.1-1, 22.1-5, 22.1-6, 22.2-1, 22.2-6, 22.2-8, 22.3-1, 22.3-2
18 28/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 pptx
pdf 		[CLRS] Exercises 22.4-2, 22.5-7
A4: [CLRS] Problem 22-3
1/5 Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24.1-24.3 pptx
pdf 		[CLRS] Exercises 24.1-3, 24.2-4, 24.3-2, 24.3-8, Problems 24-3
19 5/5 Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2 pptx
pdf 		[CLRS] Exercises 25.1-6, 25.1-9, 25.1-10, 25.2-4, 25.2-6, Problems 25-1
A5: Opgave 6 (a-c)
8/5 Graf algoritmer: Minimum udspændende træer [CLRS] Kap. 23 pptx
pdf 		[CLRS] Exercises 23.1-3, 23.1-4, 23.1-10, 23.1-11, 23.2-2, 23.2-4
20 12/5 Graf algoritmer: Maksimale strømninger, Maximale todelte parringer
Bemærk: Under forelæsningen bruges notationen fra CLRS 2. udgave, hvor f(u,v)=-f(v,u). Kapitel 26 fra udgave 2. udgave af CLRS findes under dokumenter. I 3. udgave er negativt flow erstattet med flow af størrelse 0, men dette har kompliceret fremstillingen i resten af kapitel 26 unødigt. 		[CLRS] Kap. 26.1-26.3 pptx
pdf 		[CLRS] Exercises 26.1-7, 26.2-2, 26.2-3, 26.2-4, 26.2-13, (26.3-1), (26.3-3), Problem (26-1)
A6: [CLRS] Exercise 26.2-11
15/5 Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4 pptx
pdf 		[CLRS] Exercises 32.1-2, 32.1-4, 32.2-1, 32.2-3, 32.4-7
16/5 Store Bededag: Hold DA7 ingen øvelser
21 19/5 Streng algoritmer: Suffix træer og suffix arrays [Smyth] 5.3.2, [GT] 9.2 pptx
pdf 		[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(n3)-time algorithm for finding a longest substring that is common to all three of A, B, and C.
22/5 Repetition
Diskusion af eksamen		   pptx
pdf 		7, 8 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 9, 10.
22 26/5 Ingen forelæsning
29/5 Kr. Himmelfartsdag: Hold DA5 ingen øvelser

Materiale

Introduction to Algorithms (Third Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press, 2009.

Kernen af kursusmaterialet udgøres af denne bog.

Bemærk: Til emnet maksimale strømninger bruges definitionerne fra den 2. udgave af bogen. Siderne 644-663 fra den 2. udgave findes under dokumenter.
Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.

Til forelæsningen om suffix træer gennemgås Kapitel 9.2 fra bogen, der findes under dokumenter. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.
William Smyth: Computing Patterns in Strings. Pearson Education, 2003. ISBN: 0-20139-839-7 (errata).

Til forelæsningerne om suffix arrays gennemgås Kapitel 5.3.2 fra bogen, der findes også under dokumenter. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

Eksamen

4 timers skriftlig eksamen, ekstern censur, 7 skala.

Hjælpemidler: Alle sædvanlige hjælpemidler (lærebøger, notater, lommeregner). Computer må ikke medbringes.

For at kunne indstilles til eksamen skal man have godkendt besvarelserne af 6 obligatoriske opgaver.

Pensum

Pensum til dADS 2 eksamen i foråret 2014:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Introduction to Algorithms (Third Edition), MIT Press and McGraw-Hill, 2009:
Kapitel 2.3.1-2.3.2, 4.2-4.5, 15, 16.1-16.3, 22, 23, 24.1-24.3, 24.5, 25.1-25.2, 26.1-26.3, 32.1-32.2, 32.4

Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples, John Wiley & Sons, Inc., 2002:
Kapitel 9.2

William Smyth: Computing Patterns in Strings. Pearson Education, 2003. ISBN: 0-20139-839-7 (errata).
Kapitel 5.3.2

Eksamensopgaver