Kursöversikt
Viggo Kann [VK] och Per Austrin [PA] delar på föreläsningarna. Tomas Ekholm [TE] ger 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äsningsbilderna kommer i många fall att uppdateras under kursens gång.
Föreläsning 9-11 om dynamisk programmering samt föreläsning 19 om reduktioner 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
| Bilder | Datum | Lärare | Innehåll | Läsanvisning |
Mer material |
| F1 | 25 augusti (2 timmar) | VK+PA | Introduktion till kursen. Repetition av algoritmanalys. Beräkningsmodeller, bitkostnad, enhetskostnad. | KT: 29-56 | |
| F2 | 27 augusti (2 timmar) | PA | Mästarsatsen. Repetition av sorteringsalgoritmer och datastrukturer. Labbpartnermatchning i pausen. |
KTorig: 209-221/KTnie: 115-127, KT: 57-65 |
|
| F3 | 28 augusti (2 timmar) | VK+TE | Praktiska datastrukturer. Beständiga datastrukturer. Labbpartnermatchning i pausen. |
Sup: 77-83, beständiga datastrukturer, |
|
| Ö1 | 29 augusti | 4 grupper | Algoritmanalys | ||
| F4 | 1 september | PA |
Grafer: djupetförstsökning, breddenförstsökning |
KT: 73-107 | |
| Ö2 | 2 september | 4 grupper |
Datastrukturer och grafer. Teoriredovisning till labb 1. |
||
| F5 | 3 september | VK | Datastrukturer: bloomfilter. Tillämpning: rättstavning | ||
| F6 | 4 september | PA | Korrekthetsbevis | ||
| F7 | 9 september | VK | Algoritmkonstruktion: giriga algoritmer, totalsökning. | Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230 | |
| F8 | 10 september | PA | Algoritmkonstruktion: dekomposition. | KTorig: 221-234, 242-246/KTnie: 127-140, 148-152 | |
| 11 september | VK | Algoritmkonstruktion: dynamisk programmering, del 1. Omvänd föreläsning! |
KT: 251-260 | Fibonaccitalen | |
| Ö3 | 11 september | 3 grupper | Dekomposition och dynamisk programmering. | ||
| Labb 1 | 12 september | Redovisning av labb 1: Beständig array | |||
| F10 Förberedelse krävs |
15 september | VK |
Algoritmkonstruktion: dynamisk programmering, del 2. |
KT: 261-290 |
Dags att börja titta på övningsmästarprov 1! |
| Ö4 | 16 september | 4 grupper |
Dynamisk programmering. Teoriredovisning till labb 2. |
||
| F11 Förberedelse krävs |
17 september | VK |
Dynamisk programmering, del 3: konstruktion av lösning och motivering av korrekthet. Första timmen: tid för att göra förberedelserna. |
KT: 290-301, 307-311 | |
| F12 | 18 september | PA |
Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra) |
KTorig: 137-157/KTnie: 179-199 | |
| F13 | 23 september | VK |
Grafer: maximala flöden |
KT: 337-357, 367-373 |
demo av maximala flöden. Extra föreläsningsbilder från en kurs på Princeton |
| Ö-MAS1 | 23 september | 4 grupper (ev en grupp i Zoom) |
Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1, som publiceras kl 8:00 den 24 september. |
||
| F14 | 24 september | VK |
Undre gränser. Genomgång av lydelsen till uppgift 1 på mästarprov 1. |
Sup: 17-29 | |
| F15 | 25 september | PA |
Algoritmkonstruktion: geometriska algoritmer. |
geomalgorithms.com, Grahamscan: beskrivning, animering |
|
| Ö5 | 25 september | 3 grupper |
Grafalgoritmer och undre gränser |
||
| Labb 2 | 26 september |
Redovisning av labb 2: Rättstavning. |
|||
| F16 | 29 septmber | PA |
Algoritmkonstruktion: sortering i linjär tid |
Sup: 1-6 | Räknesortering och radixsortering |
| F17 | 30 september | PA |
Algoritmkonstruktion: textsökning |
Sup: 7-16, Pythonkramaren II: 46-48 |
|
| Ö6 | 1 oktober | 4 grupper |
Algoritmkonstruktion. Teoriredovisning till labb 3 |
Sammanfattning av alla algoritmer hittills i kursen | |
| F18 | 6 oktober | PA |
Probabilistiska algoritmer |
KTorig: 707-734, 769-776/KTnie: 661-688, 723-730 |
Lasvegas- och Montecarloalgoritmer, Probabilistisk algoritm för medianproblemet |
| F19 Förberedelse krävs |
7 oktober | PA |
Reduktioner. Första timmen: tid för att göra förberedelserna. |
KT: 451-459 | |
| Ö7 | 8 oktober | 3 grupper |
Probabilistiska algoritmer. Reduktioner. |
||
| F20 | 10 oktober | PA |
Kryptografi |
||
| Mästarprov 1 | Inlämning senast 13 oktober kl 19 |
Algoritmkonstruktion. Uppgiftslydelsen publiceras i Canvas 24 september. |
Period 2
| F21 | 27 oktober | PA | Introduktion till komplexitet | KT: 463-466 hela sidan | motivering |
| F22 | 28 oktober | VK | Formella definitioner | ||
| F23 | 29 oktober | PA | Oavgörbarhet | Sup: 49-73 | |
| Ö8 | 30 oktober |
Genomgång av lösning till mästarprov 1. Oavgörbarhet. |
|||
| Labb 3 | 31 oktober | Redovisning av labb 3: Flöden och matchningar | |||
| F24 | 3 november | VK | Cooks sats. | PDF att läsa | |
| Ö9 | 3 november | 4 grupper |
NP-fullständighetsbevis. Teoriredovisning till labb 4. |
||
| F25 | 6 november kl 14 | VK | NP-fullständighetsbevis | KT: 466-495 | |
| F26 | 6 november kl 15 | VK |
NP-reduktionsvisualisering med Alvie. |
Ladda ner Alviekällkoden själv och kompilera. Visualisering av reduktion av 3-CNFSAT till hörntäckning som mp4. Visualisering av reduktion av 3-CNFSAT till delmängdssumma som mp4. |
|
| F27 | 11 november | PA | NP-fullständighetsreduktioner. | KT: 459-463 | Manuskript från 2024 |
| F28 | 12 november | VK | Mer NP-fullständighetsreduktioner. | KT: 497-505 |
Fördjupning: Math has a fatal flaw - en film om ofullständighet och oavgörbarhet |
| Ö10 | 13 november | NP-fullständiga problem. | Dags att börja titta på övningsmästarprov 2! | ||
| Labb 4 | 14 november | Redovisning av labb 4: NP-fullständighetsreduktioner - Rollbesättning | |||
| F29 | 17 november | PA | Heuristiska algoritmer | KTorig: 661-670/KTnie: 749-758 | |
| Ö-MAS2 | 19 november | 4 grupper (ev en grupp i Zoom) |
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. |
||
| F30 | 20 november | VK |
Approximationsalgoritmer. |
KT: 599-630 | |
| F31 | 24 november | VK |
Mer approximationsalgoritmer. |
webbsida om Christofides algoritm, Viggos lista med approximationsresultat för NP-svåra optimeringsproblem |
|
| Ö11 | 25 november | 4 grupper |
Approximationsalgoritmer. Teoriredovisning till labb 5.
|
||
| F32 | 26 november | VK |
Komplexitetsklasser. |
KT: 495-497, 531-547 | |
| F33 | 3 december | VK |
Repetition. Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination. |
||
| Mästarprov 2 | Inlämning senast 3 december kl 19:00 |
Komplexitet. Uppgiftslydelsen publiceras i Canvas 19 november klockan 12:00. |
|||
| Ö12 | 4 december | 3 grupper |
Komplexitetsklasser och repetition. |
||
| Labb 5 | 5 december |
Redovisning av labb 5: Heuristik för rollbesättningsproblemet |
|||
| Restlabbs- redovisning | 12 december |
Extra labbredovisningstillfälle för alla labbar, inklusive högrebetygslabben. |
|||
| Teoritenta | 17 december kl 9:00-12:00 |
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. |
2026
| Ommästarprov | Inlämning senast 2 januari kl 19:00 |
Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 17 december. Muntliga redovisningar sker 5-7 januari. |
| Betygshöjande extralabb | 5 januari kl 9-12 |
Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (övriga labbar kan inte redovisas) . Bokningslistor publiceras i Canvas 31 december. |
| Labbkursreflektion |
Inlämning senast 8 januari för rapportering i Ladok vecka 2. |
|
| Frivillig munta | 8 och 9 januari |
Frivillig munta för höjning av mästarprovsbetyg, Anmälan görs under perioden 31 december till 5 januari. 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å adk25. Labbkursreflektionen lämnar du in i kursrummet för adk25 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 2026 eller nästa ordinarietenta i december 2026.