Schema och detaljschema i ADK, våren 2008

SU-studenterna redovisar sista labben 27 mars. Labbtiderna därefter är enbart för teknologerna.

Detaljschema

Kursen består av 22 föreläsningar och 12 övningar. Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna och övningarna. För varje föreläsning anges vilket avsnitt i kursboken som behandlas.

Period 3: algoritmer och datastrukturer
F1 21 januari: Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (s 29-56, 214-221)
F2 24 januari: Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson.
F3 28 januari: Repetition av sortering och datastrukturer. (s 57-65, 209-214)
F4 31 januari: Datastrukturer: skipplistor, praktiska datastrukturer. (s 595-602)
Ö1 31 januari: Algoritmanalys.
F5 4 februari: Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F6 7 februari: Undre gränser. Korrekthetsbevis. (s 535-547)
Ö2 7 februari: Datastrukturer och undre gränser. Teoriredovisning för labb 1.
F7 11 februari: Grafer: sökning, maximala flöden. (s 73-107, 337-357, 367-373)
F8 14 februari: Giriga grafalgoritmer: minimala spännande träd, kortaste stigar. (s 137-157)
Ö3 14 februari: Grafalgoritmer.
F9 18 februari: Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (s 115-177, 183-188, 221-234, 242-246, 549-566)
F10 21 februari: Algoritmkonstruktion: dynamisk programmering. (s 251-311)
Ö4 21 februari: Dekomposition och lådpackning
Labb 1 21-22 februari: Konkordans, redovisning.
F11 25 februari: Algoritmkonstruktion: mer dynamisk programmering, geometriska algoritmer.
F12 28 februari: Algoritmkonstruktion: sortering i linjär tid, textsökning. (s 519-534)
Ö5 28 februari: Dynamisk programmering. Teoriredovisning för labb 2.
F13 3 mars: Algoritmkonstruktion: polynomberäkningar och FFT. (s 234-242)
Mästarprov 1, senast måndag 3 mars klockan 10.15: Algoritmer.
Ö6 5 mars: Algoritmkonstruktion.
Period 4: komplexitet
F14 27 mars: Reduktioner. (s 375-383)
Ö7 27 mars: Genomgång av lösning till mästarprov 1. Reduktioner.
Labb 2 27-28 mars: Flöden och matchningar, sista redovisningstillfälle.
F15 31 mars: Introduktion till komplexitet. (s 387-390)
F16 3 april: Oavgörbarhet. (s 567-590)
Ö8 3 april: Oavgörbarhet. Teoriredovisning för labb 3.
F17 7 april: Turingmaskiner och Cooks sats.
F18 10 april: NP-fullständighetsbevis. (s 390-419)
Ö9 10 april: NP-fullständighetsbevis.
Labb 3 10-11 april: Ordkedjor, redovisning.
F19 14 april: NP-fullständighetsreduktioner. (s 383-387, 421-429)
Ö10 17 april: NP-fullständiga problem. Teoriredovisning för labb 4.
F20 21 april: Approximationsalgoritmer. (s 477-508)
Ö11 24 april: Approximationsalgoritmer.
Labb 4 24-25 april: NP-fullständighetsreduktioner, redovisning.
F21 28 april: Heuristiska algoritmer, komplexitetsklasser. (s 509-518, 419-421, 455-474)
Mästarprov 2, senast 28 april klockan 10.15: Komplexitet.
F22 5 maj: Repetition.
Ö12 8 maj: Komplexitetsklasser och repetition.
Teoritenta 13 maj klockan 9-12 i sal F1

Handledarschema