bild
Skolan för
elektroteknik
och datavetenskap
KTH / CSC / Kurser / DD1352 / adk09 / Schema

Schema och detaljschema i ADK, våren 2009

Här finns schemat för kursen.

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

Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2009-04-15