Algoritmer og Datastrukturer 2 (Forår 2011, Q4)
Meddelelser
- 5/9: Karaktererne sendt til studiekontoret
- 20/8: Vejledende besvarelse august 2011
- 12/8: Eksamensopgaverne august 2011
- 28/7: Endelige dato for reeksamen: 12. august
- 8/7: Karaktererne sendt til studiekontoret
- 5/7: Tid og sted for reeksamen i august
- 24/6: Eksamensopgaverne juni 2011 og vejledende besvarelse
- 31/5 2011: Tid og sted for spørgetimer i forbindelse med eksamen
- 25/5: Der er ingen forelæsning torsdag den 26. maj
- 10/5: Fredag lecture med Andrew Yao (Turing Award 2000), fredag 13. maj 2011, 14:15-15:15, Store Auditorium
- 15/4: Slide om bachelor & kandidat orienteringer
- 21/3: DatLab hver fredag 13.00-15.00 i Q4 fra den 8. april
- 15/3 2011: Ugesedler 1-7
- 22/11: Eksamensdato, 24. juni 2011
- 11/10 2010: 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 (1/4-7/4)
- Ugeseddel 2 (8/4-14/4)
- Ugeseddel 3 (15/4-28/4)
- Ugeseddel 4 (29/4-5/5)
- Ugeseddel 5 (6/5-12/5)
- Ugeseddel 6 (13/5-19/5)
- Ugeseddel 7 (23/5-27/5)
Den obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.
Øvelser starter fredag den 1. april 2011 (hold DA1).
Forelæser
Forelæsninger
Mandag 14.15-16.00 og torsdag 12.15-14.00. Store Auditorium (IT Huset).
Spørgetime før eksamen
De enkelte hold aftaler selv med instruktoren hvornår der skal holdes spørgetime før eksamen.
20. juni 10.00, Shannon-159, Freek (DA4)
21. juni 10.00, IT-huset, lokale 129 (DA5).
22. juni 10.15, Shannon-159, Magnus (Hold 1)
22. juni 12.00, IT-huset, lokale 129, Jana (DA1)
Kursusplan
Bemærk: Slides med clicker spørgsmål findes under dokumenter efter forelæsningen.
| Uge | Dag | Forelæsning | Litteratur | Slides |
|---|---|---|---|---|
| 14 | 4/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 |
divide.pptx divide.pdf |
| 7/4 | Dynamisk programmering | [CLRS] Kap. 15.1-15.3 |
dynamicprogramming.pptx dynamicprogramming.pdf |
|
| 15 | 11/4 | Dynamisk programmering5 (Hirsberger's liniære plads LCS algoritme, CACM 1975, ikke pensum) |
[CLRS] Kap. 15.4-15.5 |
dynamicprogramming.pptx dynamicprogramming.pdf |
| 14/4 | Grådige algoritmer | [CLRS] Kap. 16.1-16.3 |
greedy.ppt greedy.pdf |
|
| 16-17 | 18/4 | Graf algoritmer: Repræsentation, BFS, DFS | [CLRS] Kap. 22.1-22.3 |
graphs.ppt graphs.pdf |
| 20-26/4 | Påskeferie | |||
| 28/4 | Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter | [CLRS] Kap. 22.4-22.5 |
topologicalsort.ppt topologicalsort.pdf |
|
| 18 | 2/5 | Graf algoritmer: Korteste veje (SSSP) | [CLRS] Kap. 24.1-24.3 |
shortestpaths-sssp.ppt shortestpaths-sssp.pdf |
| 5/5 | Graf algoritmer: Korteste veje (APSP) | [CLRS] Kap. 25.1-25.2 |
shortestpaths-apsp.ppt shortestpaths-apsp.pdf |
|
| 19 | 9/5 | Graf algoritmer: Minimum udspændende træer | [CLRS] Kap. 23 |
mst.pptx mst.pdf |
| 12/5 | Graf algoritmer: Maksimale strømninger, Maximale todelte parringer | [CLRS] Kap. 26.1-26.3 |
flow.pptx flow.pdf |
|
| 20 | 16/5 | Streng algoritmer: Mønstergenkendelse | [CLRS] Kap. 32.1-32.2, 32.4 |
patternmatching.ppt patternmatching.pdf |
| 19/5 | Streng algoritmer: Suffix træer og suffix arrays | [Smyth] 5.3.2, [GT] 9.2 |
tries.ppt tries.pdf |
|
| 20/5 | Store Bededag | |||
| 21 | 23/5 | Repetition Diskusion af eksamen |
||
| 26/5 | Ingen forelæsning | |||
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 (findes også under dokumenter). 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 (findes også under dokumenter). De øvrige kapitler i bogen vil ikke blive gennemgået i kurset. |