Till KTH:s startsida Till KTH:s startsida

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. 

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.

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.

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.
Alvie är utvecklat av Pierluigi Crescenzi. Om du inte vill ladda ner Alvie själv kan du titta på reduktionsvisualiseringarna som filmer:
Visualisering av reduktionen av 3-CNFSAT till delmängdssumma som Flash och Quicktime.
Visualisering av reduktionen av 3-CNFSAT till hörntäckning 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)

NP-fullständiga problem.

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.

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.

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

Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, 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.