Algoritmer og Datastrukturer 2 (Forår 2012, Q4)
Meddelelser
- 18/9: Karaktererne sendt til studiekontoret
- 24/8: Eksamensopgaverne august 2012 og vejledende besvarelse
- 4/8: Spørgetime (reeksamen) tirsdag den 21. august 13.00 i Ada-018
- 13/7: Karaktererne sendt til studiekontoret
- 23/6: Vejledende besvarelse juni 2012
- 22/6: Eksamensopgaverne juni 2012
- 27/3: Der afholdes DatLab i Ada-018 hver fredag 13. april-18. maj (dog ikke Store Bededag den 4. maj)
- 22/3 2012: Email fra Jesper om deltagelse i IDI programmerings konkurrence
- 6/12 2011: 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 (29/3-11/4)
- Ugeseddel 2 (12/4-18/4)
- Ugeseddel 3 (19/4-25/4)
- Ugeseddel 4 (26/4-2/5)
- Ugeseddel 5 (3/5-9/5 + 11/5)
- Ugeseddel 6 (10/5 + 14/5-18/5)
- Ugeseddel 7 (21/5-25/5)
Den obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.
Forelæser
Forelæsninger
Mandag 14.15-16.00 og torsdag 12.15-14.00.
Første forelæsning er torsdag den 29. marts 2012.
Spørgetime før eksamen
De enkelte hold aftaler selv med instruktoren hvornår der skal holdes spørgetime før eksamen.
17. juni 12.00, Ada 020, Torben og Andreas (Hold 1 og Hold 2)
20. juni 13.00, Ada 020, Mathias (DA1)
12. juni 14.00, Ada 018, Casper (DA2)
20. juni 10.00, IT-huset 112, Jana (DA4)
17. juni 15.00, Stibitz, Mathies (DA5)
21. juni 13.00, Nygaard 395, Barbora (DA6)
Kursusplan
Bemærk: Slides med clicker spørgsmål findes under dokumenter efter forelæsningen.
| Uge | Dag | Forelæsning | Litteratur | Slides |
|---|---|---|---|---|
| 13 | 29/3 | 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 |
| 14-15 | 2/4 | Dynamisk programmering | [CLRS] Kap. 15.1-15.3 |
dynamicprogramming.pptx dynamicprogramming.pdf |
| 4-10/4 | Påskeferie | |||
| 12/4 | Dynamisk programmering (Hirsberger's liniære plads LCS algoritme, CACM 1975, ikke pensum) |
[CLRS] Kap. 15.4-15.5 |
dynamicprogramming.pptx dynamicprogramming.pdf |
|
| 16 | 16/4 | Grådige algoritmer | [CLRS] Kap. 16.1-16.3 |
greedy.ppt greedy.pdf |
| 19/4 | Graf algoritmer: Repræsentation, BFS, DFS | [CLRS] Kap. 22.1-22.3 |
graphs.ppt graphs.pdf |
|
| 17 | 23/4 | Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter | [CLRS] Kap. 22.4-22.5 |
topologicalsort.ppt topologicalsort.pdf |
| 26/4 | Graf algoritmer: Korteste veje (SSSP) | [CLRS] Kap. 24.1-24.3 |
shortestpaths-sssp.ppt shortestpaths-sssp.pdf |
|
| 18 | 30/4 | Graf algoritmer: Korteste veje (APSP) | [CLRS] Kap. 25.1-25.2 |
shortestpaths-apsp.ppt shortestpaths-apsp.pdf |
| 3/5 | Graf algoritmer: Minimum udspændende træer | [CLRS] Kap. 23 |
mst.pptx mst.pdf |
|
| 4/4 | Store Bededag | |||
| 19 | 7/5 | Graf algoritmer: Maksimale strømninger, Maximale todelte parringer | [CLRS] Kap. 26.1-26.3 |
flow.pptx flow.pdf |
| 10/5 | Streng algoritmer: Mønstergenkendelse | [CLRS] Kap. 32.1-32.2, 32.4 |
patternmatching.ppt patternmatching.pdf |
|
| 20 | 14/5 | Streng algoritmer: Suffix træer og suffix arrays | [Smyth] 5.3.2, [GT] 9.2 |
tries.ppt tries.pdf |
| 17/5 | Kr. Himmelfartsdag | |||
| 21 | 21/5 | Ingen forelæsning | ||
| 24/5 | Repetition Diskusion af eksamen |
repetition.pptx | ||
Materiale
|
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. |
|
Michael T. Goodrich and Roberto Tamassia: Algorithm design -
Foundations, Analysis and Internet Examples. John Wiley & Sons,
Inc. ISBN: 0-471-38365-1.
Til forelæsningen om suffix træer gennemgås Kapitel 9.2 fra bogen, der findes under dokumenter. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset. |
|
William Smyth: Computing Patterns in Strings.
Pearson Education, 2003.
ISBN: 0-20139-839-7
(errata).
Til forelæsningerne om suffix arrays gennemgås Kapitel 5.3.2 fra bogen, der findes også under dokumenter. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset. |