Kursöversikt

Viggo Kann [VK] och Stefan Nilsson [SN] delar på föreläsningarna, som under period 1 genomförs via Zoom:  https://kth-se.zoom.us/j/66455760375 Links to an external site.

Under period 2 ges föreläsningarna i sal enligt ordinarie schema.

Nedanstående tabell visar vad som kommer att behandlas under föreläsningarna och övningarna. För varje föreläsning anges vilket material i kurslitteraturen som behandlas. Du bör ha skummat det innan du kommer till föreläsningen för att ha riktig glädje av föreläsningen. I tabellen nedan finns länkar till föreläsningsbilder, övningsuppgifter och annat material.

Föreläsning 9-11 om dynamisk programmering samt föreläsning 20 och 21 om reduktioner och introduktion till komplexitet har omvänd undervisning, så videor ska ses och uppgifter ska göras före dessa föreläsningar. Första timmen på föreläsning 9, 10, 11 och 20 är avsatt för att du ska kunna göra förberedelserna.

Undervisning, redovisningar och läsanvisningar

  • KT=Kleinberg-Tardos, oavsett om det är KTorig eller KTnie
  • KTorig=Kleinberg-Tardos International Edition (2006) eller motsvarande amerikanska utgåva
  • KTnie=Kleinberg-Tardos New International Edition (2014), när denna skiljer sig från den tidigare utgåvan (kapitel 5 Divide and Conquer kommer före kapitel 4 Greedy Algorithms och kapitel 13 Randomized Algorithms kommer före kapitel 12 Local Search)
  • Sup=supplementet Algorithms and Complexity

Period 1

  • F7 Download F7 14 september
    [SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)
  • Labb 2 1 oktober
    Rättstavning, redovisning.

Sammanfattning av alla algoritmer hittills i kursen.

  • Download F20 13 oktober OBS, omvänd föreläsning: Förbered dig genom att göra detta quiz!
    [SN] Reduktioner. (KT: 451-459)
    Första timmen: tid för att göra förberedelserna.
    Andra timmen: frågestund och arbete med uppgifter i grupp
  • Ö7 Download Ö7 13 oktober
    Probabilistiska algoritmer. Reduktioner.
  • Mästarprov 1, senast tisdag 12 oktober klockan 13:00!
    Uppgiftslydelsen publiceras i Canvas 28 september.

    Algoritmer. Muntliga redovisningar sker 18-26 oktober.

  • Download F21 15 oktober OBS, omvänd föreläsning, förberedelse krävs!
    [SN] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)
    Förberedelserna ska göras före föreläsningen. Hela föreläsningen ägnas åt frågestund och arbete med uppgifter i grupp

Period 2

I period 2 ges föreläsningarna i sal enligt ordinarie schema.

  • Ö8 Download Ö8 3 november
    Genomgång av lösning till mästarprov 1. Oavgörbarhet.
  • Labb 3 4 november
    Flöden och matchningar, redovisning.
  • Download F27 16 november
    [SN] NP-fullständighetsreduktioner. (KT: 459-463)
  • Labb 4 22 november
    NP-fullständighetsreduktioner, redovisning.
  • Ö12 Download Ö12 7 december (övningsgrupp 2 inställd)
    Komplexitetsklasser och repetition.
  • Mästarprov 2 , senast 8 december klockan 18:00!
    Uppgiftslydelsen publiceras i Canvas 24 november.

    Komplexitet. Muntliga redovisningar sker 13-17 december.

  • Labb 5 10 december
    Heuristik för rollbesättningsproblemet, redovisning. 
  • Extra labbredovisningstillfälle 15 december för alla labbar, inklusive högrebetygslabben.
    Labbredovisningar prioriteras framför labbhjälp. Eftersom längden på redovisningarna varierar läggs inga bokningslistor upp, utan Stay-a-while används som kö.

Efter period 2 är kursen slut. Den som har labbar kvar att redovisa kan göra det antingen i labbveckan i juni eller under våren på labbpassen i systerkursen DD2352 Algoritmer och komplexitet. Säg till den du redovisar för att du ska ha labben rapporterad på adk21.

Den som har mästarprov kvar kan göra dom i en senare kursomgång av antingen ADK (som går varje hösttermin) eller systerkursen DD2352 (som går varje vårtermin; du ska inte registrera dig på DD2352, men du behöver kontakta kursledaren för DD2352, Per Austrin, för att bli inlagd i kursrummet). Säg till den du redovisar att du ska ha mästarprovet rapporterat på adk21.

Den som har teoritentan kvar kan gå upp på omtentan i april 2022 eller nästa ordinarietenta i december 2022.