Algoritmer og Datastrukturer 2 (Q4, 2017)

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 30. marts 2017.

Studiecafé

Der afholdes dagligt studiecafé i Javahulen, hvor der vil være en instruktor til stede for Algoritmer og Datastrukturer 2:

Mandag 12-14 (Sabine), Tirsdag 14-16 (Kostas), Onsdag 12-14 (Andreas), Torsdag 14-16 (Rasmus), Fredag 13-15 (Alexander).

Spørgetime før eksamen

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

Kostas, mandag 19. juni, 9.00, Nygaard 184
Rasmus, mandag 19. juni, 10.00, Ada 018
Casper, mandag 19. juni, 12.00, Nygaard 192
Gerth, tirsdag 20. juni, 13.00, INCUBA Store Auditorium
Sabine, onsdag 21. juni, 9.00, Nygaard 184
Alexander, onsdag 21. juni, 14.00, Nygaard 184
Andreas, torsdag 22. juni, 9.00, Nygaard 184

Kursusbelastning

Forelæsning 7 uger á 2 x 2 timer : 28 timer
Teoretiske øvelser 7 uger á 3 timer : 21 timer
StudieCafé 7 uger á 2 time : 14 timer
Udarbejdelse af 6 afleveringsopgaver á 2 timer : 12 timer
Forberedelse til forelæsning 1 time per 2 timers forelæsning : 14 timer
Forberedelse til teoretiske øvelser 7 uger á 2 timer : 14 timer
Foreberedelse til eksamen 5 dage á 8 timer : 40 timer
Eksamen : 4 timer
I alt: 147 timer

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 Materiale (begrænset adgang) efter forelæsningen. Opgaverne A1-A6 er de seks obligatoriske ugeafleveringsopgaver. De obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.

UgeDagForelæsningLitteraturSlides & VideoOpgaver
13 (opgaverne antager dADS1 pensum) Opgaver 1-3
[CLRS] Problem 7.6
30/3 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
Video
1 2 		[CLRS] Exercises 4.2-3, 4.2-5, 4.3-2, Problem 4.1
A1: Opgave 4
Quizz: Rekursionsligninger
14 3/4 Dynamisk programmering [CLRS] Kap. 15.1-15.3 pptx
pdf
Video
1 2 		[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
6/4 Dynamisk programmering
(Hirsberger's liniære plads LCS algoritme, CACM 1975, ikke pensum)		 [CLRS] Kap. 15.4-15.5 pptx
pdf
Video
1 2 		[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
15-16 10/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 pptx
pdf
Video
1 2 		[CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
12/4-18/4 Påskeferie - Ingen undervisning
20/4 Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3 pptx
pdf
Video
1 2		 [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
17 24/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 pptx
pdf
Video
1 2		 [CLRS] Exercises 22.4-2, 22.5-7
A4: [CLRS] Problem 22-3
27/4 Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24.1-24.3 pptx
pdf
Video
1 2 3		 [CLRS] Exercises 24.1-3, 24.2-4, 24.3-2, 24.3-8, Problems 24-3
18 1/5 Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2 pptx
pdf
Video
1		 [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)
4/5 Graf algoritmer: Minimum udspændende træer
(denne forelæsning forventes at tage ca. 1 time) 		[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
19 8/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
11/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
12/5 St. Bededag : Hold DA5 ingen øvelser
20 15/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.
18/5 Repetition
Diskusion af eksamen		 pptx
pdf		 Opgave 7, 8 ([GT] Kapitel 7.2.1 = [CLRS] Kapitel 25.2), 9, 10.
21 22/5 Ingen forelæsning
25/5 Kristi himmelfartsdag : Hold DA4 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 Materiale (begrænset adgang).
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 Materiale (begrænset adgang). 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 Materiale (begrænset adgang). 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 2017:

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

Karakterhistorik

Karaterfordelingen 2012-2016.

Eksamensopgaver