Algoritmer og Datastrukturer 2 (Forår 2009, 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

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15-16.00 og torsdag 12.15-14.00 i Store Auditorium (IT Huset).

Kursusplan

Uge Dag Forelæsning Litteratur Slides
14 2/4 Del-og-kombiner
(under forelæsningen bevises en simplere udgave af Master Theorem'et)
[CLRS] Kap. 2.3.1-2.3.2, 4.1-4.3, 28.2, Problem 30.1.c divide.pptx
divide.pdf
15-16 6/4 Dynamisk programmering [CLRS] Kap. 15.1-15.3 dynamicprogramming.ppt
dynamicprogramming.pdf
8/4-14/4 Påskeferie: Ingen øvelser    
16/4 Dynamisk programmering [CLRS] Kap. 15.4-15.5 dynamicprogramming.ppt
dynamicprogramming.pdf
17 20/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3 greedy.ppt
greedy.pdf
23/4 Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3 graphs.ppt
graphs.pdf
18 27/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5 topologicalsort.ppt
topologicalsort.pdf
30/4 Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24.1-24.3, 24.5 shortestpaths.ppt
shortestpaths.pdf
19 4/5 Graf algoritmer: Korteste veje (APSP)
ACM/ICPC programmeringskonkurrencer (slides: acm.pdf | acm.ppt)
[CLRS] Kap. 25.1-25.2 shortestpaths.ppt
shortestpaths.pdf
7/5 Graf algoritmer: Minimum udspændende træer [CLRS] Kap. 23 mst.pptx
mst.pdf
8/5 Store Bededag: Hold 1 og Dat 5 ingen øvelser    
20 11/5 Graf algoritmer: Maksimale strømninger [CLRS] Kap. 26.1-26.2 flow.pptx
flow.pdf
14/5 Graf algoritmer: Maximale todelte parringer [CLRS] Kap. 26.3 flow.pptx
flow.pdf
21 18/5 Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4 patternmatching.ppt
patternmatching.pdf
21/5 Kr. Himmelfartsdag: DA2 og DA4 ingen øvelser    
22 25/5 Streng algoritmer: Suffix træer og suffix arrays [Smyth] 5.3.2, [GT] 9.2 tries.ppt
tries.pdf
28/5 Repetition
Diskusion af eksamen
Slut 4. kvarter
   

Materiale


(stort billede)
Introduction to Algorithms (Second Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press and McGraw-Hill, 2001.

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. 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. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.