Kursöversikt

Kursen består av 33 föreläsningar och 14 övningar. Alla föreläsningar efter första veckans tre föreläsningar är egentligen entimmesföreläsningar (men av schematekniska skäl har vid ett tillfälle två entimmesföreläsningar kommit att hamna direkt efter varandra). Viggo Kann [VK] och Stefan Nilsson [SN] delar på föreläsningarna. Följande 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. 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.

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

  • Ö1 28 augusti
    Algoritmanalys.
  • Ö5 24 september
    Grafalgoritmer och undre gränser.
  • Labb 2 25 september
    Rättstavning, redovisning.

Sammanfattning av alla algoritmer hittills i kursen.

  • Ö7 7 oktober
    Probabilistiska algoritmer. Reduktioner.
  • Mästarprov 1, senast onsdag 7 oktober klockan 19!
    Uppgiftslydelsen läggs upp i Canvas 23 september.

    Algoritmer. Muntliga redovisningar sker 12-16 oktober.

Period 2

  • Ö8 29 oktober (endast grupp 2-4, den lite enklare gruppen är inställd)
    Genomgång av lösning till mästarprov 1. Oavgörbarhet.
  • Labb 3 30 oktober
    Flöden och matchningar, redovisning.
  • F27 10 november
    [SN] NP-fullständighetsreduktioner. (KT: 459-463)
    Zoomlänk
  • F28 11 november
    [VK] Mer NP-fullständighetsreduktioner. (KT: 497-505)
    Zoomlänk
  • Ö10 11 november (endast grupp 2-4, den lite enklare gruppen är inställd)
    NP-fullständiga problem.
  • Labb 4 13 november
    NP-fullständighetsreduktioner, redovisning.
  • F31 24 november
    [VK] Mer approximationsalgoritmer. (webbsida om Christofides algoritm, Viggos lista med approximationsresultat för NP-svåra optimeringsproblem)
    Genomgång av lydelsen till uppgift 1 och 3 på mästarprov 2.
    Zoomlänk
  • F32 25 november
    [VK] Komplexitetsklasser. (KT: 495-497, 531-547)
    Genomgång av lydelsen till uppgift 2 på mästarprov 2.
  • Mästarprov 2, senast 3 december klockan 15!
    Uppgiftslydelsen läggs upp i Canvas 19 november.

    Komplexitet. Muntliga redovisningar sker 7-11 december.

  • Ö12 2 december (endast grupp 2-4, den lite enklare gruppen är inställd)
    Komplexitetsklasser och repetition.
  • Labb 5 4 december
    Heuristik för rollbesättningsproblemet, redovisning.
  • Extra labbredovisningstillfälle 11 december för alla labbar, inklusive högrebetygslabben. Bokningslistor.
  • Teoritenta 15 december klockan 9-12. Skrivtid 9:00-10:30. Obligatorisk rättningssession kl 11:00-12:00.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 15 december och redovisas skriftligt 4 januari och muntligt veckan 7-11 januari 2021.
  • Frivillig munta för högre mästarprovsbetyg, 13 och 15 januari 2021. Anmälan görs under perioden 31 december 2020 till 6 januari 2021. 
  • Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (inga andra labbar kan redovisas), 12 januari 2021 kl 9-12. 

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

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; du får leta upp kursrummet i Canvas och läsa informationen om mästarproven där). Kursledare för DD2352 är Per Austrin. Säg till den du redovisar för att du ska ha mästarprovet rapporterat på adk20.

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