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, beständiga datastrukturer. 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 godkänd 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 och därmed kan bidra till ekonomiskt och miljömässigt hållbar utveckling
• i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

2024 årskursomgång, som har kortbeteckningen adk24, 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 par tillfällen två entimmesföreläsningar kommit att hamna direkt efter varandra). Viggo Kann [VK] och Douglas Wikström [DW] delar på föreläsningarna. Tomas Ekholm [TE] håller en gästföreläsning.

I kursöversikten i kursrummet finns detaljplaneringen för alla aktiviteter i kursen med länkar till föreläsningsbilder, övningsuppgifter och annat material. 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 kursrummet 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å dessa föreläsningar är avsatt för att du ska kunna göra förberedelserna.

För labb 2 behövs vissa kunskaper i Javaprogrammering. För några av kursens labbar behöver ett snabbare programspråk än Python användas, till exempel Java eller C/C++.

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

Kunskaper i diskret matematik är nödvändigt. 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, se under övriga föreskrifter i kursplanen.

• Algorithm Design av Kleinberg-Tardos, Pearson, 2014, ISBN 978-1292023946. Gamla upplagan från 2005, ISBN 978-0321372918 eller 978-0321295354, går också bra. Boken kan också köpas eller hyras från förlaget (en 20%-rabattkod publiceras i ett anslag i kursrummet vid kursstart).

• Det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126. Finns bara som fysisk bok och 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 handläggare av stöd till studenter med 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.

Betyget på LAB1 beror på hur många datorlabbar som redovisas muntligt inom angiven tid.

Mästarproven utgörs av individuella uppgifter som redovisas både skriftligt och muntligt.

Frivilliga teoriuppgifter med kamratbedömning ger bonuspoäng till teoritentamen. 
Teoritentamen genomförs som ett digitalt quiz med efterföljande kamraträttning.

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 av två särskilda labbredovisningstillfällen i december och 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 läggs till tentapoängen på tentorna under närmaste läsåret. Under övningstillfället tillämpas kamraträttning, men det är en assistent som avgör om inlämningen är godkänd eller inte.

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.

Efter att du har redovisat alla labbarna ska du avsluta labbkursen med att lämna in en kort reflektion över vad du har lärt dig i kursen.

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.

Mästarprov 1 motsvarar momentet MAS1 och mästarprov 2 motsvarar momentet MAS2. 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 19 december 2024 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. Syftet med detta är att examinera kursens teoridel både genom teoriuppgifterna under kursens gång samt med den avslutande teoritentan.

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 samt ett övningsquiz på motiveringar av påståenden.

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 genomförs i tentaveckan i januari, se schemat. Bokningslistor kommer att publiceras i Canvas vid årsskiftet. 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.

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.

Generativa AI-verktyg

Generativa AI-verktyg är kraftfulla verktyg som rätt använda kan hjälpa dig att lära dig effektivare. Använd inte AI om det minskar ditt eget lärande. Kontrollera i uppgiftsinstruktioner om och hur du får använda generativ AI. Lita inte på att AI-genererad text är korrekt.

Om du använt generativ AI för att generera programkod eller text i en labb eller ett mästarprov måste du redovisa det. Du får inte använda generativ AI för att lösa mästarprovsuppgifter eller tentauppgifter. Däremot får du gärna använda generativ AI för att typsätta med LaTeX, be om förklaringar eller ta fram exempel och övningsuppgifter.

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.

Sedan föregående kursomgång, adk23, har följande ändrats:

• Gå igenom Kattis felmeddelanden i labb 2-5 och förtydliga dom som är otydliga. Tipsa om Kattissystemets egna hjälptexter.
• Förtydliga i kursplanen att betyget på labbkursen beror på hur många labbar som redovisas inom angiven tid.
• Ta fram kursmaterial som förklarar matematisk notation som används i kursen, såsom max, min och mängdnotation.
• Använd genomgående termen certifikat istället för lösning i samband med NP-verifikation.
• Ändra schemaläggningen så att mer tid ges till labb 1.
• Numrera övningsuppgifterna.
• Försök göra arbetsmiljön vid labbteoriredovisningarna bättre genom att sprida ut redovisningarna över en större yta.
• Gör ett inledande diskussionsinlägg i kursrummet om hur diskussionsforumet är tänkt att användas i kursen.
• Spara resurser genom att bara hålla tre övningsgrupper istället för fyra vid dom övningspass som inte har labbteoriredovisningar.