Kursanalys för DD1352 Algoritmer (datastrukturer) och komplexitet, våren 2010

Kursvarianter

Kursomgången var en samläsning mellan två kurser:

DD1352 Algoritmer, datastrukturer och komplexitet, obligatorisk för D2, KTH
Algoritmer och komplexitet för datalogikandiatprogrammet på SU, årskurs 3

Kurserna är identiska till innehållet och examinationen så när som på labbkursens storlek.

Kursdata per 7 juni 2010

Tid: period 3-period 4 läsåret 2009/2010 dvs januari-maj 2010
Högskolepoängantal KTH: 9 (varav 3 på labb, 3 på mästarprov, 3 på tenta)
Poängantal SU: 7,5 (varav 1,5 på labb, 3 på mästarprov, 3 på tenta)
Tenta: ordinarietenta efter period 4, omtenta i augusti
Föreläsningar: 34 timmar.
Övningar: 24 timmar.
Kursledare och föreläsare: Viggo Kann
Övningsassistenter: Torbjörn Granlund (doktorand i datalogi), Marcus Dicander och Jonas Sundberg (D-teknologer).
Antal registrerade elever, KTH: 139 varav 136 från D, 2 från CL, 1 från Media.
Antal registrerade elever, SU: 10.
Prestationsgrad förstagångsregistrerade KTH: 72% (jfr 75% år 2009)
Prestationsgrad totalt KTH: 86% (85% år 2009)
Examinationsgrad förstagångsregistrerade KTH: 53% (74 stycken; jfr 60% år 2009)
Prestationsgrad SU: 82%
Examinationsgrad SU: 70% (7 godkända av 10 aktiva)

STATISTIK efter ordinarietentan (inklusive äldre elever)

LABBSTATISTIK
  Labb nr 1: 148, 2: 133, 3: 136, 4: 141
  Hela labbkursen: 119 st (jfr 111 st år 2009)

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                                 Medelbetyg
mas1    155      17 x F   75 x E   12 x D   43 x C    2 x B    6 x A    1,9
mas2    144      17 x F   79 x E    7 x D   19 x C    2 x B   20 x A    2,0
tenta   150      30 x F   53 x E   40 x D   27 x C      -        -      1,6
x-labb4  30         -        -        -        -      4 x B   26 x A    4,9
munta    21         -        -        -      4 x C    6 x B    9 x A    3,9

22 anmälde sig till muntan. 19 klarade den (varav två med lägre betyg), två missade,
en dök inte upp.

SLUTBETYG
 59 x E    6 x D    11 x C     7 x B    14 x A
medelbetyg: 2,1 (jfr 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

Tre av fyra förändringar som planerades i föregående års kursanalys genomfördes:

Nästan alla föreläsningar har varit entimmespass för att både elevernas och föreläsarens koncentration ska vara hög.
På föreläsningarna har algoritmsimuleringar på dator visats när det är möjligt.
Labblydelserna, mästarprovslydelserna och tentalydelsen har gåtts igenom noggrant så att formuleringarna ska vara entydiga.
En för alla tillgänglig uppsättning testfall har genererats för labb 2, 3 och 4X.

Sammanfattning

Kursen fungerar bra rent praktiskt, men det höga antalet elever som bara får betyg E liksom flera kommentarer på kursenkäten visar att en betydande del av D-teknologerna inte är mogna att tillgodogöra sig kursen väl. Kursen kommer därför att flytta från våren i årskurs 2 till hösten i årskurs 3 på D. Även kursen Diskret matematik gör samma flytt. Därmed ligger ADK efter Matematisk statistik och Databasteknik, varför det finns skäl att tro att mognaden och motivationen hos D-teknologerna kommer att vara större nästa gång kursen går. I och med detta kommer det också att vara möjligt att gå in mer på probabilistisk algoritmanalys och probabilistiska algoritmer.

Faktiskt innehåll i kursen

Kursen följde det planerade innehållet.

Elevernas synpunkter

Jag la upp en kursutvärdering på webben efter teoritentan men före muntan. Den besvarades av 65 elever, varav fyra SU-studenter, 60 D-teknologer och en annan, vilket är ungefär hälften av antalet registrerade kursdeltagare.

Här följer en sammanfattning av enkätsvaren med mina kommentarer.

Kursinnehåll

Kursen ansågs vara ganska svår (55%) eller mycket svår (11%) av lite mer än hälften, medan 3% tyckte den var lätt och resten medelsvår. Det är samma andel som förra året som ansåg att kursen var svår.

6% tyckte inte att dom i början av kursen fick klart för sig vad kursens mål var, jämfört med 8% förra året.

80% tyckte kursen var intressant (jämfört med 88% 2009, 81% 2008 och 91% 2007).

Kurslitteratur

Indakursens kursböcker förra året kunde användas som ADK-kursböcker, varför dom flesta inte behövde skaffa någon ny bok. 60% har använt kursboken. En fjärdedel tyckte att boken är mindre bra eller dålig. Kommentarerna är motsägelsefulla - vissa skriver att boken är enkel att läsa och förstå och andra att den är torr och tråkig. Flera kommenterar att man kan klara sig långt med anteckningarna och Wikipedia.

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 45%, jämfört med 74% förra året. Anteckningarna var i stort sett samma - enda väsentliga skillnaden var att dom fanns på papper i kursbunten förra året.

lite tydligare förklaringar skulle vara bra. om man missat en föreläsning kan det ibland vara svårt att förstå allting.
Väldigt heltäckande och mycket bra att ha om man missat många föreläsningar.
Bra att de finns, men de är ganska svårlästa. Det är också svårt att hitta det man letar efter, man får ofta gå in i många olika pdf:er och leta.
Jag tror mer på en samlad lista över problem, algoritmer respektive datastrukturer med beskrivning, komplexitet, m.m.
Handskriva anteckningar gör att det känns mer personligt. Grafer och liknande blir även mer tydliga.

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. För att föreläsningarna ska bli mer stimulerande så visar jag inte alla bilderna från anteckningarna utan går igenom en del bara på tavlan istället. Inget viktigt ämnesinnehåll från föreläsningarna saknas i föreläsningsanteckningarna.
Jag gillar handskrivna anteckningar. En lista över kursens algoritmer och problem med komplexiteter finns på kurswebbsidan. Det tycks som om kritiken mot anteckningarna till största delen är ett informationsproblem: vissa elever har inte förstått hur föreläsningsanteckningarna är tänkta att användas.
Nästa år ska jag vid kursstart erbjuda alla föreläsningsanteckningar och övningsanteckingar på papper för självkostnadspris.

Undervisningen

Kursen är upplagd så att den som vill läsa in den själv ska kunna göra det. Trots detta gick nästan hälften på i stort sett alla föreläsningarna. 14% gick nästan inte på några föreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 59% (52% förra året och 60% för två år sen) medan 23% ansåg dom vara mindre bra eller dåliga (10% förra året).
65% föredrar entimmesföreläsningar i kursen och 18% föredrar tvåtimmesföreläsningar.

Viggo är strukturerad, talar tydligt, förklarar koncist och kommer i tid. En mönsterlärare! :-)
Lite bättre "fart", känns som att det inte riktigt hinns med pga av frågor.
Har varit en del krångel med java-applets för demonstration av olika algoritmer, testa mer i förväg och spara ner dem på föreläsarens dator så att de alltid är åtkomliga på föreläsningen.
För långa exempel. Du hinner med 1 max 2 exempel på dessa korta lektioner.
Mer korta och olika exempel. Ingen vill veta om TSP 700 gånger.
Korta koncisa föreläsningar är lättare att ta till sig än tunga tvåtimmarsoreringar. Ett bra initiativ som bör spridas genom svenska högskolor.
Jag har inte orkat åka in till skolan bara för en entimmesföreläsning. Idén är bra, men den funkar inte om det inte är så att alla kurser på KTH är entimmespass. Dessutom har det tydligen ofta varit så att lektionen dragit över för att du (Viggo) inte hunnit med allt i tid.

Föreläsningarna har i år strukturerats om helt och hållet och gjorts om till mestadels entimmespass. Dessutom har algoritmvisualisering på dator gjorts där det är möjligt. Dessa visualiseringar strulade vid några tillfällen, mestadels i början av kursen och delvis på grund av orutin - jag hade förberett noga men inte insett att själva projektorinkopplingen också kan påverka animationerna. Det kommer nog att fungera bättre nästa gång - jag tycker att det har varit givande när det fungerat, och det har det oftast gjort.
Jag tycker att entimmesföreläsningar är mycket mer stimulerande än tvåtimmesföreläsningar och jag ser betydligt färre sovande elever i föreläsningssalen.
Största problemet är som vanligt spridningen i nivå, förkunskaper och behov hos eleverna som gör det omöjligt att tillfredsställa alla. Med entimmesföreläsningarna har jag kunnat ställa högre krav på att eleverna förberett sig till föreläsningarna. Det tycks vara dom som inte förberett sig som tycker föreläsningarna är för svåra.

67% av eleverna gick på minst 60% av övningarna, mot 55% förra året. Grupperna var någorlunda jämnstora. 64% tyckte att övningarna pedagogiskt sett var mycket bra eller bra, en liten minskning mot förra året, men å andra sidan var det flera som gick på övningarna.

Jag tycker att Jonas va väldigt duktig och pedagogisk. Det var mycket man inte förstod på föreläsningarna som blev klarare på övningarna.
Mycket bättre och lärorikare än föreläsningarna! Tyvärr har jag inte haft tid att gå på alla, men de jag har varit på har varit väldigt bra. Jag har varit på övningar hos alla tre och de är riktigt bra hela bunten!

På övningarna går det bättre än på föreläsningarna att anpassa undervisningen eftersom grupperna är svårighetsgraderade. Detta, tillsammans med ambitiösa och duktiga assistenter gör att övningarna överlag får goda omdömen.

Examinationsformen

Examinationsformen med en tredjedel av vardera labbar, mästarprov och tenta ansågs mycket bra eller bra av nästan alla (81%). Majoriteten 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.

I stort sett alla (89%) tyckte att kamraträttning av teoritentan var bra eller åtminstone acceptabelt.

Jättebra att få flera möjligheter. Betygssystemet var lite rörigt i början och det var svårt att förstå, men nu i slutet är jag glad över det. Det gör att det fokuseras med på att faktiskt kunna saker än att få flest poäng på tentan, och man är inte helt körd om man missar ett moment i början på kursen. Systemet med bonuspoäng gör att man faktiskt gör labbar i tid och hjälper på så sätt med planeringen.
Jag anser att det är ganska hårt att ha tre moment på kursen, och slutbetyget blir det lägsta av de tre. Ett snittvärde hade varit mer representativt för elevens kunskaper. Tentorna anser jag vara för inriktade på smala kunskaper som visar att man har koll på små algoritmer som gåtts igenom på någon föreläsning under kursens gång. En tenta som är utformad för att testa eleven på mer djupgående teoretiska kunskaper som är kursens egentliga budskap.
Lite hårt att betyget enbart sätts av lägsta betyget, det borde viktas. Bra att man kan plussa muntligt dock. Extralabben borde kunna redovisas under labbveckan också.

Kamraträttningen fungerade mycket bra, och min uppfattning är att det var en mycket nyttig upplevelse för eleverna att få insikt i hur rättning med rättningsmall fungerar. Min granskning av svaren efteråt visade att kamraträttaren nästan alltid satt rätt betyg och att dom fall där det var fel rättat var lätta att upptäcka.
Jag har efter noga övervägande valt att ha icke-kompensatorisk betygsättning i kursen, alltså att inte ge slutbetyg efter snittet utan efter det lägsta delmomentbetyget. Jag förstår att flera har uppfattat det som dåligt, och därför har jag undersökt hur många elever som har fått ett flera steg lägre betyg på grund av att ett av delmomenten är lägre än övriga. Detta har bara skett i 7 fall. I två fall har ett betyg dragit ner från A till C, i fyra fall har ett betyg dragit ner från C till E. I ett enda fall har slutbetyget dragits ner mer än två steg. Alla fall där ett delbetyg drar ner slutbetyget två snäpp eller mer uppfyller automatiskt villkoret som krävs för att en elev ska få gå upp på muntan. Det finns därför i alla såna fall en extra chans att höja det låga delbetyget. Många har också gjort det. Det tycks alltså som att betygsättningen har sporrat elever att göra bra ifrån sig i alla delar av kursen. Dessutom ger ett icke-kompensatoriskt betyg en garanti för elevens (minimi)kunskaper inom alla betygsatta moment.

Jag utformade tentan för att den till allra största delen skulle testa de viktigaste teoridelarna av kursen. Bara en delfråga (värd 2 poäng) testade kunskap om en specifik datastruktur (Bloomfilter och hashning). Jag håller alltså inte med om att tentan testade detaljkunskaper.

Komplexitetslabben

Den nya labb 4 infördes för att ge bättre förståelse för NP-reduktioner. Mer än fyra av fem elever ansåg att labben också gjorde det. Bara 3% ansåg att labben var för arbetskrävande. Komplexitetslabbens inverkan har studerats i ett nyligen presenterat konferensbidrag av doktoranden Emma Enström.

Kattis

Det automatiska programtestningssystemet Kattis används för fjärde året i kursen. Kattis fick helhetsbetyget mycket bra eller bra av 83% (mot 71% förra året och 65% året innan). Endast 6% ansåg systemet vara mindre bra eller dåligt. Trenden är att eleverna uppskattar Kattis allt mer.

Jättebra att Kattis används! Det är väldigt skönt att få svart på vitt att man har klarat uppgiften.
Ganska roliga labbar faktiskt. Kattis gör sitt jobb men är sjukt trög på att beskriva vad som gått fel. Några till testfall hade nog varit bra till hands till labbarna.
Som flera säkert sagt så skulle mer information sitta fint. Det var tråkigt att missa en bonuspoäng och tid för att fastna på ett problem som ingen annan stötte på eller kunde förklara.

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! I år la jag till en helt öppen extra uppsättning testfall för varje labb. Då kunde eleverna testa och avlusa programmet mot dessa testfall först. Jag tror att detta har hjälpt, men det finns fortfarande elever som fastnar för länge på vissa testfall när programmet är fel eller för långsamt. Kattis kommer att uppdateras och feedbacken från testfallen kommer att ses över till nästa kursomgång.

Feedback på mästarproven

De flesta tyckte att lärarens feedback vid muntliga redovisningarna av mästarproven var mycket bra eller bra. Bara 11% (mot 16% förra året) ansåg att feedbacken var mindre bra eller dålig.

Mycket bra sätt att examinera. Man får tid till att tänka självständigt och hitta egna lösningar till problem, bra att sedan få diskutera sina lösningar med en assistent för att få ytterliggare förståelse. Mycket bra!
Efter att ha diskuterat mästarproven (i efterhand :P) verkar det som om assarnas bedömningar av mästarproven har varit olika hårda. En bekant till mig hade i princip identisk lösning men blev underkänd då jag blev godkänd.
Jag kände att jag fick brottom på redovisningarna. Att förlänga tiden kanske inte är lösningen. Men det kan vara bra att understryka att man ska kunna redovisa allt på utsatt tid, och att man ser till att lämna in lösningar som inte blir för tidskrävande att försvara.
Jag gjorde ommästarprov 2 och klarade inte det p.g.a. att det var ett optimeringsproblem som man skulle göra om till ett beslutsproblem och sedan bevisa NP-fullständighet. Då det första mästarprovet gav dig ett beslutsproblem så borde även ommästarprovet ge dig ett beslutsproblem och inte något "nytt".

Med assistentmöten och bedömningsregler försöker jag få bedömningarna så lika som möjligt. Jag har studerat assistenternas genomsnittsbedömningar, och de skiljer sig inte åt på något misstänkt sätt. Det som gör det svårt är att två likvärdiga skriftliga inlämningar kan få helt olika betyg på grund av att dom muntliga redovisningarna är olika. Detta har alltid varit svårt att få fram till alla elever.

På övningen närmast efter varje mästarprov gås mästarprovet igenom och den som har frågor om det kan fråga assistenten då.

Problemet i ommästarprov 2 var ett optimeringsproblem som först skulle skrivas om till ett beslutsproblem. Detta är en standardtransformation som är en viktig del av kursen och som alla som blir godkända på kursen ska behärska. Jag ska införa extra övningsuppgifter specifikt om detta.

Särbehandling och genus

Bara en ansåg sig ha blivit utsatt för särbehandling, och den personen gav kommentaren: algoritmerna fucked min hjärna ibland (dvs psykologiisk sexualitet). Dom flesta hade inte funderat över kursens genusperspektiv eller tyckte ens att det var något som hade med kursen att göra. En positiv kommentar var: Det är trevligt med en kurs i programmering där man inte behandlas speciellt bara för att man är tjej, utan folk ses som människor i större utsträckning. Tummen upp!

Glädje av kursinnehållet

67% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden. En enda person tror sig inte ha nytta av kursen alls. Detta visar att kursen är och uppfattas som central för utbildningen, vilket är glädjande.

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

Intressant kurs och ett upplägg som ställer krav på eleverna. Bra allt som allt!
väldigt svår kurs. men att den är intressant och rolig väger upp.
En riktig kvalitetskurs. Förmodligen den bästa jag läst på KTH hittills.
Vi är flera som går SU-varianten av kursen som tycker att vår särbehandling minskar våra chanser att få höga betyg på kursen, jämfört med KTH:arna. Vi resonerar så här:

Vi får bara 7,5 hp för kursen. De moment vi "slipper" måste kth:arna göra, men om vi vill ha extra bonus måste vi också göra dessa moment. Följaktligen får vi antingen svårare än de andra att få högre betyg eller så måste vi göra lika mycket arbete som de andra - men får fortfarande mindre antal poäng. Observera att vi antagligen har mer att göra utanför adk:kursen än de som får mer poäng för kursen, eftersom att vi också läser på heltid!
Kanske skulle ha någon labb där man får prova på att lösa problem med dekomposition och dynamisk programmering i praktiken, går just nu bara igenom det teoretiskt.

Dynamisk programmering brukar vara svårt att lära sig. Det finns flera uppgifter i Kattis som tränar dynamisk programmering, så till nästa gång föreslår jag några såna uppgifter.

SU kommer inte att läsa kursen tillsammans med ADK nästa gång utan istället tillsammans med Algoritmer och komplexitet för F med flera. Den kursen är utan labbkurs, så problemet med bonuspoäng kommer att finnas kvar men vara till SU-studenternas fördel i framtiden.

Anpassning till andra kurser

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

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

Kursen flyttas till hösten i årskurs 3 och ges nästa gång hösten 2011.
Ta upp probabilistisk algoritmanalys och probabilistiska algoritmer i kursen.
Vid kursstart erbjuda alla föreläsningsanteckningar och övningsanteckingar på papper för självkostnadspris.
Kattis kommer att uppdateras och feedbacken från testfallen kommer att ses över.
Några enkla övningsuppgifter ska läggas till. Tips på fler övningsuppgifter och programmeringsövningar för den som vill öva mer kommer att ges.