Algoritmer og Datastrukturer 2 (Forår 2009, Q4)
Meddelelser
- 28/9: Karaktererne sendt til studiekontoret.
- 23/8: Eksamensopgaverne august 2009.
- 10/8: August eksamen i dADS2: Fredag den 21-8-2009, kl. 9.00-13.00, Trøjborg, Willemoesgade 15, Aarhus N
- 6/7: Karaktererne for eksamen den 26. juni 2009 er sendt til studiekontoret.
- 26/6: Eksamensopgaverne juni 2009 og vejledende besvarelse.
- 23/6: Augusteksamen i dADS2 er den 21. august 2009
- 18/5: Eksamen: Fredag den 26-6-2009, kl. 9.00-13.00. Årskortnr. 19982269-20082119 skal i Åbogade 34, Benjaminbygningen indgang B. Årskortnr. 20082178-20085513 skal i Skøjtehallen.
- 15/5: Ugeseddel 7.
- 11/5: Ugeseddel 6.
- 4/5: ACM/ICPC programmeringskonkurrencer (slides: acm.pdf | acm.ppt)
- 30/4: Ugeseddel 5.
- 24/4: Ugeseddel 4.
- 11/4: Ifølge eksamensplanen, så er dADS2 eksamen den 26. juni 2009.
- 20/4: Ugeseddel 3.
- 6/4: Ugeseddel 2.
- 21/3: Holdlister tilføjet.
- 5/3: Kursusplan og første ugeseddel tilgængelig. Bemærk første øvelser er torsdag den 2. april.
- 22/1 2009: Bemanding og eksamensinfo tilføjet. Omlagt websiderne til nyt AU design.
- 19/11 2008: Kursussiden oprettet
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.
Øvelser og obligatoriske opgaver
- Ugeseddel 1 (2/4-15/4)
- Ugeseddel 2 (16/4-22/4)
- Ugeseddel 3 (23/4-29/4)
- Ugeseddel 4 (30/4-6/5)
- Ugeseddel 5 (7/5-13/5 + 15/5)
- Ugeseddel 6 (14/5 + 18/5-22/5)
- Ugeseddel 7 (25/5-29/5)
Forelæser
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. |