Kurs-PM för DD1352 adk16

Lärare Kursledare och föreläsare är Viggo Kann, viggo@csc.kth.se och Stefan Nilsson snilsson@csc.kth.se

Det står var och en fritt att välja övningsgrupp eller byta grupp under kursens gång. Övningsassistenter är:

* Emma Nimstad, normalsvår grupp
* Marcus Dicander, lite svårare grupp
* Susanna De Rezende, lite enklare grupp på engelska
Det finns också ett antal ytterligare personer som är labbhandledare och tar emot mästarprovsredovisningar.

Kurslitteratur Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet.

Kursböcker
* Algorithm Design av Kleinberg-Tardos, Pearson, 2014 med ISBN 978-1292023946. Gamla upplagan från 2005, ISBN 978-0321372918 eller 978-0321295354, går också bra.

* Det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126. Säljs bara på kårbokhandeln.

Dessa kan köpas i ett inplastat bokpaket på kårbokhandeln för 670 kronor. Supplementet kan även köpas löst för 120 kronor.

Funktionsnedsättning Om du har en funktionsnedsättning kan du få stöd via Funka:https://www.kth.se/student/studentliv/funktionsnedsattningInformera dessutom kursledaren om du har särskilda behov. Visa då upp intyg från Funka.

Kursens pedagogiska upplägg
* Studera på det sätt som är effektivast för dej! 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!
* Övningsuppgifter med fullständiga lösningar. Övningsgrupper med svårighetsgradering.
* Momenten i kursen tränar verkliga arbetssituationer för bättre autenticitet.
* Aktiverande färgfrågor på föreläsningarna och kontinuerlig examination med labbteoriuppgiftredovisning 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 12 ö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 fem tillfällen 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.

Undervisning, redovisningar och läsanvisningar
* KT=Kleinberg-Tardos,
* 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 31 augusti (2 timmar) [SN+VK] Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)

* F2 1 september(2 timmar) [SN] Repetition av sortering (animering 1, animering 2). (KTorig: 209-221/KTnie: 115-127)Effektiv kodning och avlusning. Se även Diverse länkar i kurswebbens vänstermeny.

* F3 2 september (2 timmar) [VK] Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (KT: 57-65) Latmanshashning, skipplistor. (Sup: 77-83)

* Ö1 2 september Algoritmanalys.

* F4 5 september [SN] Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)

* F5 6 september [VK] Datastrukturer: bloomfilter. Tillämpning: rättstavning.

* F6 8 september [SN] Korrekthetsbevis.

* Ö2 9 september Datastrukturer och grafer. Teoriredovisning för labb 1.

* F7 13 september kl 13 [SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)

* F8 13 september kl 14 [SN] Algoritmkonstruktion: dekomposition. (KTorig: 221-234, 242-246/KTnie: 127-140, 148-152)

* F9 14 september [VK] Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-260) Visualiseringar: Fibonaccitalen.

* Ö3 15 september Dekomposition och dynamisk programmering.

* Labb 1 16 september Konkordans, redovisning.

* F10 19 september kl 10 [VK] Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 261-290)

* F11 19 september kl 11 [VK] Exempel på motivering av korrekthet: dynamisk programmering. (KT: 290-301, 307-311)

* Ö4 20 september Dynamisk programmering. Teoriredovisning för labb 2.

* F12 21 september [SN] Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KTorig: 137-157/KTnie: 179-199)

* F13 26 september[VK] Grafer: maximala flöden. Lecture notes (Princeton) (KT: 337-357, 367-373)

* F14 26 september [VK] Undre gränser. (Sup: 17-29)

* F15 28 september [SN] Algoritmkonstruktion: geometriska algoritmer. (Grahamscan: beskrivning, animering)

* Ö5 29 september Grafalgoritmer och undre gränser.

* Labb 2 30 september Rättstavning, redovisning.

* F16 4 oktober [SN] Algoritmkonstruktion: sortering i linjär tid. Räknesortering och radixsortering.. (Sup: 1-6)

* F17 4 oktober [SN] Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)

* F18 5 oktober [SN] Algoritmkonstruktion: polynomberäkningar och FFT. (KTorig: 234-242/KTnie: 140-148)

* Ö6 7 oktober Algoritmkonstruktion. Teoriredovisning för 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)

* Mästarprov 1, senast måndag 10 oktober klockan 15.15!Uppgiftslydelsen läggs upp på mästarprovssidan på kurswebben 26 september. Algoritmer. Muntliga redovisningar sker 14-20 oktober.

* F20 11 oktober [SN] Reduktioner. (KT: 451-459)

* Ö7 11 oktober Probabilistiska algoritmer. Reduktioner.

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

Period 2

* F22 31 oktober [VK] Formella definitioner, turingmaskiner. (PDF att läsa)

* F23 1 november [SN] Oavgörbarhet. (Sup: 49-73)

* Ö8 3 november Genomgång av lösning till mästarprov 1. Oavgörbarhet.

* Labb 3 4 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 (instruktioner).I Alvie finns reduktioner för delmängdssumma (Subset Sum) och hörntäckning (Vertex Cover) 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.

* Ö9 10 november NP-fullständighetsbevis. Teoriredovisning för labb 4.

* F27 15 november [SN] NP-fullständighetsreduktioner. (KT: 459-463)

* F28 16 november [VK] Mer NP-fullständighetsreduktioner. (KT: 497-505)

* Ö10 16 november NP-fullständiga problem.

* Labb 4 18 november NP-fullständighetsreduktioner, redovisning.

* F29 22 november [VK] Approximationsalgoritmer. (KT: 599-630)

* F30 23 november [VK] Mer approximationsalgoritmer. (webbsida om Christofides algoritm)

* Ö11 24 november Approximationsalgoritmer

* F31 28 november [SN] Heuristiska algoritmer. Simulated annealing. (KTorig: 661-670/KTnie: 749-758)

* F32 30 november [VK] Komplexitetsklasser. (KT: 495-497, 531-547)

* Mästarprov 2, senast 6 december klockan 12.15!Uppgiftslydelsen läggs upp på mästarprovssidan på kurswebben senast 22 november. Komplexitet. Muntliga redovisningar sker 9-15 december.

* F33 6 december [SN+VK] Repetition. Kursens betygssystem.

* Ö12 8 december Komplexitetsklasser och repetition.

* Extra labbredovisningstillfälle 13 december kl 13-15.

* Teoritenta 19 december klockan 9-12 i sal D1 och F2.
* Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.

* Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, i Spel- och Sporthallen 10 januari 2017 kl 14-17. I mån av tid kan också övriga labbar redovisas då. Ingen anmälan.

* Frivillig munta för högre betyg, 10-12 januari 2017. Anmälan ska göras senast 6 januari 2017 på kurswebben.
Examination Fyra labbar, två mästarprov och teoritenta krävs för godkänt. Betygsättningen är målrelaterad, se betygskriterierna på nästa sida. Alla resultat rapporteras i Rapp. För mer information om examinationen, se kurswebbens examinationssida.