Kursanalys för DD1352 Algoritmer datastrukturer och komplexitet, hösten 2011

Kursen är obligatorisk för D3.

Kursdata per 8 februari 2012

Tid: period 1-period 2 läsåret 2011/2012 dvs september 2011-januari 2012
Högskolepoängantal KTH: 9 (varav 3 på labb, 3 på mästarprov, 3 på tenta)
Tenta: ordinarietenta efter period 2
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 Adam Renberg (D-teknologer).
Antal registrerade teknologer: 143 varav 123 från D, 2 från IT, 4 från CL, 1 från Media, 7 från F och 6 datahögskoleingenjörer. Dessutom en doktorand.
Prestationsgrad förstagångsregistrerade KTH: 77% (jfr 72% år 2010)
Prestationsgrad totalt KTH: 90% (86% år 2010)
Examinationsgrad förstagångsregistrerade KTH: 63% (90 stycken; jfr 53% år 2010)

STATISTIK efter ordinarietentan (alla i Rapp)

LABBSTATISTIK
  Labb nr 1: 137, 2: 132, 3: 120, 4: 123
  Hela labbkursen: 114 st (jfr 119 st år 2010)

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                                 Medelbetyg
mas1    131       8 x F   33 x E   22 x D   22 x C   29 x B   17 x A    2,6 (1,9 2010)
mas2    126      13 x F   45 x E   10 x D   11 x C    7 x B   40 x A    2,6 (2,0 2010)
tenta   129      14 x F   20 x E   26 x D   69 x C      -        -      2,2 (1,6 2010)
x-labb4  38         -        -        -        -      9 x B   29 x A    4,8 (4,9 2010)
munta    44         -        -        -      7 x C   11 x B   17 x A    3,4 (3,9 2010)

SLUTBETYG
 32 x E    7 x D    11 x C    15 x B    25 x A
medelbetyg: 2,9 (jfr 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:

Kursen flyttades från våren i årskurs 2 till hösten i årskurs 3.
Probabilistiska algoritmer och komplexitet har tagits upp i kursen, eftersom kursen nu ligger efter Sannstat.
Vid kursstart kunde den som ville köpa föreläsningsanteckningar och övningsanteckingar på papper för självkostnadspris.
Kattis har uppdaterats och feedbacken från testfallen har setts över.
Några enkla övningsuppgifter har lagts till. Tips på fler övningsuppgifter och programmeringsövningar för den som vill öva mer i Kattis har getts.

Komplexitetsdelen av kursen anses traditionellt som svår. Därför har Viggo i ett forskningsprojekt tillsammans med universitetet i Florens utvecklat motivation och pedagogisk framställning av komplexitet. Detta genomfördes och utvärderades i denna kursomgång.

Sammanfattning

Kursen fungerar mycket bra. Betygsfördelningen är nu mycket jämnare och betygsmedlet har höjts med nästan ett helt steg sedan föregående år och ligger nu på C. Det beror troligen delvis på att kursen går en termin senare i utbildningen och delvis på dom insatser som gjorts för att förbättra kursen, framför allt vad gäller komplexitetsdelen.

Faktiskt innehåll i kursen

Kursen följde det planerade innehållet.

Elevernas synpunkter

D-teknologen Dorothea Andersson var kursansvarig student. Den 22 november 2011 hölls ett kursnämndsmöte, se separat protokoll.

Jag la upp en kursutvärdering på webben efter teoritentan men före muntan. Den besvarades bara av 51 elever, vilket kanske beror på att jag gjorde flera andra utvärderingar i kursen inom mitt forskningsprojekt.

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

Kursinnehåll

Kursen ansågs vara ganska svår (57%) eller mycket svår (12%) av lite mer än hälften, medan 6% 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, samma som förra året.

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

Kurslitteratur

Bara drygt hälften har använt kursboken, men två tredjedelar av dessa tycker att den är bra. Flera kommenterar att man kan klara sig långt med undervisningen, anteckningarna och Wikipedia. Det är sant för vissa personer men långt ifrån alla.

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 80%, vilket är mycket fler än förra året (45%) och i samma storleksordning som året dessförinnan (74%). Anteckningarna var i stort sett samma - enda väsentliga skillnaden var att dom 2010 bara fanns elektroniskt, medan dom 2011 erbjöds på papper till dom som ville. Uppenbarligen är det många som önskar materialet samlat på papper, medan andra är mycket nöjda med att bara ha det på webben. Jag kommer att fortsätta på detta sätt.

Man kan inte söka text i dom, men det kanske bara är bra då man verkligen måste kolla igenom allt.
Var lite svårt att hänga med och läsa ikapp om man missat en föreläsning men mycket bra annars. Fast samtidigt så kanske det är lite poängen då de inte skulle ha varit lika bra och sammanfattande om de innehöll mer detaljer.
Precis lagom mycket från föreläsningarna är med på anteckningarna. Efter ett tag lär man sig vad man själv måste anteckna om man vill komma ihåg det, speciellt om man sitter med laptop och kollar själv i föreläsningsanteckningarna under föreläsningen. Det gör det verkligen lättare att hänga med, eftersom man kan kolla tillbaka på någon bild själv om man var ofokuserad någon minut!
Tydliga och snygga. Roligt med handskrivna.

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 63% (förra året 46%) 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 94% (59% förra året) och bara en elev ansåg att dom var mindre bra eller dåliga (23% förra året).
76% föredrar entimmesföreläsningar i kursen (65% förra året) och 12% föredrar tvåtimmarsföreläsningar (18% förra året).

Föreläsningarna är väldigt givande! Jag tycker speciellt om de blå/gula lapparna som verkligen tvingade en att tänka. De får gärna användas på mer än komplexitetsdelen tycker jag!
Demonstrationerna av algoritmer = jättebra.
Entimmesföreläsningar är superbra! Då orkar man koncentrera sig.
Entimmarsföreläsningar var bra av flera anledningar: 1) Man var fokuserad under nästan hela passet 2) Föreläsningarna var oftare, vilket gjorde att man kom ihåg mer från förra tillfället 3) Eftersom de oftast var schemalagda kl 9 kunde man aldrig börja kl 8 på en dag med ADK-föreläsning, vilket jag tror verkligen uppskattades när det blev lite mörkare ute.
Jag tycker det är jobbigt att ta sig till skolan för en timme. Hade gått på mer om det varit tvåtimmars.

Entimmesföreläsningar och algoritmvisualiseringar infördes förra året. Det fick positiv respons då och har fungerat ännu bättre i år.
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.

71% av eleverna gick på minst 60% av övningarna, mot 67% förra året. Grupperna var någorlunda jämnstora. 78% tyckte att övningarna pedagogiskt sett var mycket bra eller bra, en liten ökning från förra årets 64%.

Första övningen upplevde jag som svår för att vara "en första övning", så den kanske skrämde iväg vissa.
På föreläsningarna blev man intresserad av materialet och på övningarna lärde man sig det. Så var det i alla fall för mig! Dicander är väldigt duktig på att förklara alla delarna av kursen och ge spontana och lite mer ovanliga exempel som verkligen gör att man kommer ihåg materialet också. Ibland kan det bli lite mycket av "ta fem minuter och diskutera det här med grannen!". Det fungerar oftast, men ibland har man verkligen ingen idé och vill bara veta svaret och då känns det lite som bortkastad tid. Som lärare måste det dock vara väldigt svårt att känna av det, så det är en väldigt liten detalj!
Jag tycker Torbjörn gick igenom problemet på ett rakt och tydligt sätt. Det var ofta lätt att förstå. Dessutom var tempot ofta väldigt bra. Ibland kanske det kunde skrivas lite snyggare på tavlan så det blir lättare att se vad som står där. Men som helhet är jag mycket nöjd med Torjbörns undervisning.
Adam är kung, kände inte heller att det var någon nackdel alls att man gått till en "långsammare" grupp.

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

Examinationsformen

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

I stort sett alla (94%) tyckte att kamraträttning av teoritentan var bra eller åtminstone acceptabelt. Även lärarens återkoppling vid redovisningarna av mästarproven ansågs bra eller acceptabel av nästan alla (90%).

Betygssättningsmetoden hade fått högre betyg om systemet hade förklarats genomgående tidigare i kursen. Som det var nu vet jag att det var en del personer som efter första mästarprovet trodde att de inte kunde få högre betyg än de fick där. Annars mycket bra.
Många klagar på betygssystemet. Jag är deras opposition. Håll kvar detta system. Det lär teknologerna att vissa saker har man bara en chans på att lyckas bra med och man måste lägga ner ordentligt med tid. Dessutom håller det kursen på en högre nivå av kvalité.
Både labbarna och mästarproven har varit intressanta och samtidigt lite knepiga vilket har skapat ett djupare intresse för området som tas upp i kursen.
Tycker det är utmärkt att man får en extra chans att påverka betyget. Jag tycker ändå det är vid kursens slut som kunskapen skall mätas till stor del och detta sätt ger studenten två chanser vilket är generöst. Att det dessutom går att examineras på olika sätt tycker jag är bra då vissa elever kanske är bättre på att redovisa på ena sättet än på andra sättet. Idén med mästarprov tycker jag är det bästa examinationsmoment jag varit med om på KTH. Skulle gärna se det i många fler kurser.

En elev på kursen gjorde på eget initiativ ett flödesschema som beskriver kursens examinationsprocess. Det beskriver examinationen mycket tydligt och kommer att användas i kursinformationen nästa gång.

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.

Komplexitetsdelen av kursen

Se separat artikel.

Kattis

Det automatiska programtestningssystemet Kattis används för femte året i kursen. Kattis fick helhetsbetyget mycket bra eller bra av 76% (mot 83% förra året och 71% året innan). Ingen ansåg systemet vara mindre bra eller dåligt.

Jag har valt mina datastrukturer mer omsorgsfullt, så att de operationer jag måste göra oftast är mest effektiva. Jag har till exempel använt betydligt fler binära sökträd än jag brukar eftersom sökning i strukturen ofta var viktigt.
För några av labbarna fick man ganska ordentlig hjälp av felmeddelandena, utan att för mycket avslöjades. Det är också givande att man kan se hur effektiv (ur tidsperspektiv) implementationen är.
Är väldigt bra att man kan fokusera på förståelse av problemet och algoritmkonstruktionen på redovisningen snarare än om algoritmen är korrekt eller inte.

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!

Särbehandling och genus

Bara en ansåg sig ha blivit utsatt för särbehandling, och den personen gav kommentaren: Som dyslektiker upplever jag att tempot på kursen är mycket högt. Speciellt de korta redovisningstiderna för mästarproven kändes svåra att hantera, jag hinner helt enkelt inte med att tänka i sådana situationer..
Jag kan förstå detta. Dyslektiker som ger sig tillkänna före redovisningen får extra tid.

En annan kommentar var:
kursupplägget fungerade väldigt bra för mig som synskadad. Speciellt tänker jag då på att undervisningen framförallt kretsade kring frlanteckningar som fanns tillgängligt på papper.

Dom flesta hade inte funderat över kursens genusperspektiv eller tyckte ens att det var något som hade med kursen att göra.
De flesta i kursens administration är män, men det är kanske inte så konstigt då det är en ganska typisk könsfördelning inom det här området. Bland handledarna, som man har mest personlig kontakt med, var dock 50% (har inte redovisat extralabben än...) av de som tog mina redovisningar kvinnor och det var inget som någon har reagerat på vad jag vet.

Nästa gång kursen går hoppas jag kunna ha en eller två kvinnor som övningsassistenter.

Glädje av kursinnehållet

88% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden (67% förra året). Detta visar att kursen är och uppfattas som central för utbildningen, och att jag lyckats med att motivera även komplexitetsdelen av kursen, vilket är glädjande.

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

Bra kurs, riktigt bra innehåll, värdefull inför framtiden. Rolig! Äntligen algoritmer och programmering på en lite högre nivå.
Fantastiskt intressant kurs med en oerhört engagerad föreläsare och duktiga övningsassistenter. Detta är helt klart den roligaste och bäst genomförda kursen hittills på KTH!
För svår kurs och dålig info inför mästarproven,man vet ej vart man ska hitta all information inför mästarproven och ej tydliga formuleringar på labbar och mästarprov! För svårt att få ett E i kursen!
Rolig kurs som känns central i programmet, materialet är typiskt sådant som får oss D-teknologer att stå ut över mängden självlärda källarprogrammerare.

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

Mer färgfrågor på föreläsningarna.
Mönsterorienterad undervisning för att lära ut dynamisk programmering.
Eventuellt ny labb i dynamisk programmering.
Komplexitetsdelen kommer att finputsas i en fortsättning av forskningsprojektet.

Viggo Kann