Kursöversikt
Viggo Kann [VK] och Stefan Nilsson [SN] delar på föreläsningarna. Tomas Ekholm [TE] håller en gästföreläsning. Både föreläsningar och övningar ges i sal på campus. 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å det finns förberedande videor och uppgifter till dessa föreläsningar. Första timmen på dessa föreläsningar är avsatt för att du ska kunna göra förberedelserna. Ta i så fall med egen dator. Om du gör förberedelserna i förväg räcker det att du kommer till andra timmen på 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
- F1
Download F1 30 augusti (2 timmar)
[SN+VK] Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)
Mer material: algoritm Links to an external site., tidskomplexitet Links to an external site., ordonotation Links to an external site., mästarsatsen Links to an external site., bitkostnad. Links to an external site.
- F2
Download F2 31 augusti (2 timmar)
[SN] Repetition av sortering (animering 1 Links to an external site., animering 2 Links to an external site.). (KTorig: 209-221/KTnie: 115-127)
Effektiv kodning och testning. Labbpartnermatchning i pausen.
Mer material: insättningssortering Links to an external site. (videoklipp Links to an external site.), quicksort Links to an external site.. Se även Diverse nyttiga och roliga länkar i ADK.
- F3
Download F3 1 september (2 timmar)
[VK] Datastrukturer: repetition Links to an external site., tidskomplexitet för listor Links to an external site., hashning Links to an external site., praktiska datastrukturer, trie Links to an external site. (animering Links to an external site.) (KT: 57-65) Latmanshashning, skipplistor Links to an external site.. (Sup: 77-83 Download Sup: 77-83) Labbpartnermatchning i pausen.
- Ö1
Download Ö1 4 september
Algoritmanalys.
- F4
Download F4 5 september (färgfråga om datastrukturer
Download färgfråga om datastrukturer)
[VK] Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Mer material: bloomfilter Links to an external site. - F5
Download F5 6 september
[SN] Grafer: djupetförstsökning Links to an external site., breddenförstsökning Links to an external site.. (KT: 73-107)
Mer material: grafteori och grafsökning Links to an external site., grafpaket i Go Links to an external site. - F6
Download F6 7 september
[SN] Korrekthetsbevis.
Mer material: invarianter Links to an external site., induktion Links to an external site..
- Ö2
Download Ö2 8 september
Datastrukturer och grafer. Teoriredovisning till labb 1.
- F7
Download F7 11 september
[SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)
- F8
Download F8 12 september
[SN] Algoritmkonstruktion: dekomposition. (KTorig: 221-234, 242-246/KTnie: 127-140, 148-152) - F9 13 september (OBS, omvänd föreläsning. Förberedelse krävs, som kan göras under första föreläsningstimmen)
[VK] Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-260)
Visualiseringar: Fibonaccitalen Links to an external site..
Första timmen: tid för att göra förberedelserna.
Andra timmen: frågestund och arbete med uppgifter i grupp Download arbete med uppgifter i grupp (lösningar Download lösningar) - Ö3
Download Ö3 13 september
Dekomposition och dynamisk programmering. - Labb 1 14 september
Konkordans, redovisning. - F10 18 september (OBS, omvänd föreläsning. Förberedelse krävs!)
[VK] Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 261-290)
Första timmen: tid för att göra förberedelserna.
Andra timmen: frågestund och arbete med uppgifter i grupp Download arbete med uppgifter i grupp (lösningar Download lösningar)
Dags att börja titta på övningsmästarprov 1! - F11 19 september (OBS, omvänd föreläsning. Förberedelse krävs!)
[VK] Dynamisk programmering, del 3: konstruktion av lösning och motivering av korrekthet. (KT: 290-301, 307-311)
Första timmen: tid för att göra förberedelserna.
Andra timmen: frågestund och arbete med uppgifter i grupp Download arbete med uppgifter i grupp (lösningar Download lösningar) - F12
Download F12 20 september
[SN] Grafer: minimala spännande träd (Prim Links to an external site. och Kruskal Links to an external site.), kortaste stigar (Dijkstra Links to an external site.). (KTorig: 137-157/KTnie: 179-199) - Ö4
Download Ö4 21 september
Dynamisk programmering. Teoriredovisning till labb 2. - F13
Download F13 26 september
[VK] Grafer: demo av maximala flöden Links to an external site.. Extra föreläsningsbilder från en kurs på Princeton Links to an external site. (KT: 337-357, 367-373)
- Övningsmästarprovsövning 1 26 september
Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1, som publiceras denna dag.
Grupp 1 (Noras grupp) genomför övningsmästarprovet i Zoom: https://kth-se.zoom.us/j/65627359290 Links to an external site. (Du laddar då upp din lösning i Canvas under övningen.)
Övriga grupper är i sal. Det går bra att gå till vilken av grupperna som helst. - F14
Download F14 27 september
[VK] Undre gränser. (Sup: 17-29)
Genomgång av lydelsen till uppgift 2 på mästarprov 1.
- F15
Download F15 28 september
[SN] Algoritmkonstruktion: geometriska algoritmer, geomalgorithms.com Links to an external site., Grahamscan: beskrivning Links to an external site., animering Links to an external site..
Genomgång av lydelsen till uppgift 1 på mästarprov 1.
- Ö5
Download Ö5 28 september
Grafalgoritmer och undre gränser.
- Labb 2 29 september
Rättstavning, redovisning.
- F16
Download F16 2 oktober kl 15
[SN] Algoritmkonstruktion: sortering i linjär tid. Räknesortering och radixsortering Links to an external site.. (Sup: 1-6)
Genomgång av lydelsen till uppgift 3 på mästarprov 1.
- F17 2 oktober kl 16
[SN] Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48 Download Pythonkramaren II: 46-48)
- F18 3 oktober
[TE] Inspirationsföreläsning. Beständiga datastrukturer Links to an external site.. Benefits of pure functions Links to an external site.
- Ö6
Download Ö6 5 oktober
Algoritmkonstruktion. Teoriredovisning till labb 3.
Sammanfattning av alla algoritmer hittills i kursen.
- F19
Download F19 9 oktober
[SN] Probabilistiska algoritmer. (KTorig: 707-734, 769-776/KTnie: 661-688, 723-730)
Lasvegas- och Montecarloalgoritmer, Links to an external site. Probabilistisk algoritm för medianproblemet Download Probabilistisk algoritm för medianproblemet
- F20
Download F20 10 oktober (OBS, omvänd föreläsning: förberedelse krävs!)
[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 11 oktober
Probabilistiska algoritmer. Reduktioner. - F21
Download F21 12 oktober (OBS, omvänd föreläsning, förberedelse krävs!)
[SN] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)
Första timmen: tid för att göra förberedelserna.
Andra timmen: frågestund och arbete med uppgifter i grupp. - Mästarprov 1 (Algoritmkonstruktion) senast tisdag 17 oktober klockan 19:00.
Uppgiftslydelsen publiceras i Canvas 26 september.
Muntliga redovisningar sker 23-27 oktober.
Period 2
- F22
Download F22 30 oktober
[VK] Formella definitioner, turingmaskiner Links to an external site.. (PDF att läsa Download PDF att läsa, bild 1 Links to an external site., bild 2 Links to an external site., bild 3) - F23
Download F23 31 oktober
[SN] Oavgörbarhet. (Sup: 49-73)
- Ö8
Download Ö8 1 november
Genomgång av lösning till mästarprov 1 Download lösning till mästarprov 1. Oavgörbarhet.
- Labb 3 3 november
Flöden och matchningar, redovisning.
- F24
Download F24 6 november
[VK] Cooks sats. (PDF att läsa) -
F25 Download F25 7 november kl 15
[VK] NP-fullständighetsbevis. (KT: 466-495)
- F26 7 november kl 16
[VK] NP-reduktionsvisualisering med Alvie Links to an external site..
Alvie är utvecklat av Pierluigi Crescenzi. Om du själv vill ha tillgång till Alvie kan du ladda ner Alviekällkoden själv Links to an external site. och kompilera. Enklare är att titta på reduktionsvisualiseringarna som filmer:
Visualisering av reduktion av 3-CNFSAT till hörntäckning som Quicktime / mp4.
Visualisering av reduktion av 3-CNFSAT till delmängdssumma som Quicktime / mp4.
- Ö9
Download Ö9 9 november
NP-fullständighetsbevis. Teoriredovisning till labb 4.
- F27
Download F27 14 november kl 15
[SN] NP-fullständighetsreduktioner. (KT: 459-463)
- F28
Download F28 14 november kl 16
[VK] Mer NP-fullständighetsreduktioner. (KT: 497-505) - Dags att börja titta på övningsmästarprov 2!
- Två relevanta länkar från kursens länksamling för den som vill fördjupa sin förståelse av oavgörbarhet och reduktioner:
- Math has a fatal flaw - en film om ofullständighet och oavgörbarhet
- Reducing reductions to intuition - Douglas Wikström beskriver och definierar dom olika typerna av reduktioner som ingår i ADK. - Ö10
Download Ö10 15 november
NP-fullständiga problem.
- Labb 4 17 november
NP-fullständighetsreduktioner, redovisning.
- F29
Download F29 20 november
[SN] Heuristiska algoritmer Links to an external site.. Simulated annealing Links to an external site.. (KTorig: 661-670/KTnie: 749-758)
Detta är Stefans sista föreläsning som lärare på KTH. Missa inte den! - F30
Download F30 21 november
[VK] Approximationsalgoritmer. (KT: 599-630) - Övningsmästarprovsövning 2 23 november
Redovisning av övningsmästarprov 2 och genomgång av fler exempel på NP-fullständighetsproblem som förberedelse till mästarprov 2, som publiceras denna dag.
Grupp 2 (Douglas grupp) genomför övningsmästarprovet i Zoom Links to an external site..
Övriga grupper är i sal.
Grupp 3 (Jespers grupp) genomför övningsmästarprovet den 24 november kl 10-12.
Det går bra att gå till vilken av grupperna som helst.
Lösningsförslag till övningsmästarprovet Download Lösningsförslag till övningsmästarprovet
- F31
Download F31 27 november
[VK] Mer approximationsalgoritmer. (webbsida Links to an external site. om Christofides algoritm, Viggos lista med approximationsresultat för NP-svåra optimeringsproblem)
Genomgång av lydelsen till uppgift 1 på mästarprov 2. - Ö11
Download Ö11 28 november
Approximationsalgoritmer. Teoriredovisning till labb 5. - F32
Download F32 29 november
[VK] Komplexitetsklasser. (KT: 495-497, 531-547)
Genomgång av lydelsen till uppgift 2 och 3 på mästarprov 2. - F33
Download F33 5 december
[VK] Repetition. Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination.
- Ö12
Download Ö12 6 december
Komplexitetsklasser och repetition. - Mästarprov 2 (komplexitet), senast 7 december klockan 19:00!
Uppgiftslydelsen publiceras i Canvas 23 november.
Muntliga redovisningar sker 11-15 december. - Labb 5 7 december
Heuristik för rollbesättningsproblemet, redovisning.
- Extra labbredovisningstillfälle 14 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ö. Redovisningar kommer att kunna genomföras både i Zoom och i datorsal Grå+Karmosin. - Teoritenta 18 december klockan 9-12. Skrivtid 9:00-10:30 i Canvas. Obligatorisk rättningssession kl 11:00-12:00 i Zoom. Sedvanlig tentaanmälan måste göras i förväg.
Den som har 50% förlängd skrivtid tentar klockan 8:15-10:30. - Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 18 december och redovisas skriftligt 4 januari och muntligt 8-11 januari 2024.
- Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (övriga labbar kan inte redovisas), 8 januari 2024 kl 9-12. Bokningslistor publiceras i Canvas 31 december.
- Labbkursreflektion bör lämnas in senast 9 januari 2024.
- Frivillig munta för högre mästarprovsbetyg, 11 och 12 januari 2024. Anmälan görs under perioden 31 december 2023 till 5 januari 2024. Instruktioner om hur muntan genomförs.
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å adk23. Labbkursreflektionen lämnar du in i kursrummet för adk23 när du är klar med alla labbarna.
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å att du kan lämna in mästarprovet).
Den som har teoritentan kvar kan anmäla sig till och gå upp på omtentan i april 2024 eller nästa ordinarietenta i december 2024.