Schema och detaljschema i ADK, hösten 2011

Detaljschema

Kursen består av 32 föreläsningar och 12 övningar. Alla föreläsningar efter första veckans tre föreläsningar ä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 har använts tidigare i kursen, Sup=Supplementet Algorithms and Complexity 2009/2011.

Period 1
F1 29 augusti (2 timmar): Introduktion till kursen. Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även länksidan.
F2 30 augusti (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 31 augusti (2 timmar): Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (GT: 55-130, 141-151, 429-438, KT/Moln: 57-65); Datastrukturer: latmanshashning, skipp listor. (Sup: 77-83, Moln: 595-602)
Ö1 31 augusti: Algoritmanalys.
F4 5 september: Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F5 7 september: Undre gränser. (GT: 239-240, Sup: 17-29, Moln: 535-547)
F6 8 september: Korrekthetsbevis.
Ö2 8 september: Datastrukturer och undre gränser. Teoriredovisning för labb 1.
F7 12 september: Grafer: djupetförstsökning, breddenförstsökning. (GT: 287-334, KT/Moln: 73-107)
F8 14 september: Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (GT: 287-334, 339-353, 360-375, KT/Moln: 137-157)
F9 15 september: Grafer: maximala flöden. (GT: 381-397, KT/Moln: 337-357, 367-373)
Ö3 16 september: Grafalgoritmer.
Labb 1 16 september: Konkordans, redovisning.
F10 19 september: Algoritmkonstruktion: dekomposition. (GT: 263-273, KT/Moln: 221-234, 242-246)
F11 20 september: Algoritmkonstruktion: giriga algoritmer, totalsökning. (GT: 257-262, Sup: 31-48, KT/Moln: 115-177, 183-188, Moln: 549-566)
F12 21 september: Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, KT/Moln: 251-290)
Ö4 22 september: Dekomposition och lådpackning. Teoriredovisning för labb 2.
F13 26 september: Algoritmkonstruktion: mer dynamisk programmering. (GT: 354-359, KT/Moln: 290-311)
F14 28 september: Algoritmkonstruktion: geometriska algoritmer, Grahamscan. (GT: 572-586)
F15 29 september: Algoritmkonstruktion: sortering i linjär tid. Räknesortering (GT: 241-244, Sup: 1-6, Moln: 519-524)
Ö5 29 september: Dynamisk programmering.
Labb 2 30 september: Ordkedjor, redovisning.
F16 3 oktober: Algoritmkonstruktion: textsökning. (Sup: 7-16, Moln: 525-534, Pythonkramaren II: 46-48)
F17 4 oktober: Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
F18 6 oktober: Probabilistiska algoritmer. (GT: 245-247, KT: 707-724)
Ö6 6 oktober: Algoritmkonstruktion. Teoriredovisning för labb 3.
Sammanfattning av alla algoritmer hittills i kursen
Mästarprov 1, senast måndag 10 oktober klockan 9.15!: Algoritmer.
F19 10 oktober: Reduktioner. (KT: 451-459, Moln: 375-383)
F20 12 oktober: Introduktion till komplexitet, motivering. (GT: 592, KT: 463-466, Moln: 387-390)
F21 13 oktober: Formella definitioner, turingmaskiner. (GT: 593-599)
Ö7 13 oktober: Probabilistiska algoritmer. Reduktioner.
Period 2
F22 24 oktober: Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
Extra visualiseringsföreläsning 24 oktober kl 11-12: NP-reduktionsvisualisering med Alvie (instruktioner)
I Alvie finns reduktioner för delmängdssumma (Subset Sum) och hörntäckning (Vertex Cover) visualiserade och bevisade. Reduktionerna finns implementerade i Java i Teaching machine (klicka på Table of contents, NP-completeness och Run, vänta sedan några sekunder tills maskinen startas; den fungerar ungefär som en grafisk avlusningsmiljö).
Alvie och Teaching machine är utvecklade av Pierluigi Crescenzi.; Reduktionen av 3-cnfsat till delmängdssumma visualiserad med Alvie och sparad som Flash och Quicktime.
F23 25 oktober: Cooks sats. (GT: 600-602)
Ö8 25 oktober: Genomgång av lösning till mästarprov 1. Oavgörbarhet.
Labb 3 28 oktober: Flöden och matchningar, sista redovisningstillfälle.
F24 1 november: NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
F25 2 november: NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
Ö9 2 november: NP-fullständighetsbevis. Teoriredovisning för labb 4.
F26 8 november: Mer NP-fullständighetsreduktioner.; Reduktionen av 3-cnfsat till hörntäckning visualiserad med Alvie och sparad som Flash och Quicktime.
F27 9 november: Approximationsalgoritmer. (GT: 618-626, KT: 599-630, 724-727 Moln: 477-508)
Ö10 9 november: NP-fullständiga problem.
Labb 4 11 november: NP-fullständighetsreduktioner, redovisning.
F28 15 november: Mer approximationsalgoritmer.
F29 16 november: Heuristiska algoritmer. Simulated annealing. (KT: 661-670, Moln: 509-518)
Ö11 16 november: Approximationsalgoritmer.
Mästarprov 2, senast 22 november klockan 9.15: Komplexitet.
F30 22 november: Komplexitetsklasser. (KT: 495-497, 531-547, Moln: 419-421, 455-471)
F31 23 november: Föreläsning till förfogande: Fortsättningskurser, Knuths terminologi, komplexitet för parallella beräkningar.
F32 29 november: Repetition. Kursens betygssystem.
Ö12 29 november: Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.
Teoritenta 19 december klockan 9-12 i sal F1
Extralabb 9 och 11 januari 2012: Heuristik för rollbesättningsproblemet, redovisning av frivillig labb.
Frivillig munta för högre betyg, 12 och 13 januari 2012

Handledarschema