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 det behandlas i kursböckerna. 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.

* F2 6 september(2 timmar)
Repetition av sortering. (KT: 29-56, 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) Datastrukturer: latmanshashning, skipp listor. (Sup: 77-83)

* Ö1 9 september
Algoritmanalys.

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

* F5 10 september
Korrekthetsbevis.

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

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

* F7 16 september
Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KT: 115-177, 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 1723 september
Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-311)

* F11 1824 september
Exempel på motivering av korrekthet: dynamisk programmering

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

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

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

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

* F15 26 septem1 oktober
Algoritmkonstruktion: geometriska algoritmer, Grahamscan.

* Ö5 27 septem3 oktober
Grafalgoritmer och undre gränser

* Labb 2 28 septem4 oktober
Rättstavning, redovisning.

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

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

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

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

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

* F19 314 oktober
Probabilistiska algoritmer. (KT: 707-724)

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

* Ö7 17 oktober
Probabilistiska algoritmer. Reduktioner.¶


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

* Ö7 11 oktober
Probabilistiska algoritmer. Reduktioner.¶ Period 2

* F22 11 okto4 november
Formella definitioner, turingmaskiner.

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

* F24 23 okto6 november
Cooks sats.

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

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

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

* F26 22 okto11 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, 497-505)

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

* F28 518 november
Mer NP-fullständighetsreduktioner.

* F29 720 november
Approximationsalgoritmer. (KT: 599-630, 724-727)

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

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

* F30 125 november
Mer approximationsalgoritmer.

* Mästarprov 2, senast 27 november klockan 10.15!
Komplexitet. Muntliga redovisningar sker 3-6 december.¶


* F31 1427 november
Heuristiska algoritmer. Simulated annealing. (KT: 661-670)

* Ö11 1529 november
Approximationsalgoritmer.

* Mästarprov 2, senast 19 november klockan 15.00
Komplexitet.¶
* F32 21 novF32 2 december
Komplexitetsklasser. (KT: 495-497, 531-547)

* F33 27 nov9 december
Repetition. Kursens betygssystem.

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

* Teoritenta 1320 december klockan 9-12 i sal F1
* Extralabb, längst ner på sidan.
Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, 17 december klockan 9-12 i Spelhallen och Sporthallenjanuari 2014

* Frivillig munta för högre betyg, 17-19 decemberjanuari 2014
Handledarschema