Kursanalys

Kursanalys för DD1352 Algoritmer datastrukturer och komplexitet, hösten 2013. Kursen är obligatorisk för D3.

Kursdata per 17 mars 2014

Tid: period 1-period 2 läsåret 2013/2014 dvs september 2013-januari 2014
Högskolepoängantal KTH: 9 (varav 3 på labb, 3 på mästarprov, 3 på tenta)
Tenta: ordinarietenta sista dagen i läsperiod 2
Föreläsningar: 35 timmar.
Övningar: 24 timmar.
Kursledare och föreläsare: Viggo Kann
Övningsassistenter: Emma Enström (doktorand i datalogi), Marcus Dicander och Anders Ye (D-teknologer).
Antal registrerade teknologer: 186 varav 135 från D, 19 från IT, 3 från F, 3 från I, 1 från CL, 9 från högskoleingenjörsprogrammet i datateknik, 9 från kandidatprogrammet i IT, 6 från olika masterprogram och en utbytesstudent.
Av dessa har 20 inte något enda resultat på kursen och har inte lämnat in någon utvärderingsenkät. Dessa har räknats bort i nedanstående statistik, som alltså baseras på 166 stycken förstagångsregistrerade (165 föregående år).
Prestationsgrad förstagångsregistrerade KTH: 78% (samma som år 2011 och 2012)
Prestationsgrad totalt KTH: 81% (85% i maj 2013)
Examinationsgrad förstagångsregistrerade KTH: 59% (98 stycken; jfr 59% år 2012, per 1 maj 2013)

STATISTIK efter ordinarietentan (förstagångsregistrerade)

LABBSTATISTIK
  Labb nr 1: 150, 2: 156, 3: 130, 4: 136
  Hela labbkursen: 127 st (jfr 125 st år 2012)

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                                 Medelbetyg
mas1    146       9 x F   45 x E   13 x D   72 x C    0 x B    7 x A    2,2 (1,8 2012)
mas2    134      38 x F   26 x E    7 x D   21 x C   11 x B   31 x A    2,3 (2,2 2012)
tenta   138      13 x F   18 x E   36 x D   71 x C      -        -      2,2 (1,9 2012)
x-labb4  36         -        -        -        -      7 x B   29 x A    4,8 (4,8 2012)
ommas1                     6 x E
ommas2                    21 x E
munta1   29       8 x F      -        -      1 x C    8 x B   12 x A
munta2   12       4 x F      -        -      3 x C    2 x B    3 x A
muntahög  4       3 x F      -        -        -      1 x B      -

SLUTBETYG
 34 x E   12 x D    31 x C     5 x B    16 x A
medelbetyg: 2,6 (jfr 2,3 år 2012, 2,9 år 2011,  2,1 år 2010, 2,8 år 2009 och 2,2 år 2008)

Lärandemål

Efter kursen 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 begreppen P, NP, NP-fullständighet och oavgörbarhet,
jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,
förklara hur man kan hantera problem med hög komplexitet

för 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.

Förändringar inför denna kursomgång

Förändringarna som planerades i föregående års kursanalys har genomförts:

Finputsning av den mönsterorienterade undervisningen i dynamisk programmering.
Utveckling av undervisningen och övningen i pseudokod och korrekthetsmotivering.
Tips om att man ska börja tidigt med mästarproven och avsätta en hel del tid till dom har getts på föreläsningarna.
Uppmaningar vad som ska läsas i kursboken har lämnats vid varje föreläsning.

Sammanfattning

Tre delar av kursen har identifierats som särskilt svåra. Därför har Viggo tillsammans med Emma Enström och delvis i samarbete med universitetet i Florens i ett forskningsprojekt studerat svårigheterna och hur dom kan överkommas med olika aktiviteter. Därför har flera självvärderingsenkäter getts vid föreläsningar under kursen, enkäter hämtats in vid varje mästarprov och i samband med tentan.

Kursen har fungerat mycket bra. Aktionsforskningsprojekten har förbättrat kursen och studierna har inte varit störande, tvärtom snarast givande. Nästa år planeras inga nya studier, men resultat från årets studier kommer att användas för att förbättra kursen ytterligare.

Faktiskt innehåll i kursen

Kursen följde det planerade innehållet.

De datadidaktiska forskningsstudierna i kursen kommer att avrapporteras i en artikel som skrivs under senvåren.

Elevernas synpunkter

Kursansvariga studenter för adk13 var D-teknologen Kristoffer Emanuelsson och I-teknologerna Kattarina Hallin och Björn Söderlind. Mitt i kursen hölls ett kursnämndsmöte. KASarna hade också inflytande över kursenkätens utformning.

Jag la upp en kursutvärdering på webben efter teoritentan men före muntan. Den besvarades bara av 31 elever, vilket enligt flera elever beror på att det gjordes en utvärdering på papper vid tentan, och många uppfattade inte att kursenkäten på webben var en annan enkät som också kunde besvaras.

Eftersom det var så få svar (bara drygt 15% av kursdeltagarna) kan representativiteten vara låg. Här följer en sammanfattning av enkätsvaren med mina kommentarer.

Kursinnehåll

Kursen ansågs vara ganska svår av hälften och mycket svår av en fjärdedelar, medan en tiondel tyckte den var lätt och resten medelsvår. Det är i stort sett samma som förra året.

4 stycken tyckte inte att dom i början av kursen fick klart för sig vad kursens mål var.

94% tyckte kursen var intressant (jämfört med 98% 2012, 95% 2011, 80% 2010).

Kurslitteratur

Två tredjedelar har använt kursboken (mot knappt hälften förra året), och bara en femtedel av dessa tycker att den inte är bra. Eftersom jag varje föreläsning har påpekat vad man ska läsa i boken till nästa gång så är det inte oväntat att fler har skaffat boken. Alla som använt boken har åtminstone ibland förberett sig inför föreläsningar genom att läsa i boken. Tyvärr är det bara en tredjedel av dom som oftast gör det inför föreläsningarna. Jag tror att detta ändå är mycket mer än i andra kurser, men det är svårt att ändra på inrotade studievanor. Förleläsningarna är upplagda för att i första hand passa den som är förberedd.

Föreläsningsanteckningarna på webben (cirka 140 sidor), med alla stordiabilder som visades samt alla övningsuppgifter med lösningar, ansågs vara mycket bra eller bra av två tredjedelar.

Föreläsningsanteckningarna ger en bra överblick och kurslitteraturen är väldigt bra skriven för ett relativt komplicerat ämnesområde.
Kurslitteraturen är bra men mycket djupgående, vilket som alltid gör det svårt att sålla ut det relevanta. Bra med läshänvisningar inför föreläsningar.
Kurslitteraturen kändes inte nödvändig. Föreläsningsanteckningarna kunde ha haft mer information, är deras begränsade information avsiktlig?

Jag har inte tänkt att föreläsningsanteckningarna ska vara självförklarande och ersätta kursboken. Den som har missat en föreläsning måste läsa i kursboken - det räcker inte med föreläsningsanteckningarna.

Undervisningen

Kursen är upplagd så att den som vill läsa in den själv ska kunna göra det. Trots detta gick 58% (förra året 52%) på i stort sett alla föreläsningarna. 3% (förra året 9%) gick nästan inte på några föreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 90% (94% förra året).
84% föredrar entimmesföreläsningar i kursen (79% förra året) och 1% föredrar tvåtimmarsföreläsningar (11% förra året). Jag tycker att entimmesföreläsningar är mycket mer stimulerande än tvåtimmarsföreläsningar och jag ser betydligt färre sovande elever i föreläsningssalen. Att nästan ingen föredrar tvåtimmarsföreläsningar är anmärkningsvärt eftersom detta är den enda kursen i utbildningen som har entimmesföreläsningar.

Under förutsättingen att innehållet ska läsas i förväg har föreläsningarna varit bra. Har man dock missat någon liten del kan det ibland vara svårt att hänga med.
Imponerande hur Viggo kan göra så svår teori lättbegriplig. Tror att det bygger mycket på att kursen är så bra planerad och att det finns mycket erfarenhet kring vad som är svårt. Mycket tid har lagts på att reda ut det som är svårast, och det är jättebra.
Jag föredrar föreläsningar som är till för att vara före läsning, men kursföreläsningarna har fungerat utmärkt att använda på det sättet också. Frågorna har varit extremt givande för mig, man tvingades att dra lite slutsatser och reflektera över vad man just hade hört (På ett sätt som man aldrig får chansen att göra på andra föreläsningar). Går säkert att förbättra dessa ännu mer!

84% tyckte att färgfrågorna (aktiverande alternativfrågor där var och en svarar med en färglapp) var mycket givande eller ganska givande. Bara 10% ansåg dom mindre givande och ingen att dom var värdelösa.

36% av eleverna gick på minst 60% av övningarna, mot 47% förra året. Över 70% tyckte ändå att övningarna pedagogiskt sett var mycket bra eller bra, så varför inte fler deltog är svårt att förstå.

Jag har stor respekt för alla tre assistenterna men tycker att Marcus kan bli lite rörig ibland plus att han typ aldrig suddar tavlan och försöker hitta småställen att skriva på varför det blir ännu rörigare att hänga med. Anders har bra koll själv men kan vara lite för stressad för att på ett lugnt och pedagogiskt sätt förklara när man inte vet. Emma har jag enbart oerhört positiva saker att säga om, trevlig, lugn, mycket kunnig, jättepedagogisk, lyhörd.. skulle kunna fortsätta.. jag förstod jättemycket när jag hade henne!
Bra övningar, men svårt att följa de komplexa uppgifterna. Vet inte hur det skulle kunna göras annorlunda, dock.

Övningsgrupperna har olika karaktär och svårighet, och de flesta elever tycks ha hittat en grupp som passar.

Examinationsformen och tentan

Examinationsformen med en tredjedel av vardera labbar, mästarprov och tenta ansågs mycket bra eller bra av nästan alla (87%). Majoriteten (70%) tyckte att betygsättning med betygskriterier var bra och att det var bra att det fanns flera sätt att redovisa att man uppnått lärandemålens betygskriterier.

64% tyckte att kamraträttning av teoritentan var bra eller åtminstone acceptabelt, jämfört med 84% förra året, en försämring.

Målet med en kurs är att man ska lära sig.. PUNKT! Inte att sätta dit eleverna eller vad det nu handlar om... och den här undervisningsformen gör att man VERKLIGEN lär sig.. har sällan stött på en så bra kursutformning.. dock förstår man att den kräver mycket stor insats från skolan och lärare (enklare att bara han en tenta i slutet av kursen) men absolut.. ALL heder åt den här formen.. jag har lärt mig jättemycket och jag har verkligen kämpat.. men på ett betydligt "bättre" sätt än att sitta 100 timmar och läsa i en bok inför en tenta... Den här kunskapen kommer att sitta vilket inte tentapluggning gör... Kamraträttning är ju alltid lite av ett gissel.. det blir en massa dumma frågor och när någon väl banat väg för desa frågor.. då börjar alla.. det är acceptabelt och kanske till och med bra om man tillämpar den som Viggo (som ett forum där man har kontakt med vad eleverna tycker och kan ta detta i beaktan) men generellt är det knappt acceptabelt...
Examinationen har förvisso uppmuntrat till kontinuerligt lärande, men samtidigt ger man lätt upp sina ambitioner ifall ett delmoment går dåligt, eftersom det lägsta betyget av alla delmoment blir ditt slutbetyg. Något slags medelvärde eller liknande vore att föredra. Annars skulle det kanske fungera om det var enklare att komplettera eller "plussa" något delmoment. Kamraträttning är ett generellt dåligt element i undervisning av flera skäl. Eleverna som läser kursen har extremt varierande kunskap i ämnet och betygskriterierna. Generellt sett har de heller ingen erfarenhet av tentarättande, vilket kan skapa stor godtycklighet i bedömningen. Det tar dessutom mycket tid i anspråk av eleverna som måste fråga om specialfall eller funderingar i enskilda tentor.
Teoritentan är för mycket ingrottad på att komma ihåg exakta definitioner och liknande. Jag tycker poängen istället borde ges i form av "har förstått frågan och känner till i princip hur svaret är", "det märks att eleven kan svaret men har missat några detaljer", "har ett fullständigt och korrekt svar". Nu är det för mycket all-or-nothing på varenda fråga så även om man har en ganska bra förståelse är det ändå lätt att få 0p på de flesta frågorna, så jag tycker inte betyget för tentan motsvarar kriterierna. Ännu hellre alltså: dela istället upp frågorna i E-frågor, D-frågor och C-frågor.
Frågorna med "vad heter följande begrepp på engelska?" hittar jag ingen som helst grund för i betygskriterierna, så lägg antingen till ett kriterium för detta eller ta bort frågan.
Att folk struntar i att lära sig de korrekta definitionerna är såklart trist, när det till och med står i förväg att om man vill ha E på tentan ska man kunna "definiera begreppen P, NP, NP-fullständighet och oavgörbarhet". Kanske det är möjligt att komma på något smart pedagogiskt som pushar studenterna att lära sig dessa definitioner och begrepp bättre i detalj? Att bara känna till ungefärliga definitioner eller tro att följdsatserna är definitionerna verkar tyvärr alltför många göra.

Även om man missar ett av mästarproven och får betygen E, A, C så är det inte kört eftersom man kan munta upp första betyget till C och få C som slutbetyg eller både första och tredje betygen till A och få A som slutbetyg. Det går också att göra extralabben för att få A på det tredje betyget. Ytterligare en metod är att plussa betyg i en senare kursomgång.

Att kamraträttningen på tentan var mindre uppskattad i år än tidigare kan bero på att eleverna råkat ut för kamraträttning i flera tidigare kurser och haft negativa förutfattade åsikter om den. Rättningssessionen efter tentan tar knappt en timme, och då hinner alla uppgifter på tentan gås igenom och alla som vill fråga frågor om rättningen får chans att göra det. Det kan kännas tufft för den som missat uppgifter på tentan att få reda på det direkt efter tentan, men utan rättningssessionen skulle hen kanske inte alls tänka på vilka svar som var fel. Denna påtvingade återkoppling ger alltså en sista möjlighet för kursledaren att reda ut eventuella missförstånd.

Det är lite otydligt på tentan vilka uppgifter som är E-uppgifter, D-uppgifter och C-uppgifter. Nästa år ska jag märka uppgifterna med nivå. Bonuspoängen kommer då bara att räknas till E-delen av tentan, och för godkäntkravet kommer att sättas enbart på E-nivån.

Min tanke var att lärandemålet definiera begreppen P, NP, NP-fullständighet och oavgörbarhet skulle täcka in begreppens namn på engelska. För att inga tvivel ska råda om det kommer detta mål att få tillägget och översätta från och med nästa kursomgång.

Mästarproven

84% tyckte att undervisningen förberedde väl eller mycket väl för mästarproven och bara 3% att den inte gjorde det. 98% ansåg att lärarens återkoppling vid redovisningarna av mästarproven var mycket bra, bra eller acceptabel, vilket var betydligt bättre än förra årets 85%. Bara 14% la ner mer än 30 timmar på mästarprov 1 (27% förra året) och 16% la ner mer än 30 timmar på mästarprov 2 (12% 2012).

Fungerade väl, men kriterierna för mindre och större fel borde ses över. I mästarprov två kunde ett algoritmfel i reduktionen som påverkade vissa specialfall leda till att uppgiften helt underkändes, trots att allt övrigt var tillfredställande löst, vilket känns underligt.
Mästarproven är ett suveränt att examinera kunskap på. Muntligt skriftligt = jättebra.
Kul uppgifter, trevligt med uppgifter kopplade till aktuella händelser.. :-)
Vad som krävs i form av bevis och likande hade kunnat förtydligas och övas mer på.
Jag spenderade onödigt mycket tid på att bevisa att min giriga algoritm var korrekt (jag gjorde alla steg som gjordes i boken) och fick samma bedömning som andras lösningar som i mina ögon inte var riktiga bevis. Jag tycker att det är viktigt att få fram tydligt på vilken nivå bedömningen är för ett bevis.

Eftersom mästarproven är moment värda 1,5 hp var så är det rimligt att lägga ner en veckas jobb (inklusive inläsning) på varje. Många skulle nog få bättre betyg på mästarproven om man ägnade mer tid åt dom. Denna gång sa jag detta tydligt inför mästarproven, men trots det var det färre som ägnade över 30 timmar till mästarproven. Jag ska vara ännu tydligare med detta nästa gång.

I år förbereddes bedömningen av mästarproven extra noggrant med ett detaljerat bedömningsprotokoll som alla assistenter skulle fylla i. Detta var i första hand till för att få underlag till vårt forskningsprojekt, men protokollet gjorde också att assistenterna fick lättare att göra bedömningar och att bedöma precis lika som andra assistenter. Jag definierade nämligen i förväg precis hur höga krav som skulle gälla för varje bedömningsområde, såväl i den skriftliga lösningen som den muntliga. Kraven på den muntliga lösningen ställdes efter betygskriterierna, men kraven på den skriftliga lösningen var ofta något lägre, så att eleven skulle ha möjlighet att göra missar i det skrivna men klara ut dom vid den muntliga redovisningen. Den giriga algoritmen som kommenterades ovan var en E-uppgift, och därför ställs låga krav på korrekthetsmotiveringen. Däremot ställdes krav på bevis för att det girigt beräknade värdet skulle vara optimalt; detta är nödvändigt för giriga algoritmer och det stod tydligt i uppgiftslydelsen.

För första gången användes KTH Social för kursinformationen, vilket gav en ny möjlighet för eleverna att fråga om och få svar på mästarprovsformuleringarna. Uppgifterna var granskade av assistenterna i förväg för att lydelserna ska vara tydliga och entydiga. Trots det ställdes frågor som krävde svar som var mer specifika än uppgifteslydelsen. Detta är svårt att hantera på ett perfekt sätt. Vad gäller enhetskostnad och bitkostnad så ingår det i en algoritmkonstruktörs uppgifter att välja vilket kostnadsmått som är rimligast att använda. Därför är det inte bra att specificera i uppgiften vad som ska användas. Till nästa år ska jag lägga till övningsuppgifter som handlar om att välja och motivera om enhetskostnad eller bitkostnad ska användas i några olika fall.

Kattis

Det automatiska programtestningssystemet Kattis används för sjunde året i kursen. Kattis fick helhetsbetyget mycket bra eller bra av 68% (mot 80% förra året och 76% året innan). Bara två stycken ansåg systemet vara mindre bra eller dåligt.

Kattis är bra då det tvingar oss att inte fulhacka oss till lösningar, samtidigt som vi måste reflektera mer över komplexitet.
Väldigt bra för att avlasta labbassistenterna. Det är också mycket praktiskt att kunna kontrollera om ens program är korrekt när som helst på dygnet, vilket ökar flexibiliteten i när och var man kan göra labbarna. Man sparar också tid då man enklare kan upptäcka misstag innan redovisningen.
Återkopplingen var bristfällig. Det var väldigt svårt att felsöka program eftersom att man inte visste vad som var fel.
Tiderna kan variera. Samma lösning kan ena stunden ta för lång, för att i nästa bli accepterad.
Gällande problemlydelserna för Kattis så hade jag gärna sett indatagränser som stämmer överens med testdata, så man vet hur effektivt ens program behöver vara. I år var det vissa lydelser som saknade dessa helt, medan DP-labben hade givna testdatagränser som var betydligt högre än värsta fallet i testdatan. Detta fick mig att tro att den tänkta lösningen var alldeles för ineffektiv.

Kattis har massor av goda pedagogiska sidor. Det gäller bara att undvika dom få avigsidorna. Kattis kan inte avslöja sina testindata, det skulle urvattna Kattis funktion mer och mer. Kattis skulle ursprungligen bara testa att programmen gör rätt och är tillräckligt snabba, men många som använder Kattis vill också att hon ska hjälpa till att hitta fel i programmen! Kattis server var överbelastad i början av kursen på grund av att AI-kursen gjorde mycket tunga körningar på Kattis samtidigt, och det gjorde att tiderna varierade, något som inte varit något problem tidigare. Under kursens gång byttes Kattisservern mot en ny kraftfullare server, och då försvann vad vi vet dessa problem.

Jag ska se över indatagränserna i labblydelserna till nästa år.

Särbehandling och genus

En person ansåg sig ha blivit utsatt för särbehandling, på grund av invandrarbakgrund. Sådan särbehandling ska inte förekomma, och jag hoppas att det var ett undantagsfall som inte kommer att upprepas.

Några kommentarer om kursen ur ett genusperspektiv:

Varken eller, har inte haft någon tanke på genus. Det i sig är väl ett bra betyg, att "genusproblem" inte förekommit (å andra sidan är jag vit man i 30-årsåldern!). Positivt att ni har det i åtanke och är medvetna om det!
Jag tycker den håller en hög nivå. Det är positivt att det har funnits kvinnliga kursassistenter också, det är bra med lite mer mångfald på KTH.
Jag vet inte svaret på den här frågan... jag tycker genus är en viktig fråga men jag tycker också att den kan bli överdrivet förstorad och att man nästan gör det till en grej för människor som kanske från början inte gör en så stor grej av det... Men visst.. vi hade en kvinnlig assistent... och boken var kanske skriven av en kvinna och en man.. eller var det två män? Eller två kvinnor?.. Spelar det någon roll?

Glädje av kursinnehållet

93% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden (90% förra året och 88% året innan). Detta visar att kursen är och uppfattas som central för utbildningen.

Förslag till förbättringar och allmänna kommentarer

Mycket intressant, givande och utmanande kurs. Tydlig koppling till verkliga problem och pedagogisk samt välmotiverad examination. Har inte några direkta klagomål på kursen, och att den är 'svår' är knappast något negativt, även om det såklart ökar arbetsbördan.

Tycker att boken är har varit helt värdelös som ett hjälpmedel. Det som har hjälpt mig oerhört mycket har varit föreläsningar från youtube, speciellt om NP begreppet. Mer specifikt följande videoserie om algoritmer och komplexitet

Jag tycker att en obligatorisk labb i approximationer och heurestiker ska till. Alla inklussive mig kommer nog inte ta sig tiden att göra extralabben, och det kändes även som att det var ett moment som saknades inför tentan.

Användandet av KTH Social skulle kunna förbättras. I år har en del viktig information funnits gömda i långa kommentarstrådar, men i någon av huvudtexterna. Detta gör att många elever riskerar att missa informationen.

Kursen får generellt mycket beröm även om vissa kritiska röster finns. Labbkursen kan inte göras större och heuristiker är något som kommer tillbaka i högre kurser, så jag har bedömt att det räcker med en betygshöjande labb på det området.

Anpassning till andra kurser

Kursen samordnades med Diskret matematik för D3 som lästes parallellt. Det har fungerat bra. Tidpunkter för inlämningar och redovisningar har samordnats med alla övriga kurser som D3 läser på hösten.

Fortsättningskurserna (Avancerade algoritmer, Kryptografins grunder, Seminariekurs i teoretisk datalogi, Algoritmisk bioinformatik, Komplexitetsteori och Problemlösning och programmering under press) är planerade att passa ihop med ADK.

Planerade förändringar

Föreläsningarnas upplägg kommer ännu tydligare att bygga på färgfrågorna.
Lärandemålet om begreppsdefinitioner kommer att utökas med översättningsförmåga.
Tentans uppgifter kommer att specificeras med betygsnivå och bonuspoängen kommer att räknas till E-uppgifterna.
Övningsuppgifter som tränar val mellan komplexitetsanalys med enhetskostnad och bitkostnad kommer att läggas till.
Indatabegränsningarna i labblydelserna kommer att ses över.
När det insamlade datat i forskningsstudierna om dynamisk programmering, pseudokod och korrekthet, samt NP-fullständighet är färdiganalyserat kan fler modifieringar komma att göras.

Viggo Kann