Detaljschema

Detaljschema för adk13

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ö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 17 september

Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-311)

• F11 18 september

Exempel på motivering av korrekthet: dynamisk programmering

• F12 18 september

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

• F13 19 september

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

• Ö4 20 september

Dynamisk programmering. Teoriredovisning för labb 2.

• F14 24 september

Undre gränser. (Sup: 17-29)

• F15 26 september

Algoritmkonstruktion: geometriska algoritmer, Grahamscan.

• F16 27 september

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

• Ö5 27 september

Grafalgoritmer och undre gränser

• Labb 2 28 september

Rättstavning, redovisning.

• F17 1 oktober

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

• F18 2 oktober

Algoritmkonstruktion: polynomberäkningar och FFT. (KT: 234-242)

• F19 3 oktober

Probabilistiska algoritmer. (KT: 707-724)

• Ö6 4 oktober

Algoritmkonstruktion. Teoriredovisning för labb 3. 
Sammanfattning av alla algoritmer hittills i kursen

• Mästarprov 1, senast måndag 8 oktober klockan 11.15!

Algoritmer.

• F20 8 oktober

Reduktioner. (KT: 451-459)

• F21 9 oktober

Introduktion till komplexitet, motivering. (KT: 463-466)

• F22 11 oktober

Formella definitioner, turingmaskiner.

• Ö7 11 oktober

Probabilistiska algoritmer. Reduktioner.

Period 2

• F23 22 oktober

Oavgörbarhet. (Sup: 49-73)

• F24 23 oktober

Cooks sats.

• Ö8 25 oktober

Genomgång av lösning till mästarprov 1. Oavgörbarhet.

• Labb 3 26 oktober

Flöden och matchningar, sista redovisningstillfälle.

• F25 29 oktober

NP-fullständighetsbevis. (KT: 466-495)

• F26 22 oktober 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 1 november

NP-fullständighetsreduktioner. (KT: 459-463, 497-505)

• Ö9 2 november

NP-fullständighetsbevis. Teoriredovisning för labb 4.

• F28 5 november

Mer NP-fullständighetsreduktioner.

• F29 7 november

Approximationsalgoritmer. (KT: 599-630, 724-727)

• Ö10 8 november

NP-fullständiga problem.

• Labb 4 9 november

NP-fullständighetsreduktioner, redovisning.

• F30 12 november

Mer approximationsalgoritmer.

• F31 14 november

Heuristiska algoritmer. Simulated annealing. (KT: 661-670)

• Ö11 15 november

Approximationsalgoritmer.

• Mästarprov 2, senast 19 november klockan 15.00

Komplexitet.

• F32 21 november

Komplexitetsklasser. (KT: 495-497, 531-547)

• F33 27 november

Repetition. Kursens betygssystem.

• Ö12 29 november

Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.

• Teoritenta 13 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 Sporthallen

Frivillig munta för högre betyg, 17-19 december

Handledarschema