Detaljschema

Detaljschema för adk13 Kursen består av 33 föreläsningar och 12 övningar. Alla föreläsningar efter första veckans tre föreläsningar är entimmesföreläsningar (men av schematekniska skäl har två par av entimmesföreläsningar kommit att hamna direkt efter varandra). 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 i kursböckerna du bör ha skummat innan du kommer till föreläsningen.

KT=Kleinberg-Tardos, Sup=supplementet Algorithms and Complexity.

Period 1

* F1 5 september (2 timmar)
Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)

* F2 6 september(2 timmar)
Repetition av sortering. (KT: 209-221)Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även Diverse länkar i kurswebbens vänstermeny.

* F3 6 september (2 timmar)
Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (KT: 57-65) Latmanshashning, skipplistor. (Sup: 77-83)

* Ö1 9 september
Algoritmanalys.

* F4 9 september
Datastrukturer: bloomfilter. Tillämpning: rättstavning.

* F5 10 september
Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)

* F6 12 september
Korrekthetsbevis. (webbsida att läsa)

* Ö2 12 september
Datastrukturer och grafer. Teoriredovisning för labb 1.

* F7 16 september
Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KT: 115-136, 183-188)

* F8 17 september
Algoritmkonstruktion: dekomposition. (KT: 221-234, 242-246)

* F9 19 september
Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-290) Visualiseringar: Fibonaccitalen.

* Ö3 19 september
Dekomposition och dynamisk programmering.

* Labb 1 20 september
Konkordans, redovisning.

* F10 23 september
Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-301)

* F11 24 september
Exempel på motivering av korrekthet: dynamisk programmering. (KT: 307-311)

* F12 25 september
Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KT: 137-157)

* Ö4 26 september
Dynamisk programmering. Teoriredovisning för labb 2.

* F13 30 september
Grafer: maximala flöden. (KT: 337-357, 367-373)

* F14 1 oktober
Undre gränser. (Sup: 17-29)

* F15 1 oktober
Algoritmkonstruktion: geometriska algoritmer. (webbsida om Grahamscan)

* Ö5 3 oktober
Grafalgoritmer och undre gränser.

* Labb 2 4 oktober
Rättstavning, redovisning.

* F16 7 oktober
Algoritmkonstruktion: sortering i linjär tid. Räknesortering. (Sup: 1-6)

* F17 8 oktober
Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)

* F18 9 oktober
Algoritmkonstruktion: polynomberäkningar och FFT. (KT: 234-242)

* Ö6 10 oktober
Algoritmkonstruktion. Teoriredovisning för labb 3. Sammanfattning av alla algoritmer hittills i kursen.

* Mästarprov 1, senast måndag 14 oktober klockan 11.15!
Algoritmer. Muntliga redovisningar sker 18-23 oktober.

* F19 14 oktober
Probabilistiska algoritmer. (KT: 707-734, 769-776)

* F20 15 oktober
Reduktioner. (KT: 451-459)

* Ö7 17 oktober
Probabilistiska algoritmer. Reduktioner.

* F21 17 oktober
Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)

Period 2

* F22 4 november
Formella definitioner, turingmaskiner. (PDF att läsa)

* F23 4 november
Oavgörbarhet. (Sup: 49-73)

* F24 6 november
Cooks sats. (PDF att läsa)

* Ö8 8 november
Genomgång av lösning till mästarprov 1. Oavgörbarhet.

* Labb 3 8 november
Flöden och matchningar, sista redovisningstillfälle.

* F25 11 november kl 13-14
NP-fullständighetsbevis. (KT: 466-495)

* F26 11 november kl 14-15
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.Reduktionen av 3-cnfsat till hörntäckning visualiserad med Alvie och sparad som Flash och Quicktime.

* F27 12 november
NP-fullständighetsreduktioner. (KT: 459-463)

* Ö9 13 november
NP-fullständighetsbevis. Teoriredovisning för labb 4.

* F28 18 november
Mer NP-fullständighetsreduktioner. (KT: 497-505)

* F29 20 november
Approximationsalgoritmer. (KT: 599-630)

* Ö10 20 november
NP-fullständiga problem.

* Labb 4 22 november
NP-fullständighetsreduktioner, redovisning.

* F30 25 november
Mer approximationsalgoritmer. (webbsida om Christofides algoritm)

* Mästarprov 2, senast 29 november klockan 8.15!
Komplexitet. Muntliga redovisningar sker 3-6 december.

* Ö11 29 november
Approximationsalgoritmer.

* F31 2 december (flyttad från 27 november)
Heuristiska algoritmer. Simulated annealing. (KT: 661-670 <avsnitt 13.1-13.2 i nytrycket>)

* F32 3 december (flyttad från 2 december, ny föreläsningstid)
Komplexitetsklasser. (KT: 495-497, 531-547)

* F33 9 december
Repetition. Kursens betygssystem.

* Ö12 9 december
Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.

* Extra labbredovisningstillfälle 19 december klockan 13-15 i Grå sal
* Teoritenta 20 december klockan 9-12 i sal F1
* Extralabb, uppgiftslydelse längst ner på sidan
Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, preliminärt 10 januari 2014 klockan 13-16 i Spelhallen. I mån av tid kan också övriga labbar redovisas då. Ingen anmälan.

* Frivillig munta för högre betyg, 15-17 januari 2014. Anmälan görs senast 10 januari klockan 13.