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

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 och betygsskalan. På KTH-kursen användes för andra gången och på SU-kursen för första gången betygskalan A-F.

Kursdata per 12 juni 2009

Tid: period 3-period 4 läsåret 2008/2009 dvs januari-maj 2009
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: 44 timmar.
Övningar: 24 timmar.
Kursledare och föreläsare: Viggo Kann
Övningsassistenter: Torbjörn Granlund (doktorand i datalogi), Marcus Dicander och Leo Giertz (D-teknologer).
Antal registrerade elever, KTH: 124 varav 120 från D, 3 från F, 1 fristående kurs.
Antal registrerade elever, SU: 3.
Prestationsgrad förstagångsregistrerade KTH: 75% (jfr 72% år 2008)
Prestationsgrad totalt KTH: 85%
Examinationsgrad förstagångsregistrerade KTH: 60% (74 stycken; jfr 56% år 2008)
Prestationsgrad SU: 87%
Examinationsgrad SU: 67% (2 godkända av 3 aktiva)

STATISTIK efter ordinarietentan (inklusive äldre elever)

LABBSTATISTIK
  Labb nr 1: 127, 2: 114, 3: 130, 4: 129
  Hela labbkursen: 111 st (jfr 103 st år 2008)

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                                 Medelbetyg
mas1    131      21 x F   48 x E    7 x D   23 x C    6 x B   26 x A    2,1
mas2    121       9 x F   54 x E    2 x D   18 x C    6 x B   32 x A    2,3
tenta   123      24 x F   33 x E   30 x D   36 x C      -        -      1,6
x-labb4  18         -        -        -        -      4 x B   36 x A    4,9
munta    26       9 x -      -        -      1 x C    4 x B   12 x A    3,0

35 elever var behöriga att gå upp på muntan och hade inte redan betyg A.
26 anmälde sig till muntan. 17 klarade den, 6 missade, 3 dök inte upp.

SLUTBETYG
 37 x E    5 x D     8 x C     6 x B    28 x A
medelbetyg: 2,8 (jfr 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:

Använd Indakursens bok som kursbok tillsammans med ett supplement med dom delar som inte täcks av Indaboken.
Sätt ut betygskriterierna istället för svårighetsmärkningen på mästarproven.
Skriv en tydligare text på webbsidan som ger några exempel på hur man får olika betyg.

Den fjärde föreslagna förändringen var "Lista några lämpliga övningsproblem i Kattis på kurswebbsidan." Istället beskrev jag på en föreläsning hur man hittar Kattis problemlista och att man kan botanisera själv i den.

I övrigt har kursen fungerat på samma sätt som förra året, med betygsgraderade mästarprov, teoritenta och munta för högre betyg.

Sammanfattning

Prestationsgrad och examinationsgrad för förstagångsregistrerade var båda 4 procentenheter högre än förra året. Den målrelaterade examinationen i betygskalan A-F har fungerat väl. Men eftersom alla lärandemål måste vara uppfyllda för slutbetygsnivån så blir betygsfördelningen förskjuten mot betygen E och A. Medelbetyget var nästan C, betydligt högre än förra året, mest på grund av att många fler valde att göra extralabben till labb 4 och därigenom fick betyg A.

Största förändringen till nästa år blir att föreläsningarna görs om till entimmespass, blir mer koncentrerade och använder datorsimuleringar. Dessutom ska alla uppgiftslydelser gås igenom och nya testfall som är tillgängliga för alla genereras till labbarna.

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 62 elever, varav en SU-student, 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 (52%) eller mycket svår (11%) av lite mer än hälften, medan 8% tyckte den var lätt och resten medelsvår. Det var en tredjedel färre än förra året som ansåg att kursen var mycket svår.

71% fick i början av kursen klart för sig vad kursens mål var, jämfört med 75% förra året.

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

Kurslitteratur

Indakursens kursbok kan användas i ADK tillsammans med ett supplement som årets elever fick köpa för 120 kronor. Nästa års elever har redan fått köpa supplementet samtidigt som Indakursboken. Drygt hälften har använt huvudkursboken. Av dessa tyckte en tredjedel att boken är mindre bra eller dålig, samma betyg som förra årets kursbok.

Föreläsningsanteckningarna (cirka 140 sidor), med kopior på alla stordiabilder som visades samt alla övningsuppgifter med lösningar, ansågs vara mycket bra eller bra av 74% (ungefär samma som förra året). Föreläsningsanteckningarna ingick i kursbunten som såldes vid kursstart.

Grymt att du tillhandahåller föreläsningsanteckningarna. Under föreläsningarna slipper man anteckna i ett och man har möjlighet att hoppa över föreläsningar, vilket jag utnyttjade.
Föreläsningsanteckningarna räcker inte/ger inte tillräcklig information för att klara labbarna och mästarproven. Jag har behövt googla mycket. Jag skulle gärna ha sett en elektronisk pdf också som är lätt att slå upp i.
Hade önskat att vissa av de sakerna som skrevs på svarta tavlan under föreläsningarna hade funnits med, men det skulle kanske vara aningen problematiskt att trycka upp i förväg.

Jag har inte tänkt att föreläsningsanteckningarna ska vara självförklarande och ersätta kursboken. 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. Nästa år kommer föreläsningstiden att minska, vilket gör att föreläsningsanteckningarna blir mer omfattande än föreläsningarna.

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. 15% gick nästan inte på några föreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 52% (60% förra året och 81% för två år sen) medan 10% ansåg dom vara mindre bra eller dåliga.

Dåligt:
- Det går för långsamt. Tempot är under all kritik och jag får kämpa för att inte somna. Jag tycker att du borde våga ställa implicita krav på kursdeltagarna genom att höja tempot.
- Tavlan är gud. Ibland är det bästa sättet INTE tavlan, Viggo. Ta hjälp av någon duktig visualiseringsdoktorand så kan många algoritmer visas med filmer eller bilder (särskilt när det är många olika tillstånd som ska "kommas ihåg" blir det kladdigt på tavlan - t.ex. när Prim/Kruskals algos förklaras, men nästan alltid vid graf-algoritmer)
Bra:
- Utmanande frågor till publiken. T.ex. de mini-hemuppgifterna när vi skulle skapa invarianter. Det gör att man måste tänka själv på föreläsningen, något som för mig är väldigt hjälpsamt när jag ska lära mig. Mer sånt tack!
- Entusiasmen. Det märks att du brinner för ämnet och gillar att stå vid tavlan, det skapar en bra stämning i föreläsnings-salen.

Föreläsningarna är den del av kursen som behöver göras om. Spridningen i nivå, förkunskaper och behov hos eleverna gör det omöjligt att tillfredsställa alla. Jag har valt att gå igenom det grundläggande ordentligt, med tanke på dom svaga eleverna (vilket gör att dom duktigare tycker att det går för långsamt) och sedan dra upp tempot på dom delar som vänder sig till den som vill ha högre betyg (vilket gör att många tycket att det går för snabbt). Jag tänker pröva entimmesföreläsningar nästa år. Det blir då tre entimmesföreläsningar varje vecka istället för två tvåtimmerföreläsningar - ett upplägg jag har erfarenhet av från Amherst College i USA. Den totala föreläsningstiden minskar, men eleverna (och föreläsaren) behöver bara koncentrera sig en timme i taget, vilket ökar utbytet av undervisningen. Tempot kommer då naturligt att öka. Det finns en del färdiga algoritmsimuleringar och -visualiseringar på nätet som jag ska visa där det är möjligt istället för att göra algoritmkörningar på tavlan.

55% av eleverna gick på minst 60% av övningarna, något mindre än förra året. Grupperna var någorlunda jämnstora. 75% tyckte att övningarna pedagogiskt sett var mycket bra eller bra, en ökning från förra årets 69%.

Dicander har bra tavelteknik och han har alltid svar på frågor som kan dyka upp. Han har roligt när han håller i övningarna och vi som går på dom har också roligt.
Leo är en väldigt duktig övningsassistent, pedagogisk, trevlig och inspirerande.
Kul med en "pragmatic programmer" som Torbjörn i en annars teoritung kurs!

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 (48%!) eller bra (21%) av nästan alla. Drygt hälften tyckte att betygsättning med betygskriterier var bra, men oavsett detta så är det krav på målrelaterad betygsättning numera. Att det fanns flera sätt att redovisa att man uppnått lärandemålens betygskriterier ansåg tre fjärdedelar var bra eller mycket bra.

69% var positiva till kamraträttning av teoritentan och bara en person negativ. Det är uppseendeväckande gott omdöme med tanke på att tentaformen skiljer sig dramatiskt från vanliga tentor på KTH.

Lite krångligt, men det känns som om man verkligen är värd sitt betyg
Det är bra att betyget baseras mycket på hemarbete där man har tillgång till (nästan) alla resurser, det är mer som i verkliga livet och ger därmed mer realistiska resultat.
Tycker examinationen i sig varit bra. Men betygssättningen är galen - man borde få ett genomsnitt istället. AAE ger nu ett E i betyg, vilket är helt orimligt. Man kan inte bedömma en kurs efter ens lägstanivå.

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 8 fall (i sex fall har ett betyg dragit ner från A till C och i två fall har ett betyg dragit ner från C till E). Inte i något fall har ett delbetyg dragit ner slutbetyget tre eller fyra 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. 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.

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 5% ansåg att labben var för arbetskrävande. Komplexitetslabbens inverkan studeras i en just färdigställd artikel 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 71% (mot 65% förra året). Endast 5% ansåg det vara mindre bra. Trenden är att eleverna uppskattar Kattis mer nu än tidigare.

Kattis är frustrerande när hon säger att man har fel. Men är ett bra sätt att rätta sina labbar. Man bör ganske få tillgång till mer test data för de olika labbarna så man kan testa sin kod mer.
Kattis är awesome
Fler och bättre felmeddelanden.

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! Jag vill prova att generera en extra uppsättning testfall för varje labb som är helt öppen. Då kan eleverna testa och avlusa programmet mot dessa testfall först, och om det klarar dom fallen så klarar det troligen även Kattis testfall.

Feedback på mästarproven

De flesta tyckte att lärarens feedback vid muntliga redovisningarna av mästarproven var mycket bra eller bra. Bara 16% ansåg att feedbacken var mindre bra eller dålig.

Inte en helt ointressant examinationsform, där expertsituationen faktiskt tydliggörs.
Godtycklig betygsättning, dvs olika betyg beroende på vem man redovisade för.
Läraren kunde ju tyvärr inte tala om vad som var fel vid redovisningen. Pedagogiskt hade det varit väldigt bra om man hade kunnat få veta vad man gjort fel och sedan diskutera sina felaktiga lösningar med läraren och få veta var man borde tänkt annorlunda.
Uppgifterna på mästarproven borde beskrivas tydligare. Ibland fanns det flera tolkningar av samma uppgift.

Med assistentmöten och bedömningsregler försöker jag få bedömningarna så lika som möjligt. Assistenternas bedömningar tycks inte ha skiljt sig åt på något misstänkt sätt. Den assistent som gav lägst betyg på första mästarprovet gav högst på det andra, och den assistent som gav högst betyg på första gav lägst på andra! Jag och assistenterna anstränger oss för att bedömningarna ska bli så lika som möjligt. 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 examinationerna är olika. Detta har alltid varit svårt att få fram till eleverna.

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å. Uppgiftsmärkning med betygskriterier istället för svårighet har fungerat bra. Uppgiftsformuleringarna råkade ut för ovanligt många problem i år. Jag visar alltid uppgifterna för assarna i förväg, men det är ofta precis innan dom ska offentliggöras. Jag ska försöka ge dom mer tid för att hinna läsa och ge respons på formuleringarna nästa år.

Teoritentan

På ordinarietentan fanns en uppgift som var formulerad med dubbel negation, vilket gjorde att flera studenter hade svårt att förstå den.

Dubbelnegationer i tentamen är enligt min åsikt oproffesionelt och dålig stil mot tentander att inte anstränga sig mer för en begriplig tenta.

I komplexitetsteori behövs ibland dubbla negationer för att uttrycka satser, men jag ska i framtiden ta hänsyn till att sådana satser kan vara svårare att förstå.

Särbehandling och genus

Ingen som svarade på enkäten ansåg sig ha utsatts för någon särbehandling. Dom flesta hade inte funderat över kursens genusperspektiv eller tyckte ens att det var något som hade med kursen att göra. Några tyckte att det vore bra med kvinnliga lärare och assar och fler tjejer bland teknologerna. Jag ska försöka rekrytera några fler kvinnliga handledare till nästa år (i år var det en).

Glädje av kursinnehållet

82% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden (74% förra året). En enda person tror sig inte ha nytta av kursen alls, och övriga av en liten del av kursen. 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

Att låta slutbetyget vara det lägsta delbetyget kan vara väldigt missledande. T.ex. låta D, D, D bli ett bättre betyg än A, A, E. Någon avrunding borde göras. Utöver det tycker jag kursen har varit jättebra och intressant!
Som jag skrivit ovan så får ingen A-A-E, så det är inget problem. Betygssammanvägningen behöver inte vara likadan i alla kurser, bara det framgår ordentligt av kurswebbsidan vilken sammanvägningsmetod som används.

1. Skippa tentan och inför kontrollskrivningar av varje moment (algo/datastrukt/komplex) som fyller samma funktion som tentan (dvs kollar att eleverna har lärt sig teorin).
2. Gör labbarna mer tävlingsinriktade med en t-shirt som pris för snabbast lösning eller så. Tävlingar får alltid små nördar intresserade och gör att de kommer fördjupa sig i ett ämne (cache? algoimplementation? datastruktursimplementation?) för att få lägre körtid.
Jag tror inte att fler provtillfällen under kursen är lämpligt. Jag försöker avdramatisera teoritentan istället. Den som har följt föreläsningarna aktivt eller läst på ordentligt ska inte ha några problem att klara den. I år var det fler än förra året som fick underkänt på tentan, vilket möjligen kan förklaras med att jag avdramatiserat tentan så mycket att en del elever chansade och gick upp på den utan att ha förberett sig tillräckligt.
Kattislabbarna har redan en tävlingsmöjlighet eftersom dom tre snabbaste lösningarna i varje språk syns för alla. Och i extralabben ger en bättre heuristik bättre betyg. Kanske skulle dom bästa heuristikerna också kunna få en offentlig topplista. Det finns en fara i att ha för mycket tävlingsmoment, eftersom det också kan avskräcka vissa.

Fler probabilistiska algoritmer
Jag har varit tvungen att ta bort nästan alla probabilistiska algoritmer ur kursen eftersom Matstat ligger i årskurs 3 på D, och alltså kommer efter ADK. Jag vill väldigt gärna lägga tillbaka probabilism eftersom det är en viktig algoritmkonstruktionsmetod, men det kräver att Matstat flyttas.

Roligaste kursen hittills. Inte så svår som alla säger. Kattis pwns.

Har gjort mig till en bättre programerare med mer förståelse.

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

Ge föreläsningarna som entimmespass för att öka både elevernas och föreläsarens koncentration.
Visa algoritmsimuleringar på dator när det är möjligt.
Gå igenom labblydelserna, mästarprovslydelserna och tentalydelsen noggrant så formuleringarna är entydiga.
Generera en för alla tillgänglig uppsättning testfall för varje labb.