Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximationsalgoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.

Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd, bloomfilter. Användning och implementation av datastrukturer. Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet.Ämnesterminologin på svenska och engelska.

Efter fullgjord kurs ska studenten kunna:

• utveckla och implementera algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet,
• jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet,
• definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet,
• jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,
• hantera problem med hög komplexitet

i syfte att

• självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne,
• i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Kursen består av 33 föreläsningar (F1-F33 nedan), 14 övningar (Ö1-Ö12 nedan, samt två övningsmästarprovsövningar) och 15 uppgifter som ska redovisas under kursens gång (i fetstil nedan).

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, som (tills annat meddelas) genomförs via Zoom: https://kth-se.zoom.us/j/66455760375
Om det i schemat står angivet en föreläsningssal är salen bokad och kan användas för att delta i föreläsningen via Zoom på egen dator.

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 kursöversikten i kursrummet finns länkar till föreläsningsbilder, övningsuppgifter och annat material. Det finns också länkar till 2020 års inspelningar av föreläsningarna.

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å videor ska ses och uppgifter ska göras före dessa föreläsningar. Första timmen på föreläsning 9, 10, 11 och 20 är avsatt för att du ska kunna göra förberedelserna.

• 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 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. (KTorig: 209-221/KTnie: 115-127)
  Effektiv kodning. och testning. Labbpartnermatchning i pausen.
• 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 3 september
• F4 6 september
  [SN] Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)
• F5 7 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 14 september
  [SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)
• F8 15 september
  [SN] Algoritmkonstruktion: dekomposition. (KTorig: 221-234, 242-246/KTnie: 127-140, 148-152)
• F9 16 september (OBS, omvänd föreläsning, förberedelse krävs!)
  [VK] Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-260)
  Första timmen: tid för att göra förberedelserna.
  Andra timmen: frågestund och arbete med uppgifter i grupp
• Ö3 16 september
  Dekomposition och dynamisk programmering.
• Labb 1 17 september
  Konkordans, redovisning.
• F10 20 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
• Dags att börja titta på övningsmästarprov 1!
• F11 22 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 arbetar med uppgifter i grupp
• Ö4 23 september
  Dynamisk programmering. Teoriredovisning för labb 2.
• F12 23 september
  [SN] Grafer: minimala spännande träd, kortaste stigar. (KTorig: 137-157/KTnie: 179-199)
• F13 28 september
  [VK] Grafer: demo av maximala flöden. (KT: 337-357, 367-373)
• MAS1-övning 28 september
  Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1, som publiceras denna dag.
• F14 29 september
  [VK] Undre gränser. (Sup: 17-29)
  Genomgång av delar av lydelsen till mästarprov 1.
• F15 30 september
  [SN] Algoritmkonstruktion: geometriska algoritmer, geomalgorithms.com, Grahamscan.
  Genomgång av resten av lydelsen till mästarprov 1.
• Ö5 30 september
  Grafalgoritmer och undre gränser.
• Labb 2 1 oktober
  Rättstavning, redovisning.
• F16 4 oktober kl 8
  [SN] Algoritmkonstruktion: sortering i linjär tid. Räknesortering och radixsortering. (Sup: 1-6)
  F17 4 oktober kl 9
  [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 6 oktober
  Teoriredovisning för labb 3.
• F19 11 oktober
  [SN] Probabilistiska algoritmer. (KTorig: 707-734, 769-776/KTnie: 661-688, 723-730)
• F20 13 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 13 oktober
  Probabilistiska algoritmer. Reduktioner.
• Mästarprov 1, senast tisdag 12 oktober klockan 13:00!
  Uppgiftslydelsen publiceras i Canvas 28 september.
  Muntliga redovisningar sker 18-22 oktober.
• F21 15 oktober OBS, omvänd föreläsning, förberedelse krävs!
  [SN] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)
  Förberedelserna ska göras före föreläsningen. Hela föreläsningen ägnas åt frågestund och arbete med uppgifter i grupp

Period 2

• F22 1 november
  [VK] Formella definitioner, turingmaskiner. (PDF att läsa)
• F23 2 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 14
  [VK] NP-fullständighetsbevis. (KT: 466-495)
• F26 9 november kl 15
  [VK] NP-reduktionsvisualisering med Alvie.
• Ö9 10 november
  NP-fullständighetsbevis. Teoriredovisning för 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!
• Ö10 17 november
  NP-fullständiga problem.
• Labb 4 22 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 24 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.
  Genomgång av delar av lydelsen till mästarprov 2.
• F32 30 november
  [VK] Komplexitetsklasser. (KT: 495-497, 531-547)
  Genomgång av resten av lydelsen till mästarprov 2.
• Ö11 1 december
  Teoriredovisning för labb 5.
• Mästarprov 2, senast 8 december klockan 17:00!
  Uppgiftslydelsen publiceras i Canvas 24 november.
  Muntliga redovisningar sker 13-17 december.
• F33 6 december
  [VK] Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination.
• Ö12 7 december
  Komplexitetsklasser och repetition.
• Mästarprov 2, senast 8 december klockan 17:00!
  Uppgiftslydelsen publiceras i Canvas 24 november.
  Muntliga redovisningar sker 13-17 december.
• Labb 5 10 december
  Heuristik för rollbesättningsproblemet, redovisning.
• Extra labbredovisningstillfälle 15 december för alla labbar, inklusive högrebetygslabben.
• Teoritenta 20 december klockan 9-12. Skrivtid 9:00-10:30 i Canvas. Obligatorisk rättningssession kl 11:00-12:00 i Zoom.

Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 20 december och redovisas skriftligt 4 januari och muntligt 7-11 januari 2022.

Frivillig munta för högre mästarprovsbetyg, 12 och 13 januari 2022. Muntan genomförs i Zoom. Anmälan görs under perioden 31 december 2021 till 6 januari 2022.

Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (inga andra labbar kan redovisas), 11 januari 2022 kl 9-12. Bokningslistor publiceras i Canvas 31 december.

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

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

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

För vissa av kursens labbar måste ett snabbare programspråk än Python användas, varför kunskaper i Java eller C/C++ rekommenderas.

Den som bara läst diskret matematik i SF1671 behöver läsa kursen SF1688 parallellt med DD2350. 

Sannolikhetsteori och statistik motsvarande SF1901 rekommenderas. Logik motsvarande DD1350/DD1351 rekommenderas men är inte nödvändigt.

• Algorithm Design av Kleinberg-Tardos, Pearson, 2014, ISBN 978-1292023946.

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

Om du har en funktionsnedsättning kan du få stöd via Funka:

Funka- stöd för studenter med funktionsnedsättningar

A, B, C, D, E, FX, F

• LAB1 - Laborationsuppgifter, 4,0 hp, Betygsskala: A, B, C, D, E, FX, F
• MAS1 - Individuellt mästarprov, 1,5 hp, Betygsskala: A, B, C, D, E, FX, F
• MAS2 - Individuellt mästarprov, 1,5 hp, Betygsskala: A, B, C, D, E, FX, F
• TEN1 - Teoritentamen, 2,5 hp, Betygsskala: P, F

Examinator beslutar, baserat på rekommendation från KTH:s samordnare för funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Kursens examination bygger helt på kursens målrelaterade betygskriterier, se nedan.

Identitetskontroll

Vid både labbredovisningar och mästarprovsredovisningar kommer vi att be dig visa legitimation så att vi är säkra på vem som examineras.

Laborationer

Fem obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. Labbarna ska göras i tvåpersonsgrupper, men enpersonsgrupper kan godkännas av kursledaren i undantagsfall. Den betygshöjande delen på labb 5 måste dock göras individuellt. Varje labb som redovisas och godkänns senast det labbtillfälle som finns angivet på labben ger en så kallad labbleveranspoäng. Den som fått 4-5 labbleveranspoäng (dvs har levererat minst fyra av labbarna i tid) får betyg C på momentet LAB1. Den som får 2-3 labbleveranspoäng får betyg D. Betyg C kan höjas till betyg A eller B med den betygshöjande extralabben som är en påbyggnad på labb 5, som ska göras och redovisas individuellt vid ett speciellt labbredovisningstillfälle i januari.

På varje labb finns dessutom frivilliga teoriuppgifter. Teoriuppgifterna redovisas skriftligt och muntligt på övningstillfällen (ingen annan möjlighet till redovisning ges) och ger en teoripoäng var, som ger bonus på tentorna under närmaste läsåret.

Det finns schemalagda labbtillfällen under hela kursen. Det kommer att finnas handledare tillgängliga på dessa labbpass. Börja att göra labbarna i god tid och fråga handledarna om du får problem. Du kan i princip redovisa alla labbarna vid alla labbtillfällen, men under det sista labbtillfället för varje labb, som är fyra timmar långt, prioriteras redovisningar av den labben.

Under Uppgifter i Canvaskursrummet ligger labbinstruktionerna.  Den som vill kan delta i labbarna på distans, se instruktionerna till första labben.

Individuella uppgifter: mästarprov

Två obligatoriska individuella uppgifter, mästarprov, kommer att ges. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas in i Canvas senast den tid som anges på uppgiftslydelsen. Den muntliga redovisningen, antingen i Zoom eller på campus, kommer att ske några dagar senare för någon av assistenterna på en tid som ska bokas i förväg i Canvas.

Varje mästarprov består av tre uppgifter av olika svårighetsgrad som testar betygskriterierna för E, C respektive A.

Inför varje mästarprov ges ett frivilligt övningsmästarprov som kan lösas i grupp och som redovisas vid speciella mästarprovsövningar, se detaljschemat. Godkänd redovisning av ett övningsmästarprov ger en teoripoäng. Totalt kan alltså två teoripoäng fås från mästarprovsövningar.

Den som inte godkänts på ett mästarprov får möjlighet att göra ett nytt i slutet av kursen, men kan då bara få betyg E på mästarprovet. Dessa ommästarprov läggs upp i Canvas i samband med ordinarie teoritentan och ska redovisas både skriftligt och muntligt i omtentaveckan i januari.

Teoritenta

Ordinarietentan går den 20 december klockan 9-12. Skrivtid 9:00-10:30. Obligatorisk rättningssession kl 11:00-12:00. Första omtentatillfälle är i påskperioden. 

Tentan (momentet TEN1) är en teoritenta som görs på distans i ett speciellt examinationsrum i Canvas (som kommer att vara tillgängligt för alla anmälda till tentan) och lämnas in i Peergrade. Alla hjälpmedel (som publicerats eller skrivits innan tentan börjar) är tillåtna. Under skrivtiden får tentanden inte kommunicera om tentan med någon annan än en lärare på kursen.

Tentans uppgifter är alla på E-nivå, dvs det går inte att få mer än godkänt på tentan. För godkänt krävs minst 13 av 14 poäng inklusive poäng på uppgifter som visar uppfyllelse av lärandemålet definiera och översätta centrala begrepp. Den som får 11 eller 12 poäng eller som får minst 13 poäng men har missat måluppfyllelsen får möjlighet att muntligt komplettera till godkänt. Teoripoängen som samlats genom labbteoriredovisningar (upp till 5 teoripoäng) och övningsmästarprov (upp till 2 teoripoäng) läggs till poängen på teoritentan på alla tentor inom ett år från kursstart.

Teoritentans uppgifter testar följande betygskriterier på nivå E:

• analysera algoritmer med avseende på effektivitet: förklara principerna, analysera enklare algoritmer
• jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet
• definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet
• jämföra problem med hänsyn till komplexitet med hjälp av reduktioner: förklara principerna
• förklara hur man kan hantera problem med hög komplexitet: förklara principerna

Vi rekommenderar alla att titta på senaste årens extentor för att bättre förstå hur uppgifterna kan se ut. Lösningsförslag finns bara till ordinarietentorna. Notera att på tentorna för kurskoden DD1352 är det bara E-uppgifterna som motsvarar uppgifter på teoritentan för DD2350. Det finns ett övningsquiz på begrepp och definitioner inför teoritentan.

Skrivtiden är 90 minuter. Direkt efter tentan vidtar en obligatorisk genomgång, i Zoom, av lösningarna till tentan och kamraträttning. Rättningen kontrolleras sedan av lärarna och resultatet kungörs förhoppningsvis samma dag. Klagomål på rättning av tentan görs till kursledaren. Kursledaren avgör hur och när kompletteringsuppgifter ska redovisas.

Tentaanmälan ska göras som vanligt.

Varför kamraträttning?

• Det är bra för lärandet att få återkoppling i direkt anslutning till examinationen.

• Att sätta sig in i någon annans lösningar och tankesätt är lärorikt.

• Du får insikt i hur bedömning av tentor går till och vilka överväganden rättande lärare behöver göra.

• Betygsättningen snabbas upp. Resultatet är klart samma dag!

Att tänka på vid kamraträttningen

• Rättningssessionen är en obligatorisk del av tentan och närvaron kontrolleras i Zoom.

• Du bedömer en annan students arbete. Var och en förtjänar en korrekt bedömning. Följ därför rättningsmallen och rättningsanvisningarna så gott du kan.

• Om du är osäker på bedömningen av en uppgift går det bra att fråga. Om du fortfarande är osäker efter frågestunden kan du ange att du är osäker på bedömningen.

• Var saklig och professionell. Gör inte narr av en lösning och skratta inte åt en lösning eller någon annans fråga under kamraträttningssessionen.

Muntlig tenta och slutbetyg

Den som fått godkänt på labbarna, båda mästarproven och teoritentan får godkänt på kursen. Slutbetyget bestäms som ett oviktat genomsnitt av betygen på samtliga tre betygsatta moment (MAS1, MAS2, LAB1), eventuellt kompletterat med en muntlig tenta och/eller en högrebetygslabb, se betygskriterierna nedan.

Exempel: 

Den som är godkänd på båda mästarproven och har fått minst betyg C på det ena (eller har klarat E- och A-uppgifterna på mästarprov 2) har möjlighet att gå upp på en muntlig tenta för att få högre betyg på mästarproven. Den muntliga tentan kan efter teoritentan bokas in (i Canvas) på tider i tentaveckan i januari 2021. Vid den muntliga tentan kommer läraren att kontrollera att du uppfyller betygskriterierna för det betyg du aspirerar på. Kursböckerna (men inga kompendier eller anteckningar) är tillåtna hjälpmedel.

Restmoment

Läs denna sida om du har uppgifter kvar att redovisa efter kursens slut.

Arbetssituationer

Det är meningen att arbetet med momenten i kursen ska motsvara olika arbetssituationer i arbetslivet.

Labbarna tränar olika typer av programutvecklingsarbete:

• I labb 1 ska du programmera efter en funktionsspecifikation.
• I labb 2 ska du programmera om ett existerande program så att det fungerar likadant fast effektivare.
• I labb 3 ska du programmera efter en detaljerad algoritmisk specifikation.
• I labb 5 ska du attackera ett problem som inte kan lösas optimalt.

I alla labbar finns noggranna beskrivningar av format för indata och utdata. Alla labbar har givna effektivitetskrav och utförs som lagarbete (labbgrupper), precis som i arbetslivets agila parprogrammeringsprojekt. I labb 1 är parprogrammering obligatoriskt att använda.

Mästarproven tränar expertsituationen, alltså situationen som den som vet mest om något på en arbetsplats ställs inför när hen får ett problem: det finns ingen att fråga, så hen måste komma fram till svaret med egen tankekraft och genom att läsa litteratur. När problemet är löst ska experten förklara lösningen för chefen, både skriftligt och muntligt.

Tentan liknar tyvärr ingen verklig arbetssituation, men den följs av en kamraträttningssession som är mycket värdefull ur ett pedagogiskt perspektiv. Labb 4 har också en konstruerad arbetssituation; den är dock mycket värdefull för begreppsförståelsen.

Betyget Fx kan kompletteras till E/godkänt för momenten MAS1, MAS2 och TEN1. Enskilda laborationer kan tillgodoräknas senare kursomgångar så länge laborationsuppgiften är oförändrad. Till kursomgången hösten 2021 ändrades labb 1 och labb 2.

Mästarprovsbetygen (MAS1 och MAS2) kan plussas i en senare kursomgång. Det är också tillåtet att plussa betyget på LAB1 från C eller B med den betygshöjande labben i en senare kursomgång. Däremot går det inte att få nya labbleveranspoäng i en senare kursomgång.

Du kan se dina resultat på redovisade uppgifter i kursen under Omdömen i Canvas. Resultatet ska normalt läggas in senast en vecka efter redovisningen. För labbteoriuppgifterna kan det ta något längre tid.

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Hederskodex

I denna kurs tillämpas EECS hederskodex, se: http://www.kth.se/eecs/utbildning/hederskodex

Den som vid kursstart inte har slutfört 7,5 hp diskret matematik motsvarande SF1610/SF1630/SF1662/SF1679 måste läsa SF1688 parallellt med DD2350.

Nästan alla föreslagna förändringar i senaste kursanalysen har genomförts. Majoriteten av förändringarna baseras på studentsynpunkter och studentförslag. Sedan föregående kursomgång, adk20, har följande ändrats:

• Ny större textfil att söka i till labb 1.
• Stöd för testning har lagts in i den givna programkoden för labb 2.
• Instruktionerna till extralabben tydliggör vad som menas med lokalsökning och simulerad härdning.
• Labbredovisningar och mästarprovsredovisningar erbjuds både fysiskt och digitalt.
• Olika långa mästarprovsredovisningar beroende på hur många uppgifter som ska redovisas.
• Nya tentaförberedelsequizfrågor som övar på vad som är en godkänd definition och vad som är en övertygande motivering (med kryssfrågor).
• På föreläsningar och övningar påminns om att ADK-kursens fokus inte är programmering utan teoretisk algoritmdesign.
• Att kommunikation i första hand ska ske genom diskussionsforumet i Canvas ska kommuniceras tydligt.
• Nya videor och instuderingsfrågor till omvända föreläsningarna om reduktioner och intro till komplexitet.
• En ny text om formulering av bevis för reduktioner tas fram.
• Se om det går att ta upp pseudopolynomi så att ingen råkar utforma pseudopolynomiska algoritmer i tron att dessa är polynomiska.
• Lägg till exempel på när stopproblemet inte är svårt och när det kan vara svårt.
• En timme före varje omvänd föreläsning har lagts in, då studenter kan titta på videor och göra förberedelseuppgifter.