Skip to main content

DD2350 Algoritmer, datastrukturer och komplexitet 9.5 credits

Kurs-PM HT 2022-52200

Version 2 – 2022-10-31 09:24:53

Kursomgång

adk22 (Startdatum 2022-08-29, Svenska)

Undervisningsspråk

Svenska

Kursen ges av

EECS/Datavetenskap

Kurs-PM HT 2022

Presentation av kursen

Denna kurs ger en introduktion till teoretisk datalogi som är ett starkt forskningsområde på KTH. Du kommer att stöta på några av våra forskningsresultat i kursen.

Du får lära dig mer om algoritmkonstruktion och får se några ganska komplicerade, men mycket användbara, algoritmer. Komplexitetsdelen av kursen handlar om hur man undersöker vilka problem som kan lösas (i rimlig tid) med datorns hjälp, vilka som tar orimligt lång tid och vilka som inte kan lösas med en dator över huvud taget.

Problem som är för svåra för att lösa exakt kan ibland lösas approximativt. Du kommer att få se exempel på några approximationsalgoritmer och några problem som är så svåra att dom inte ens kan approximeras i rimlig tid.

Rubriker markerade med en asterisk ( * ) kommer från kursplan version HT 2022

Innehåll och lärandemål

Kursinnehåll

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.

Lärandemål

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.

Läraktiviteter

2022 årskursomgång, som har kortbeteckningen adk22, 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.

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å dessa föreläsningar är avsatt för att du ska kunna göra förberedelserna.

Detaljplanering

  • 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)
  • 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 2 september
  • F4 5 september
    [VK] Datastrukturer: bloomfilter. Tillämpning: rättstavning.
  • F5 6 september
    [SN] Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)
  • F6 7 september
    [SN] Korrekthetsbevis.
  • Ö2 8 september
    Datastrukturer och grafer. Teoriredovisning för 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)
    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 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.
  • 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 arbetar med uppgifter i grupp.
  • F12 21 september
    [SN] Grafer: minimala spännande träd, kortaste stigar. (KTorig: 137-157/KTnie: 179-199)
  • Ö4 22 september
    Dynamisk programmering. Teoriredovisning för labb 2.
  • F13 27 september
    [VK] Grafer: demo av maximala flöden. (KT: 337-357, 367-373)
  • MAS1-övning 27 september
    Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1, som publiceras denna dag.
  • F14 28 september
    [VK] Undre gränser. (Sup: 17-29)
  • F15 29 september
    [SN] Algoritmkonstruktion: geometriska algoritmer, geomalgorithms.com, Grahamscan.
  • Ö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)
    F17 3 oktober kl 11
    [SN] Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48 )
  • F18 5 oktober
    [SN] Beständiga datastrukturer
  • Ö6 6 oktober
    Teoriredovisning för labb 3.
  • F19 10 oktober
    [SN] Probabilistiska algoritmer. (KTorig: 707-734, 769-776/KTnie: 661-688, 723-730)
  • F20 11 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 12 oktober
    Probabilistiska algoritmer. Reduktioner.
  • Mästarprov 1, senast tisdag 18 oktober klockan 18:00
    Uppgiftslydelsen publiceras i Canvas 27 september.
    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)
  • 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.
  • Ö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 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.
    Genomgång av delar av lydelsen till mästarprov 2.
  • Ö11 30 november
    Teoriredovisning för labb 5.
  • F32 1 december
    [VK] Komplexitetsklasser. (KT: 495-497, 531-547)
    Genomgång av resten av lydelsen till mästarprov 2.
  • F33 5 december
    [VK] Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination.
  • Ö12 7 december
    Komplexitetsklasser och repetition.
  • Mästarprov 2, senast 7 december klockan 17:00!
    Uppgiftslydelsen publiceras i Canvas 23 november.
    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.
  • 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.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt 4 januari och muntligt 9-11 januari 2023.
  • Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (inga andra labbar kan 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.

 

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 tentan kvar kan gå upp på omtentan i april 2023 eller nästa ordinarietenta i december 2023.

Kursens pedagogiska upplägg

  • Studera på det sätt som är effektivast för dig! Allt föreläsnings- och övningsmaterial finns tillgängligt i förväg. Vår erfarenhet visar dock att det oftast sparar tid att delta i undervisningen.
  • Koncentrerade entimmesföreläsningar med läsanvisningar. Kom förberedd och var vaken för bästa resultat! I vissa avsnitt av kursen används omvänd undervisning (flipped classroom).
  • Övningsuppgifter med fullständiga lösningar. Övningsgrupper med svårighetsgradering. Ett urval av uppgifterna löses på övningarna, resten lämnas för egen övning.
  • Momenten i kursen tränar verkliga arbetssituationer för bättre autenticitet.
  • Aktiverande färgfrågor på föreläsningarna och kontinuerlig examination med labbteoriuppgiftsredovisning inför varje datorlabb gör att du automatiskt hänger med i kursen.
  • Du förbereds väl för mästarproven med övningsmästarprov, bedömningskriterier och autentiska exempel på tidigare studentinlämningar med kommentarer.
  • 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.

Nyckelbegrepp

Här är 50 facktermer i ADK-kursen som inte har en uppenbar direktöversättning.

Svensk term Engelsk term
algoritm algorithm
approximationskvot approximation ratio
approximerbarhet approximability
beräkningsbarhet computability
beräkningsmodell computational model
beslutsproblem decision problem
beständig datastruktur persistent data structure
bitkostnad bit cost
datastruktur data structure
dekomposition divide and conquer
delmängdssumma subset sum
dynamisk programmering dynamic programming
enhetskostnad unit cost
förberäknad (funktion) precomputed (function)
girig algoritm greedy algorithm
grafgenomgång graph traversal
grannlista adjacency list
grannmatris adjacency matrix
heuristik heuristics
hörn vertex
ickedeterministisk non-deterministic
kant edge
kantmatris incidence matrix
komplexitet complexity
konjunktiv normalform conjunctive normal form
konstruktionsproblem construction problem
källa source
latmanshashning lazy hashing (ingen standardterm)
målfunktion objective function
mängdpartitionering partition problem
mästarsatsen Master theorem
NP-fullständig NP-complete
oavgörbar undecidable
oberoende mängd independent set
optimeringsproblem optimization problem
polynomisk reduktion polynomial reduction
polynomisk tid polynomial time
prioritetskö priority queue
probleminstans problem instance
rekursivt uppräknelig recursively enumerable
restkapacitet residual capacity
rimlig tid feasible time
räknesortering counting sort
satisfierbar satisfiable
simulerad härdning simulated annealing
slumpeliminering derandomization
spännande träd spanning tree
totalsökning exhaustive search
tuff motståndare adversary
undre gräns lower bound
utlopp sink
verifierbar verifiable
övre gräns upper bound

Förberedelser inför kursstart

Rekommenderade förkunskaper

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.

Kurslitteratur

  • 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.

Examination och slutförande

Betygsskala

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

Examination

  • 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.

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

Avsnittet nedan kommer inte från kursplanen:

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 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: 

betyg på MAS1, MAS2, LAB1 ger slutbetyg
E, E, C D
E, C, B C
C, A, A B

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 2023, 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.

Målrelaterade betygskriterier/bedömningskriterier

mål E D C B A
utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod för icketriviala problem givet ledtråd för icketriviala problem [A-kriteriet] givet ledtråd för svårare problem med den metod som passar bäst
examineras med labbar (för nivå E), mästarprov 1 och muntlig tenta
implementera algoritmer med datastrukturer efter funktionsspecifikation och efter detaljerad algoritmisk specifikation, med hänsyn taget till effektivitet med vissa krav på leveranstid med höga krav på leveranstid
examineras med labbar
analysera algoritmer med avseende på effektivitet förklara principerna, analysera enklare algoritmer analysera svårare algoritmer givet ledtråd analysera svårare algoritmer
examineras med labbar och teoritenta (för nivå E), mästarprov 1 och muntlig tenta
analysera algoritmer med avseende på korrekthet förklara principerna, förklara ett givet korrekthetsbevis framställa grundläggande idé för korrekthetsbevis framställa grundläggande idé och givet ledtråd genomföra fullständiga korrekthetsbevis [A-kriteriet] givet ledtråd genomföra fullständiga korrekthetsbevis med invarianter
examineras med mästarprov och muntlig tenta
jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet 
examineras med labbar, teoritenta och mästarprov 1
definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet 
examineras med teoritenta och mästarprov 2
jämföra problem med hänsyn till komplexitet med hjälp av reduktioner förklara principerna, utföra enklare reduktioner mellan givna problem [C-kriteriet] givet ledtråd visa NP-fullständighet eller oavgörbarhet [A-kriteriet] givet ledtråd utföra konstruktions- reduktioner
examineras med teoritenta och labb 4 (för nivå E), mästarprov 2 och muntlig tenta
förklara hur man kan hantera problem med hög komplexitet

förklara principerna,

konstruera enkla heuristiker

konstruera och analysera heuristiker konstruera och analysera mer avancerade heuristiker
examineras med teoritenta och labb 5 (för nivå E) och betygshöjande extralabb (för A och B)

 

Möjlighet till komplettering

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öjlighet till plussning

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.

Resultatrapportering

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.

Etiskt förhållningssätt

  • 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.

Ytterligare Information

Övriga föreskrifter

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.

Ändringar inför denna kursomgång

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, adk21, har följande ändrats:

  • Instruktionerna till labb 1 har uppdaterats för att underlätta arbetet med labben, särskilt i fråga om teckenkodning.
  • Uppgift 1 på mästarprov 1 utformas så att den inte kräver så många rader pseudokod att beskriva. Längre tid ges för arbetet med mästarprov 1.
  • Ett råd om att inte använda lokalsökning i labb 5 har lagts till i instruktionerna.
  • In- och utdata för testfall 1 i Kattis har lagts in för flera av labbarna.
  • FFT-föreläsningen har ersatts av en föreläsning om beständiga datastrukturer. FFT ingår istället i fortsättningskursen DD2440 Avancerade algoritmer.
  • Tydligare information om att kursens teoridel examineras både av dom teoripoängsgivande uppgifterna under kursens gång och av den avslutande teoritentan. 
  • Vi tipsar om att det troligen sparar tid att delta i undervisningen.
  • Kommenterade studentlösningar till mästarproven 2020 och 2021 har tagits fram.
  • En pedagogisk text om pseudopolynomi har tagits fram så att ingen i mästarprov 2 råkar utforma pseudopolynomiska algoritmer i tron att dessa är polynomiska. 
  • En reflektionsuppgift har lagts in sist i labbkursen. Därmed finns ett obligatoriskt examinerande moment i sista kursveckan, såsom CSN kräver. Reflektionsuppgiften kan dock genomföras direkt när man redovisat sista labben.

Kursvärdering och kursanalys

I början av kursen kommer kursansvariga studenter att utses, som du kan ta kontakt med om du har synpunkter på kursen. Du kan också vända dig direkt till någon av lärarna med synpunkter.

Efter teoritentan kommer en kursenkät att skickas ut till kursdeltagarna.  Efter kursens slut kommer kursledarna, i samråd med kursansvariga studenterna, att göra en kursanalys som publiceras på kurswebben.

Kursanalys för adk21

Tidigare kursanalyser finns upplagda på sidan kursens utveckling och historik.

Övningsgrupper

Det finns fyra stycken övningsgrupper. Grupperna har olika nivå. Välj själv grupp. Du kan byta grupp under kursens gång.

Gruppnr Övningsassistent Plats för övning Gruppens nivå
1 Emmy Yin I första salen i schemat lite enklare grupp
2 Douglas Wikström

I andra salen i schemat

normalsvår grupp
3 Kilian Risse (undervisar på engelska) och Jesper Amilon

I tredje salen i schemat

normalsvår grupp
4 Marcus Dicander I fjärde salen i schemat lite svårare grupp

 

 

Kommunikation i kursen

Kursansvarig

Lärare

Lärarassistenter

Examinator

Fakta om kursomgång

Startdatum

2022-08-29

Kursomgång

  • adk22 HT 2022-52200

Undervisningsspråk

Svenska

Kursen ges av

EECS/Datavetenskap

Kontakter

Kommunikation i kursen

Kursen har över 200 deltagare och lärarnas tid är begränsad. Tänk därför efter innan du ställer en fråga om frågan verkligen är nödvändig. Du kan hitta svar på många frågor om kursen i detta dokument och i kursöversikten i kursrummet. För frågor som inte besvaras där finns det olika kommunikationskanaler:

  • Använd diskussioner i kursrummet i Canvas. Du kan kolla i gamla diskussionstrådar om frågan redan besvarats. Om det är en ny fråga kan du starta en ny diskussionstråd.
  • Det går att fråga lärare och assistenter under föreläsningar, övningar och labbar. 
  • Administrativa frågor som gäller bara din egen speciella situation och är ointressanta för andra kan du mejla till Viggo, men svarstiden kan stundtals vara lång.

Kursansvarig

Lärare

Lärarassistenter

Examinator