Schema och detaljschema i ADK, våren 2009

SU-studenterna redovisar sista labben 20 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 vilka sidor det behandlas i kursböckena. GT=Goodrich-Tamassia, KT=Kleinberg-Tardos, Moln=Algorithms and Complexity 2007 som användes föregående kursomgångar, Sup=Supplementet Algorithms and Complexity 2009.

Period 3: algoritmer och datastrukturer
F1 19 januari: Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (GT: 3-46, 268-270, 686-688, KT/Moln: 29-56, 214-221)
F2 22 januari: Repetition av sortering och datastrukturer. (GT: 55-130, 141-151, 217-238, KT/Moln: 57-65, 209-214)
F3 26 januari: Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även länksidan.
F4 29 januari: Datastrukturer: skipplistor, praktiska datastrukturer. (GT: 429-439, Sup: 77-83, KT/Moln: 595-602)
Ö1 29 januari: Algoritmanalys.
F5 2 februari: Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F6 5 februari: Undre gränser. Korrekthetsbevis. (Sup: 17-29, KT/Moln: 535-547)
Ö2 5 februari: Datastrukturer och undre gränser. Teoriredovisning för labb 1.
F7 9 februari: Grafer: sökning, maximala flöden. (GT: 287-334, 381-397, KT/Moln: 73-107, 337-357, 367-373)
F8 12 februari: Giriga grafalgoritmer: minimala spännande träd, kortaste stigar. (GT: 339-353, 360-375, KT/Moln: 137-157)
Ö3 12 februari: Grafalgoritmer.
F9 16 februari: Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (GT: 257-273, AC: 31-48, KT/Moln: 115-177, 183-188, 221-234, 242-246, Moln: 549-566)
F10 19 februari: Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, 354-359, KT/Moln: 251-311)
Ö4 19 februari: Dekomposition och lådpackning
Labb 1 19-20 februari: Konkordans, redovisning.
F11 23 februari: Algoritmkonstruktion: mer dynamisk programmering, geometriska algoritmer. (GT: 572-586)
F12 26 februari: Algoritmkonstruktion: sortering i linjär tid, textsökning. (GT: 241-244, Sup: 1-16, Moln: 519-534)
Ö5 26 februari: Dynamisk programmering. Teoriredovisning för labb 2.
F13 2 mars: Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
Mästarprov 1, senast måndag 2 mars klockan 10.15: Algoritmer.
Ö6 5 mars: Algoritmkonstruktion.
Period 4: komplexitet
F14 16 mars: Reduktioner. (KT: 451-459, Moln: 375-383)
Ö7 19 mars: Genomgång av lösning till mästarprov 1. Reduktioner.
Labb 2 19-20 mars: Flöden och matchningar, sista redovisningstillfälle.
F15 23 mars: Introduktion till komplexitet. (GT: 592-599, KT: 463-466, Moln: 387-390)
F16 26 mars: Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
Ö8 26 mars: Oavgörbarhet. Teoriredovisning för labb 3.
F17 30 mars: Turingmaskiner och Cooks sats. (GT: 600-602)
F18 2 april: NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
Ö9 2 april: NP-fullständighetsbevis.
Labb 3 2-3 april: Ordkedjor, redovisning.
F19 16 april: NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
Ö10 16 april: NP-fullständiga problem. Teoriredovisning för labb 4.
F20 20 april: Approximationsalgoritmer. (GT: 618-626, KT: 599-630, Moln: 477-508)
Ö11 23 april: Approximationsalgoritmer.
Labb 4 23 april: NP-fullständighetsreduktioner, redovisning.
F21 27 april: Heuristiska algoritmer, komplexitetsklasser. (KT: 495-497, 531-534, 661-670, Moln: 419-421, 455-471, 509-518)
Mästarprov 2, senast 27 april klockan 10.15: Komplexitet.
F22 4 maj: Repetition.
Ö12 7 maj: Komplexitetsklasser och repetition.
Teoritenta 25 maj klockan 9-12 i sal F1

Handledarschema