Algoritmer og Datastrukturer 2 (Forår 2012, Q4)
Meddelelser
- 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.
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. |
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 |
|||
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. |