Kursanalys för 2D1352 Algoritmer (datastrukturer) och komplexitet, våren 2007

Kursvarianter

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

2D1352 Algoritmer, datastrukturer och komplexitet, obligatorisk för D2, KTH
Algoritmer och komplexitet för matte-datalinjens datalogiinriktning, årskurs 3, SU

Kurserna är identiska till innehållet och examinationen så när som på labbkursens storlek och betygsskalan. På KTH-kursen används betygskalan 3-5 och på SU-kursen G och VG, där gränsen för VG ligger mitt emellan 4 och 5.

Kursdata per 16 juni 2007

Tid: period 3-period 4 läsåret 2006/2007 dvs januari-maj 2007
Poängantal KTH: 6 (varav 2 på labb, 2 på mästarprov, 2 på tenta)
Poängantal SU: 5 (varav 1 på labb, 2 på mästarprov, 2 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: Stefan Nilsson (lektor), Mattias de Zalensky (doktorand i datalogi), Marcus Dicander (D-teknolog).
Antal registrerade elever, KTH: 113 varav 106 från D, 3 från F, 3 fristående kurs och en doktorand.
Antal registrerade elever, SU: 4.
Prestationsgrad förstagångsregistrerade KTH: 75%
Prestationsgrad totalt KTH: 92%
Examinationsgrad förstagångsregistrerade KTH: 59% (67 godkända av 113 registrerade)
Prestationsgrad SU: 75%
Examinationsgrad SU: 75% (3 godkända av 4 registrerade)

STATISTIK efter ordinarietentan (inklusive äldre elever)

LABBSTATISTIK
  Labb nr 1: 109, 2: 94, 3: 107, 4: 22
  Hela labbkursen: 93 st

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                  Medelbetyg
mas1    115       1 x U   58 x 3   40 x 4   16 x 5    3,6
mas2    108      11 x U   48 x 3   20 x 4   29 x 5    3,8
tenta   120      21 x U   42 x 3   57 x 4             3,6
munta    32       4 x U    3 x VG   7 x 4   18 x 5

49 var behöriga att gå upp på muntan, varav 20 inte var garanterade betyg 4 redan
(12 av dessa anmälda och 10 lyckades). 34 anmälde sig till muntan, men 2 kom inte.
28 klarade muntan, men en fick ett lägre betyg (4) än han satsat på.

SLUTBETYG (KTH)
 42 x 3 (52%)   20 x 4 (25%)  18 x 5 (22%)
medelbetyg: 3,7
 
SLUTBETYG (SU)
 0 x G (0%)   3 x VG (100%)
medelbetyg: VG

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

I och med Bologniseringen av högskolan utformade jag lärandemål och målrelaterade betygskriterier för kursen. För att kunna ge målrelaterade betyg var jag tvungen att modifiera examinationen. Jag hade Biggs (Biggs: Teaching for Quality Learning at University, 1999) princip om constructive alignment som vägledning, det vill säga att lärandemål, undervisning och examination bör hänga ihop, vara samstämmiga och underlätta meningsfullt lärande.

Jag formulerade betygskriterier för varje lärandemål, sammanlagt åtta stycken. För varje mål har jag angett hur det examineras. Tre av målen är inte graderade, det vill säga alla kriterierna är lika. Det var naturligt att göra så på grund av dessa måls natur och hur de examineras (med datorlabbar eller teoritenta).

Varje mästarprov bestod av tre uppgifter av olika svårighetsgrad. En rätt löst uppgift gav 3 på momentet, två gav 4 och tre gav 5. Uppgifternas svårighetsgrad motsvarade betygskriterierna för relevanta mål. Eftersom mästarproven redovisas muntligt kunde eleven korrigera mindre fel och ofullständigheter i den inlämnade skriftliga lösningen under redovisningen.

Teoritentan utfördes i storsal och följdes omedelbart av genomgång av lösningarna och rättningsmallen. Varje tentand fick sedan rätta en (anonym) kamrats tenta. Jag snabbgranskade elevrättningarna konstaterade att dom i stort sett helt och hållet var korrekt utförda. Jag kunde rapportera in resultatet på tentadagens kväll.

När jag införde betygskriterier ersatte jag problemtentan med en munta för högre betyg. Jag ville gå ifrån den kompensatoriska examinationen (Ekecrantz: Målrelaterade betyg, 2007), och då såg jag ingen möjlighet att behålla problemtentan. På muntan begärde tentanden att få frågor på en viss betygsnivå och fick då visa att han behärskade det som krävs för det betyget för alla mål som han tidigare inte examinerats på på den nivån.

En exjobbare (Emma Enström) började i april att som sitt exjobb utforma en ny laboration på komplexitet. Det har nämligen saknats en labb som introducerar NP-fullständighetsreduktioner på ett enkelt och tydligt sätt. Den resulterande labben blev klar till sista föreläsningen och delades ut som en frivillig fjärde labb i kursen. 22 elever valde att göra och redovisa labben. Dessutom gjorde 5 elever labben som ommästarprov 2. I labben ska man implementera en komplexitetsreduktion mellan ett av två känt NP-fullständiga problem och ett givet nytt problem. Reduktionen ska sedan testas av Kattis. Emma har skrivit utvärderingsfrågor på labben dels i den ordinarie kursutvärderingen och dels i en särskild utvärdering för dom som gjorde labben. Resultaten av utvärderingarna har lett till att Emma förbättrat labben, så att den till nästa år kan användas som ordinarie labb. Se vidare Emmas exjobbsrapport som kommer att presenteras i september 2007.

Sammanfattning av ändringarna inför denna kursomgång

Ny specialsammansatt kursbok (till största delen Keinberg-Tardos).
Något omarbetad labb 2 med exempelprogram.
Frivillig labb 4 (komplexitetsreduktion).
Målrelaterade betygskriterier har tillämpats.
Ny betygsättning av mästarproven.
Kamraträttad teoritenta.
Muntlig tenta för högre betyg.

Sammanfattning

Prestationsgrad och examinationsgrad ökade jämfört med förra året, liksom medelbetyget. Särskilt har antalet femmor ökat. Den nya målrelaterade examinationen bör göra det enklare att plugga för att få det betyg man vill ha. Det verkar ha fungerat väl.

I stort sett alla frågor i utvärderingen har årets elever svarat "mycket bra" eller "bra" till ungefär 10 procentenheters högre grad än förra årets elever. Jag tolkar det som att kursens nya upplägg fungerat väl.

En komplexitetslabb utvecklades och provades i år. Den kommer att bli obligatorisk i KTH-kursen nästa år.

Faktiskt innehåll i kursen

Kursen följde det planerade innehållet, sånär som att föreläsningen om effektiv kodning inte innehöll avlusningsteknik.

Elevernas synpunkter

Jag gjorde en kursutvärdering på webben efter teoritentan men före muntan. Den besvarades av 66 elever, varav 4 SU-studenter, 55 D-teknologer och 7 andra, vilket är 58% av antalet registrerade kursdeltagare, ungefär som förra året.

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

Kursinnehåll

Kursen ansågs vara ganska svår (50%) eller mycket svår (8%) av något mer än hälften, medan en tredjedel tyckte den var medelsvår. År 2006 var det tre fjärdedelar ansåg kursen vara svår. En klar minskning i år alltså, även om kursen fortfarande anses svår av många.

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

92% tyckte kursen var intressant (jämfört med 82% 2006).

Kurslitteratur

83% har använt den nya kursboken. Den har fått bättre betyg än tidigare års kursböcker, men avsaknaden av index kritiseras av många, med rätta. Det är något jag ska åtgärda till nästa år.

Det är fortfarande väldigt mycket att läsa, så de flesta hinner nog inte läsa allt. Förlitar sig på föreläsningsanteckningarna istället. Sen saknar jag väldigt mycket att det inte finns nåt index så att man kan slå upp en speciell sak. Det är oftast detta man använder boken till.
Jag tyckte att all text var på en bra nivå, och många av övningsuppgifterna var väldigt intressanta, men ett register hade ju varit bra att ha.

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 80% (mot 70% förra året). Föreläsningsanteckningarna delades ut i två buntar i förväg.

Mycket bra om de kompletteras av studenten med egna anteckningar.
Detaljerade, utförliga och korrekta. Bästa jag sett hittills, och lär vara de bästa jag någonsin ser.
Jättebra om man följer föreläsningarna. Men helt omöjliga att förstå om man missar någon föreläsning.

Jag har inte tänkt att föreläsningsanteckningarna ska vara självförklarande och ersätta kursboken.

Undervisningen

Kursen är upplagd så att den som vill läsa in den själv ska kunna göra det. Trots detta gick 58% (mot 43% förra året) på i stort sett alla föreläsningarna. 5% gick nästan inte på några föreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 81% medan 3% ansåg dom vara mindre bra eller dåliga.

Pedagogiken har varit mycket bra, men vissa avsnitt som kräver lite tid har gåtts igenom lite för fort.
Viggo förklarar stoffet bar och tydligt. En bra grej är att han faktiskt "kör" algoritmerna då det kan vara jobbigt att hänga med på vissa mer avancerade algoritmer.
Viss tendens att förklara lättare saker (tex algoritmkörningar) väldigt tydligt, men lite otydligare på de svårare områdena.
Mkt trevligt med en lärare som verkligen kan sina saker och dessutom är en lysande pedagog, det händer alldeles för sällan.

54% av eleverna gick på minst 60% av övningarna. Det är betydligt mer än förra året. Stefan Nilsson hade flest elever. 62% tyckte att övningarna pedagogiskt sett var mycket bra eller bra.

Var på större delen av övningarna hos Snilsson vilka var bra, kanske något ostrukturerade ibland :). 3 av dem provade jag dock Dicander vilka var mycket bra, Marcus var förberedd och inspirerande (p.g.a. hans kunskap och förmåga förklara svåra problem enkelt).
alla tre assar höll hög kvalitet
Mindre grupper och mer diskussion om problem skulle vara bättre. Ibland kändes det som övningsledaren helst ville ta sig igenom exemplen och sen stå och prata om egna intressen.

Övningarna får väldigt olika omdömen. Min tanke är att assistenten tillsammans med gruppen ska komma fram till en lämplig utformning av övningarna. Olika assistenter får gärna (ska helst ha) olika inriktning för att tillgodose olika behov. Flera anser att dom utdelade och lösta uppgifterna har hög svårighetsgrad. Jag ska uppmuntra assistenterna att göra några egna enkla exempel i början på varje övning.

Examinationsformen

Examinationsformen med en tredjedel av vardera labbar, mästarprov och tenta ansågs mycket bra (42%) eller bra (36%) av nästan alla. Något färre tyckte att betygsättning med betygskriterier var bra, men oavsett detta så är det krav på målrelaterad betygsättning i framtiden.

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

Var mycket skeptisk till kamraträttningen först, men det verkade fungera bra. Ger nyttig insyn i tentarättning dessutom! Dock ger rättningsmallen kanske en onödigt smal definition av rätt svar (tror att en person som rättar efter egen hjärna är benägen att acceptera fler svar, och fastnar kanske inte så mycket på att något uttryck saknas eller liknande).
För det första har det inte gett någonting om man fått 5:a på nått mästarprov, vilken inte har motiverat en att göra sista uppgiften om man klarat de två tidigare.
Kamraträttningen är trevlig i det att den minskar varje eventuellt intryck av godtycke i rättningen och kanske även faktiskt godtycke. Om än jag personligen tycker mycket illa om labbar och ännu sämre om bonuspoäng på tentor så är formen på det hela utmärkt till den grad att jag bara blivit lite irriterad på det hela.
Taskigt med betygsättning för varje steg, och taskig rättning på mästarproven. Borde vara så att man inte behöver ha ett visst betyg på alla delar för ett visst betyg, utan kompensationsbetygsättning. Om vissa skall få munta ska alla få göra det även om man har tex 2 stycken 3or.

Kamraträttningen blev för vissa en dramatisk insikt i hur rättning med rättningsmall fungerar. Min granskning av svaren efteråt visade att kamraträttningen fungerat mycket väl och att enstaka felaktiga (nästan alltid för hårda) bedömningar enkelt kunde rättas till. Ingen har klagat på sin rättning efteråt.

Jag har valt att på försök inte ha kompensatorisk betygsättning i kursen, och jag är mycket nöjd med resultatet. Med den nya betygsättningen har flera presterat bättre på kursen än förra året, och jag har intrycket att var och en som fått ett betyg verkligen har förtjänat det. Tidigare år har man med bonuspoäng och tur på tentan kunnat få ett högre betyg än motiverat.

Komplexitetslabben

Den frivilliga labb 4 som delades ut i slutet av kursen gjordes av 22 personer och fick gott betyg av dom flesta. Många ansåg att labben borde ingå i labbkursen nästa år. Den ska i så fall ligga i början av komplexitetsavsnittet av kursen så att den ger en bra övning inför mästarprov 2.

Kattis

I labb 2 och labb 3 användes för andra gången det automatiska programtestningssystemet Kattis. Kattis fick helhetsbetyget mycket bra eller bra av 80% (mot 51% förra året). Endast 3% ansåg det vara dåligt.

Mycket bra när felmeddelandena är välskrivna. Ett dåligt felmeddelande från Kattis kan leda till mycket frustration över små detaljer, t.ex format på utdata om det är dåligt specificerat.
Tyvärr får man sällan veta mer än att det är fel, vilket gör det jobbigt att felsöka då implementationer ofta fungerar på nästan all indata.
Väldigt frustrerande. Framförallt är tidsgränserna för java riktigt usla. I labb 2 klarade vi tidsgränserna för steg 1 och 2 utan problem, att sedan kombinera de två gav ett för långsamt program för steg 3, även med diverse effektiviseringar.

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, men genom att lägga testfallen i en genomtänkt ordning och genom att Kattis ger ett tips om vad som kan vara fel (om varje testfall förses med ett tips som visas för den som missar det testfallet) så blir det bli lättare att hitta felen i felaktiga program. Tidsgränserna ska ses över. Föreläsningen om effektiv Java ska kompletteras med tips om hur man avlusar program.

Feedback på mästarproven

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

Bra som examinationsform tycker jag, gillar hemtal bättre än tenta. Bra också med omedelbar feedback vid redovisningen, dels att man får ledande frågor vilket gör att det känns enklare (kanske inte meningen?), dels så förstod vad jag gjort för fel (när jag blev underkänd) och tror mig nu kunna göra ett nytt mästarprov med korrekta lösningar, tack vare Marcus feedback.
Verkade variera hur bra det gick beroende på vem man redovisade för...

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 synligt sätt. Detta är svårt att få fram till eleverna, men jag ska försöka ännu mer nästa år.

Glädje av kursinnehållet

80% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden (74% förra året). 3% tror sig inte ha nytta av mer än någon enstaka del av kurse. 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

Speciellt övningarna bör förbättras. Inte bara(eller inte alls) gå igenom de uppgifter som finns i övningshäftet då det ändå finns så utförliga svar där. Förslag är ju att övningsledaren först pratar lite allmänt om övningens ämne sen delar ut uppgifter som man ensam eller i grupp får klura på ett par minuter och sen går övningsledaren igenom uppgiften.
Om flera elever vill ha ett sånt upplägg så är det inga problem att ha en sån grupp. Redan nu är det möjligt för eleverna att påverka upplägget, men det är kanske svårt att i början veta hur man bäst vill arbeta med övningarna. Kanske ska assistenterna få olika bestämda upplägg i början av kursen och sedan anpassa sig efter elevernas vilja.

Jag tror avsnittet om oavgörbarhet måste struktureras lite bättre och få ett par slides till. I alla fall jag tyckte att det var lite svårt att förstå. Någonting som jag också saknar i de flesta kurser är ett *stort* utbud av räkneexempel med svar. Personligen behöver jag göra jättemycket exempel för att jag ska få rutin på problemlösningen. Ofta kommer förståelsen fortare om man får se lite olika synvinklar på samma problem. Man kanske också skulle dedikera en av övningsassistentera helt åt räknestuga. Det känns sällan bekvämt att ställa frågor på raster under föreläsningar och övningar.
Det kan vara värt att pröva att låta en assistent ha räknestuga, åtminstone ena övningstimmen.

En välstrukturerad kurs som kändes rolig att plugga till. På fråga två skrev jag att jag upplevde kursen som medel i svårighetsgrad. Svårighetsgraden är hög men med bra pedagogik så upplevs den som lättare.

Kursen är intressant och känns viktig. I början var jag lite tveksam, men under kursens gång har ämnet blivit mer och mer intressant.

Anpassning till andra kurser

Kursen samordnades med Diskret matematik för D2 som för andra året gick över både period 3 och 4. Det har fungerat ganska bra.

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

Gör labb 4 (komplexitetsreduktioner) obligatorisk.
Se över tidsgränserna i Kattis.
Planera dom olika övningsassistenternas upplägg i förväg.
Föreläsningen om effektiv Java ska kompletteras med tips om hur man avlusar program.
Lägg med ett index till kursboken i kursbunten.
Modifiera betygskalan till A, B, C, D, E.

Upp till kursomgången våren 2007.