Algoritmer og Datastrukturer 2 (Forår 2010, Q4)

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

Lektiecafé

Fra og med onsdag den 21. april tilbydes der lektiecafé i dADS2 to gange om ugen:

Forelæser

Gerth Stølting Brodal

Forelæsninger

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

Første forelæsning er torsdag den 8. april 2010.

Kursusplan

Uge Dag Forelæsning Litteratur Slides
14 8/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
(Bemærk at [CLRS, Ed. 3] Kap. 4.2-4.5 = [CLRS, Ed. 2] Kap. 4.1-4.3 + 28.2)
divide.pptx
divide.pdf
15 12/4 Dynamisk programmering [CLRS] Kap. 15.1-15.3
(Bemærk at i [CLRS, Ed. 2] brugte Kap. 15.1 et andet eksempel)
dynamicprogramming.ppt
dynamicprogramming.pdf
15/4 Dynamisk programmering [CLRS] Kap. 15.4-15.5 dynamicprogramming.ppt
dynamicprogramming.pdf
16 19/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 greedy.ppt
greedy.pdf
22/4 Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3 graphs.ppt
graphs.pdf
17 26/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 topologicalsort.ppt
topologicalsort.pdf
29/4 Graf algoritmer: Korteste veje (SSSP)
(Grundet kapsejladsen er der kun forelæsning 12:15-13:00)
[CLRS] Kap. 24.1-24.3, 24.5 shortestpaths.ppt
shortestpaths.pdf
30/4 Store Bededag: Hold IT og DA4 ingen øvelser
18 3/5 Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2 shortestpaths.ppt
shortestpaths.pdf
6/5 Graf algoritmer: Minimum udspændende træer [CLRS] Kap. 23 mst.pptx
mst.pdf
19 10/5 Graf algoritmer: Maksimale strømninger [CLRS] Kap. 26.1-26.2 flow.pptx
flow.pdf
13/5 Kr. Himmelfartsdag: Hold 1 ingen øvelser
20 17/5 Graf algoritmer: Maximale todelte parringer [CLRS] Kap. 26.3 flow.pptx
flow.pdf
20/5 Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4 patternmatching.ppt
patternmatching.pdf
21 24/5 2. Pinsedag: DA1 og DA2 ingen øvelser
27/5 Streng algoritmer: Suffix træer og suffix arrays [Smyth] 5.3.2, [GT] 9.2 tries.ppt
tries.pdf
22 31/5 Repetition
Diskusion af eksamen
Slut 4. kvarter
   

Materiale


stort billede
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.

stort billede
Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.

Til forelæsningerne om suffix træer udleveres der Kapitel 9.2 fra bogen (linket kræver lovlig login ved Datalogisk Institut). De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

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

Til forelæsningerne om suffix arrays udleveres Kapitel 5.3.2 fra bogen (linket kræver lovlig login ved Datalogisk Institut). De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.