Kursöversikt
Viggo Kann [VK] och Stefan Nilsson [SN] delar på föreläsningarna. Vi planerar att ge både föreläsningar och övningar i sal på campus. Om undervisning på grund av sjukdom eller smittrestriktioner behöver flyttas till Zoom kommer det att meddelas här och i anslag på kurswebben.
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 29 augusti (2 timmar)
[SN+VK] Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)
Mer material: algoritm, tidskomplexitet, ordonotation, mästarsatsen, bitkostnad.
- F2 1 september (2 timmar)
[SN] Repetition av sortering (animering 1, animering 2). (KTorig: 209-221/KTnie: 115-127)
Effektiv kodning och testning. Labbpartnermatchning i pausen.
Mer material: insättningssortering (videoklipp), quicksort. Se även Diverse nyttiga och roliga länkar i ADK.
- F3 2 september (2 timmar)
[VK] Datastrukturer: repetition, tidskomplexitet för listor, hashning, praktiska datastrukturer, trie (animering) (KT: 57-65) Latmanshashning, skipplistor. (Sup: 77-83) Labbpartnermatchning i pausen.
- Ö1 2 september
Algoritmanalys.
- F4 5 september (färgfråga om datastrukturer)
[VK] Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Mer material: bloomfilter - F5 6 september
[SN] Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)
Mer material: grafteori och grafsökning, grafpaket i Go - F6 7 september
[SN] Korrekthetsbevis.
Mer material: invarianter, induktion.
- Ö2 8 september
Datastrukturer och grafer. Teoriredovisning till labb 1.
- F7 13 september
[SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)
- F8 14 september
[SN] Algoritmkonstruktion: dekomposition. (KTorig: 221-234, 242-246/KTnie: 127-140, 148-152) - F9 15 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.
Första timmen: tid för att göra förberedelserna.
Andra timmen: frågestund och arbete med uppgifter i grupp, lösningar till uppgifterna - Ö3 16 september
Dekomposition och dynamisk programmering. - Labb 1 19 september
Konkordans, redovisning. - F10 19 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, lösningar till uppgifterna
Dags att börja titta på övningsmästarprov 1! - F11 20 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, lösningar till uppgifterna - F12 21 september
[SN] Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KTorig: 137-157/KTnie: 179-199) - Ö4 22 september
Dynamisk programmering. Teoriredovisning till labb 2. - F13 27 september
[VK] Grafer: demo av maximala flöden. Extra föreläsningsbilder från en kurs på Princeton (KT: 337-357, 367-373)
- MAS1-övning 27 september
Redovisning av övningsmästarprov 1 (lösningsförslag) som förberedelse till mästarprov 1, som publiceras denna dag. - F14 28 september
[VK] Undre gränser. (Sup: 17-29)
Genomgång av lydelsen till uppgift 1 på mästarprov 1.
- F15 29 september
[SN] Algoritmkonstruktion: geometriska algoritmer, geomalgorithms.com, Grahamscan: beskrivning, animering.
Genomgång av lydelsen till uppgift 2 på mästarprov 1.
- Ö5 29 september
Grafalgoritmer och undre gränser.
- Labb 2 30 september
Rättstavning, redovisning.
- F16 3 oktober kl 10
[SN] Algoritmkonstruktion: sortering i linjär tid. Räknesortering och radixsortering. (Sup: 1-6)
Genomgång av lydelsen till uppgift 3 på mästarprov 1.
- F17 3 oktober kl 11
[SN] Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)
Visualiseringar
- F18 5 oktober
[SN] Beständiga datastrukturer: Persistent data structures in functional programming, Benefits of pure functions
- Ö6 6 oktober
Algoritmkonstruktion. Teoriredovisning till labb 3.
Sammanfattning av alla algoritmer hittills i kursen.
- F19 10 oktober
[SN] Probabilistiska algoritmer. (KTorig: 707-734, 769-776/KTnie: 661-688, 723-730)
Lasvegas- och Montecarloalgoritmer, Probabilistisk algoritm för medianproblemet
- F20 11 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 12 oktober
Probabilistiska algoritmer. Reduktioner. - Mästarprov 1, senast tisdag 18 oktober klockan 18:00.
Uppgiftslydelsen publiceras i Canvas 27 september.Algoritmer. Muntliga redovisningar sker 21-28 oktober.
- F21 13 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.
Period 2
- F22 30 oktober
[VK] Formella definitioner, turingmaskiner. (PDF att läsa, bild 1, bild 2, bild 3) - F23 1 november
[SN] Oavgörbarhet. (Sup: 49-73)
- Ö8 2 november
Genomgång av lösning till mästarprov 1. Oavgörbarhet.
- Labb 3 3 november
Flöden och matchningar, redovisning.
- F24 8 november
[VK] Cooks sats. (PDF att läsa) -
F25 9 november kl 8
[VK] NP-fullständighetsbevis. (KT: 466-495)
- F26 9 november kl 9
[VK] NP-reduktionsvisualisering med Alvie.
I Alvie finns reduktioner för hörntäckning (Vertex Cover) och delmängdssumma (Subset Sum) 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 hörntäckning som Quicktime / mp4.
Visualisering av reduktionen av 3-CNFSAT till delmängdssumma som Quicktime / mp4.
- Ö9 10 november
NP-fullständighetsbevis. Teoriredovisning till labb 4.
- F27 16 november
[SN] NP-fullständighetsreduktioner. (KT: 459-463)
- F28 17 november
[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 18 november
NP-fullständiga problem.
- Labb 4 21 november
NP-fullständighetsreduktioner, redovisning.
- F29 22 november
[SN] Heuristiska algoritmer. Simulated annealing. (KTorig: 661-670/KTnie: 749-758) - F30 23 november
[VK] Approximationsalgoritmer. (KT: 599-630) - MAS2-övning 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.
- F31 29 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 2 på mästarprov 2. - Ö11 30 november
Approximationsalgoritmer. Teoriredovisning till labb 5. - F32 1 december
[VK] Komplexitetsklasser. (KT: 495-497, 531-547)
Genomgång av lydelsen till uppgift 3 på mästarprov 2. - F33 5 december
[VK] Repetition. Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination.
- Ö12 7 december
Komplexitetsklasser och repetition. - Mästarprov 2, senast 7 december klockan 19:00!
Uppgiftslydelsen publiceras i Canvas 23 november.Komplexitet. Muntliga redovisningar sker 12-16 december.
- Labb 5 9 december
Heuristik för rollbesättningsproblemet, redovisning.
- Extra labbredovisningstillfälle 13 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 Frodo. - Teoritenta 19 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 19 december och redovisas skriftligt 4 januari och muntligt 9-12 januari 2023.
- Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (övriga labbar kan inte redovisas), 10 januari 2023 kl 9-12. Bokningslistor publiceras i Canvas 31 december.
- Labbkursreflektion ska lämnas in senast 10 januari 2023.
- Frivillig munta för högre mästarprovsbetyg, 11 och 12 januari 2023. Anmälan görs under perioden 31 december 2022 till 5 januari 2023. Instruktioner om hur muntan genomförs och bokningslänk.
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å adk22.
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å adk22.
Den som har teoritentan kvar kan anmäla sig till och gå upp på omtentan 12 april 2023 kl 9-12 eller nästa ordinarietenta i december 2023.