Algoritmer og Datastrukturer 2 (Forår 2010, Q4)
Meddelelser
- 16/9: Karaktererne sendt til studiekontoret.
- 6/8: Reeksamen er fredag den 20. august.
- 9/7: Karaktererne sendt til studiekontoret.
- 29/6: Vejledende besvarelse til eksamensopgaverne juni 2010.
- 25/6: Eksamensopgaverne juni 2010.
- 5/5: Ugeseddel 6 og Ugeseddel 7.
- 3/5: Ifølge eksamensplanen er dADS2 eksamen den 25. juni 2010.
- 2/5: Ugeseddel 5.
- 26/4: ADVARSEL !!! Fra søndag 25/4 19.30 til mandag 26/4 12.00 har der været en virus med ondsindet JavaScript på dADS2 hjemmesiden. Virusen skulle nu være fjernet.
- 21/4: Foreløbig eksamensdato er fredag 25. juni 2010.
- 21/4: Ugeseddel 4.
- 20/4: Inivitation, Karina's Kaffestue, 28/4.
- 19/4: NYHED: lektiecafé mandag og onsdag 9.15-11.00 i IT Huset.
- 19/4: Ugeseddel 3.
- 12/4: Ugeseddel 2.
- 8/4: Invitation, Bachelor-orientering Datalogi, 16. april.
- 25/3 2010: Ugeseddel 1.
- 18/10 2009: 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 (8/4-14/4)
- Ugeseddel 2 (15/4-21/4)
- Ugeseddel 3 (22/4-28/4)
- Ugeseddel 4 (29/4-5/5 + 7/5)
- Ugeseddel 5 (6/5 + 10/5-14/5)
- Ugeseddel 6 (17/5-21/5)
- Ugeseddel 7 (25/5-31/5)
Lektiecafé
Fra og med onsdag den 21. april tilbydes der lektiecafé i dADS2 to gange om ugen:
- Mandag 9.15-11.00 IT-huset lokale 129 + 131
- Onsdag 9.15-11.00 IT-huset lokale 121 + 129
Forelæser
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. |