Algoritmer og Datastrukturer 2 (Q4, 2016)

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:

  • konstruere og analysere algoritmer ved hjælp af standard algoritmeparadigmer.
  • identificere og formulere algoritmiske problemer som graf- og streng-problemer.
  • identificere og sammenligne graf- og streng-algoritmer til løsning af algoritmiske problemer.
  • konstruere algoritmer for simple graf- og streng-problemer.

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 7. april 2016.

Studiecafé

Der afholdes dagligt studiecafé i Ada 018-020-026 for alle kurser på 1. studieår, hvor der også vil være en instruktor til stede for Algoritmer og Datastruktuer 2

Mandag+Onsdag 12.00-14.00, Tirsdag+Torsdag 14.00-16.00, Fredag 13.00-15.00

Bemanding: Mandag+Onsdag: Mathias, Tirsdag+Torsdag: Yujin, Fredag: 8/4 Yujin, 15/4 Mathias, (22/4 helligdag), 29/4 Yujin, (6/5 Kapsejlads, ingen studiecafé), 13/5 Mathias, 20/5 Yujin, 27/5 Yujin.

Spørgetime før eksamen

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

Gerth, fredag 10. juni, 14.00, INCUBA Store Auditorium
Casper (DA3), mandag 13. juni, 12.00, Nygaard 184
Benjamin (DA4), mandag 13. juni, 12.00-15.00, IT-huset, lokale 112 (5520-112, INCUBA)
Kostas (Hold 1, DA6), tirsdag 14. juni, 9.00-12.00, IT-huset, lokale 112 (5520-112, INCUBA)
Yujin (DA1), onsdag 15. juni, 9.00-12.00, Nygaard 184

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.

UgeDagForelæsningLitteraturSlidesOpgaver
14 (opgaverne antager dADS1 pensum) Opgaver 1-3, [CLRS] Problem 7.6
7/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
Quizz: Rekursionsligninger
15 11/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
14/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 18/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 pptx
pdf		 [CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
21/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
22/4 Store Bededag : Hold DA3 ingen øvelser
17 25/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
28/4 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
18 2/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)
5/5 Kristi himmelfartsdag : Hold DA4 ingen øvelser
19 9/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
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
20 16/5 2. pinsedag : Hold 2 ingen øvelser
19/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
21 23/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.
26/5 Repetition
Diskusion af eksamen		 pptx
pdf		 Opgave 7, 8 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 9, 10.
22 30/5 Ingen forelæsning

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 2016:

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