Algoritmer og Datastrukturer 2 (Q4, 2013)

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:

Øvelser og obligatoriske opgaver

Den obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.

DatLab

Der afholdes DatLab i Algoritmer og Datastrukturer 2 om fredagen 13-15 i Babbage-0 med følgende bemanding: 12/4 Bryan, 19/4 Jungwoo, 3/5 Jesper, 10/5 Jacob, 17/5 Thorbjørn, 24/5 Lauge.

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15-16.00 og torsdag 12.15-14.00 i Auditorium E.

Første forelæsning er torsdag den 11. april 2013.

Spørgetime før eksamen

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

19. juni 14.00, Incuba 112, Tore (DA2)
20. juni 10.00, Ada-18, Jungwoo (DA4)
20. juni 11.00, Ada-20, Jacob (DA3)
20. juni 14.00, Ada-20, Bryan (DA7)
21. juni 13.00, Ada-018, Lauge (DA5)
21. juni 10.15, Ada-020, Thorbjørn (DA1)
22. juni 10.00, Ada-026, Jesper (Hold 1)
22. juni 12.00, Ada-026, Andreas (DA6)

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.

Uge Dag Forelæsning Litteratur Slides Opgaver
15     (opgaverne antager dADS1 pensum)   Opgaver 1-3, [CLRS] Problem 7.6
11/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
16 15/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
18/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
17 22/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 pptx
pdf
[CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
25/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
26/4 Store Bededag
18 29/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 ppt
pdf
[CLRS] Exercises 22.4-2, 22.5-7
A4: [CLRS] Problem 22.3
2/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 6/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)
9/5 Kr. Himmelfartsdag
20 13/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
16/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
21 20/5 2. pinsedag
23/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
22 27/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.
30/5 Ingen forelæsning
Michael E. Caspersen har inviteret alle til test i programmeringskompetencer - se datalogi's facebook side for mere info.
23 3/6 Repetition
Diskusion af eksamen
  pptx
pdf
7, 8 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 9, 10.

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 2013 er:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Introduction to Algorithms (Third Edition), MIT Press and McGraw-Hill, 2001:
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