bild
Skolan för
elektroteknik
och datavetenskap

Schema och detaljschema i ADK, våren 2010

Här finns schemat för kursen.

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

Detaljschema

Kursen består av 31 föreläsningar och 12 övningar. Alla föreläsningar utom tre är entimmesföreläsningar. 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 18 januari (2 timmar)
Introduktion till kursen. Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även länksidan.
F2 21 januari (2 timmar)
Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. Repetition av sortering (merge sort). (GT: 3-46, 217-238, 268-270, 686-688, KT/Moln: 29-56, 209-221)
F3 25 januari
Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (GT: 55-130, 141-151, 429-438, KT/Moln: 57-65)
F4 28 januari
Datastrukturer: latmanshashning, skipplistor. (Sup: 77-83, Moln: 595-602)
Ö1 28 januari
Algoritmanalys.
F5 29 januari OBS! kl 11.00-11.45
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F6 1 februari
Undre gränser. (Sup: 17-29, Moln: 535-547)
F7 4 februari
Korrekthetsbevis.
Ö2 4 februari
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
F8 8 februari (2 timmar)
Grafer: djupetförstsökning, breddenförstsökning, minimala spännande träd, kortaste stigar. (GT: 287-334, 339-353, 360-375, KT/Moln: 73-107, 137-157)
F9 11 februari
Grafer: maximala flöden. (GT: 381-397, KT/Moln: 337-357, 367-373)
Ö3 11 februari
Grafalgoritmer.
F10 12 februari
Algoritmkonstruktion: dekomposition. (GT: 263-273, KT/Moln: 221-234, 242-246)
F11 15 februari
Algoritmkonstruktion: giriga algoritmer, totalsökning. (GT: 257-262, Sup: 31-48, KT/Moln: 115-177, 183-188, Moln: 549-566)
F12 18 februari
Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, KT/Moln: 251-290)
Ö4 18 februari
Dekomposition och lådpackning
Labb 1 18-19 februari
Konkordans, redovisning.
F13 19 februari
Algoritmkonstruktion: mer dynamisk programmering. (GT: 354-359, KT/Moln: 290-311)
F14 22 februari
Algoritmkonstruktion: geometriska algoritmer, Grahamscan. (GT: 572-586)
F15 25 februari
Algoritmkonstruktion: sortering i linjär tid. Räknesortering (GT: 241-244, Sup: 1-6, Moln: 519-524)
Ö5 25 februari
Dynamisk programmering. Teoriredovisning för labb 2.
F16 26 februari
Algoritmkonstruktion: textsökning. (Sup: 7-16, Moln: 525-534, Pythonkramaren II: 46-48)
F17 1 mars
Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
Mästarprov 1, senast måndag 1 mars klockan 11.15!
Algoritmer.
Ö6 4 mars
Algoritmkonstruktion.
Sammanfattning av alla algoritmer hittills i kursen
Period 4: komplexitet
F18 22 mars
Reduktioner. (KT: 451-459, Moln: 375-383)
F19 25 mars
Introduktion till komplexitet. (GT: 592, KT: 463-466, Moln: 387-390)
Ö7 25 mars
Genomgång av lösning till mästarprov 1. Reduktioner.
Labb 2 25-26 mars
Flöden och matchningar, sista redovisningstillfälle.
F20 29 mars
Formella definitioner, turingmaskiner. (GT: 593-599)
F21 1 april
Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
Ö8 1 april
Oavgörbarhet. Teoriredovisning för labb 3.
F22 12 april
Cooks sats. (GT: 600-602)
F23 15 april
NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
Ö9 15 april
NP-fullständighetsbevis.
F24 19 april
NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
F25 22 april
Mer NP-fullständighetsreduktioner. Knuths terminologi
Ö10 22 april
NP-fullständiga problem. Teoriredovisning för labb 4.
Labb 3 22-23 april
Ordkedjor, redovisning.
F26 26 april
Approximationsalgoritmer. (GT: 618-626, KT: 599-630, Moln: 477-508)
F27 29 april
Mer approximationsalgoritmer.
Ö11 29 april
Approximationsalgoritmer.
F28 3 maj
Heuristiska algoritmer. Simulated annealing. (KT: 661-670, Moln: 509-518)
Labb 4 6-7 maj
NP-fullständighetsreduktioner, redovisning.
F29 10 maj
Komplexitetsklasser. (KT: 495-497, 531-547, Moln: 419-421, 455-471)
Mästarprov 2, senast 10 maj klockan 11.15
Komplexitet.
F30 17 maj
Överraskning: programmeringstävlingsverksamheten. Kommer inte på tentan.
F31 20 maj
Repetition.
Ö12 20 maj
Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.
Teoritenta 27 maj klockan 9-12 i sal F1

Handledarschema

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