Detaljschema

Kursens pedagogiska upplägg

  • Studera på det sätt som är effektivast för dig! Allt föreläsnings- och övningsmaterial finns tillgängligt i förväg.
  • Koncentrerade entimmesföreläsningar med läsanvisningar. Kom förberedd och var vaken för bästa resultat! I avsnittet dynamisk programmering används omvänd undervisning (flipped classroom).
  • Övningsuppgifter med fullständiga lösningar. Övningsgrupper med svårighetsgradering. Ett urval av uppgifterna löses på övningarna, resten lämnas för egen övning.
  • Momenten i kursen tränar verkliga arbetssituationer för bättre autenticitet.
  • Aktiverande färgfrågor på föreläsningarna och kontinuerlig examination med labbteoriuppgiftsredovisning inför varje datorlabb gör att du automatiskt hänger med i kursen.
  • Undervisning byggd på pedagogisk forskning - en hel doktorsavhandling om ADK las fram 2014!
  • Målrelaterade betygskriterier; välj själv betyg!
  • Gott om tid för labbar och mästarprov, ingen stressad tentasituation.

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 har omvänd undervisning, så videor ska ses och uppgifter ska göras före varje föreläsning 

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

  • Download Ö2 4 september
    Datastrukturer och grafer. Teoriredovisning för labb 1.
  • F7 10 september
    [SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)
  • MAS1-övning 24 september
    Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1.
  • F14 25 september
    [VK] Undre gränser. (Sup: 17-29)
    Genomgång av lydelsen till uppgift 1 och 3 på mästarprov 1.
  • Labb 2 27 september
    Rättstavning, redovisning.
  • F18 1 oktober
    [SN] Algoritmkonstruktion: polynomberäkningar och FFT. (KTorig: 234-242/KTnie: 140-148)

Sammanfattning av alla algoritmer hittills i kursen.

  • F20 8 oktober
    [SN] Reduktioner. (KT: 451-459)
  • Download Ö7 9 oktober
    Probabilistiska algoritmer. Reduktioner.
  • Mästarprov 1, senast onsdag 9 oktober klockan 19!
    Uppgiftslydelsen läggs upp i Canvas 25 september.

    Algoritmer. Muntliga redovisningar sker 14-18 oktober.

  • F21 10 oktober
    [SN] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)

Period 2

  • F23 30 oktober
    [SN] Oavgörbarhet. (Sup: 49-73)
  • Download Ö8 31 oktober
    Genomgång av lösning till mästarprov 1. Oavgörbarhet.
  • Labb 3 1 november
    Flöden och matchningar, redovisning.
  • F24 4 november
    [VK] Cooks sats. (PDF att läsa)

  • F25 6 november kl 14
    [VK] NP-fullständighetsbevis. (KT: 466-495)

  • Download Ö9 7 november
    NP-fullständighetsbevis. Teoriredovisning för labb 4.
  • Download F27 13 november kl 15
    [SN] NP-fullständighetsreduktioner. (KT: 459-463)
  • Labb 4 15 november
    NP-fullständighetsreduktioner, redovisning.
  • Mästarprov 2, senast 5 december klockan 13!
    Uppgiftslydelsen läggs upp i Canvas 21 november.

    Komplexitet. Muntliga redovisningar sker 9-13 december.

  • Download Ö12 4 december
    Komplexitetsklasser och repetition.
  • Labb 5 6 december
    Heuristik för rollbesättningsproblemet, redovisning.
  • Extra labbredovisningstillfälle 11 december för alla labbar, inklusive högrebetygslabben. Bokningslistor.
  • Teoritenta 17 december klockan 9-12 i sal F1 och F2.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 17 december och redovisas skriftligt 4 januari och muntligt veckan 7-10 januari 2020.
  • Frivillig munta för högre mästarprovsbetyg, 9-10 januari 2020. Anmälan görs under perioden 31 december 2019 till 6 januari 2020. 
  • Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (inga andra labbar kan redovisas), 14 januari 2020 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å adk19.

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å adk19.

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