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.

• 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.

• Frivillig munta för högre betyg, 15-17 januari 2014