Algoritmer og Datastrukturer 2 (Q4, 2015)

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 9. april 2015.

Spørgetime før eksamen

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

Gerth, mandag d. 15 juni, 13:00, Peter Bøgh Andersen Auditoriet (Nygaard)
Kostas (DA3), tirsdag d. 16 juni, 11:00, Ada-018
Mathias (DA1), tirsdag d. 16. juni, 12:15, Ada-026
Bryan (DA5,DA7), tirsdag d. 16 juni, 13:00, Incuba 5523-129
Casper (Hold 1), onsdag d. 17 juni, 12:00, Ada-018
Ingo (DA2,DA6), onsdag d. 17 juni, 13:00, Incuba 5523-129

DatLab

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

DatoBemanding
10/4 Casper
17/4 Ingo
24/4 Aflyst (kapsejlads)
1/5 Aflyst (Store Bededag)
8/5 Mathias
15/5 Bryan
22/5 Kostas
29/5 Ingen dADS2 DatLab

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
15 (opgaverne antager dADS1 pensum) Opgaver 1-3, [CLRS] Problem 7.6
9/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 13/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
16/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 20/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 pptx
pdf		 [CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
23/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 27/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
30/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
1/5 Store Bededag : Hold DA5 ingen øvelser
19 4/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)
7/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 11/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
14/5 Kristi himmelfartsdag : Hold DA7 ingen øvelser
21 18/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/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 25/5 2. pinsedag : Hold DA2 ingen øvelser
28/5 Repetition
Diskusion af eksamen		 pptx
pdf		 Opgave 7, 8 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 9, 10.
23 1/6 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 2015:

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