bild
Skolan för
elektroteknik
och datavetenskap

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

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 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ändes för första gången betygskalan A-F och på SU-kursen G och VG, där gränsen för VG motsvarar gränsen för B.

Kursdata per 16 juni 2008

Tid: period 3-period 4 läsåret 2007/2008 dvs januari-maj 2008
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: Andreas Lundblad (doktorand i datalogi), Marcus Dicander och Leo Giertz (D-teknologer).
Antal registrerade elever, KTH: 149 varav 132 från D, 7 från F, 5 från IT, 1 från CL, 1 från I, 1 från Media, 1 magisterstudent, 1 fristående kurs.
Antal registrerade elever, SU: 3.
Prestationsgrad förstagångsregistrerade KTH: 72%
Prestationsgrad totalt KTH: 85%
Examinationsgrad förstagångsregistrerade KTH: 56% (83 godkända av 149 registrerade)
Prestationsgrad SU: 83%
Examinationsgrad SU: 67% (2 godkända av 3 registrerade)

STATISTIK efter ordinarietentan (inklusive äldre elever)

LABBSTATISTIK
  Labb nr 1: 127, 2: 106, 3: 130, 4: 126
  Hela labbkursen: 103 st

MÄSTARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsfördelning                                 Medelbetyg
mas1    141      26 x F   56 x E   12 x D   21 x C   10 x B   16 x A    1,8
mas2    139       7 x F   66 x E    3 x D   35 x C    3 x B   25 x A    2,1
tenta   124       6 x F   26 x E   32 x D   73 x C      -        -      2,3
x-labb4  18         -        -        -        -      2 x B   16 x A    4,9
munta    29       7 x -      -        -      8 x C   11 x B    3 x A    3,8

54 var behöriga att gå upp på muntan, varav 27 inte var garanterade betyg C eller bättre redan. 29 gick upp på muntan. 
22 elever klarade den, men 4 med lägre betyg än dom anmält sig för.


SLUTBETYG (KTH)
 60 x E    4 x D    15 x C     8 x B    16 x A
medelbetyg: 2,2
 
SLUTBETYG (SU)
  0 x G    2 x VG
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

Alla förändringar som planerades i föregående års kursanalys genomfördes:
  • Labb 4 (komplexitetsreduktioner) har införts med tillhörande teoriuppgiftsredovisning.
  • Labbarnas tidsgränser i Kattis har setts över så att ingen labb ska vara onödigt svår att klara tidskravet på.
  • Övningsgrupperna hade olika svårighetsgrader, bestämda i förhand.
  • Föreläsningen om effektiv Java kompletterades med tips om hur man avlusar program.
  • Ett index till kursboken ingick i kursbunten.
  • Betygskalan modifierades till A, B, C, D, E.
Utöver detta infördes en extrauppgift i labb 4 för det sista betygskriteriet och en extralabb för algoritmkonstruktionsbetygskriteriet. 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 var marginellt lägre än förra året, men fortfarande höga. 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 lägre betyg. Medelbetyget var ungefär som förra året, men andelen elever som fick högsta betyget var aningen mindre i år.

Den nya komplexitetslabben fungerade mycket väl och var en god hjälp inför mästarprov 2.

Största kritiken i kursenkäten drabbade priset på kursboken. Nästa år kommer därför samma bok att användas som i Indakursen, och bara ett mindre supplement behöver köpas till för ADK.

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 2 SU-studenter, 55 D-teknologer och 5 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 (46%) eller mycket svår (16%) av lite mer än hälften, medan en resten tyckte den var medelsvår. Det var dubbelt så många som förra året som ansåg att kursen var mycket svår. Å andra sidan var det betydligt fler år 2006 som ansåg kursen vara svår.

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

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

Kurslitteratur

60% har använt kursboken, som var samma som förra året. Av dessa tyckte en tredjedel att boken är mindre bra eller dålig. Den har dock fått bättre betyg än tidigare kursböcker.
  • Kommer inte så mycket till använding, mycket exempel, vilket iofs är bra, men det mesta täcks väl av föreläsningarna. Kom väl till hands inför mästarproven.
  • Alldeles för dyr för den begränsade nytta man hade av den. Hur mycket tjänade kursledaren på att 120 personer så gott som tvingades köpa boken?
  • Försök om möjligt samordna algoritmbok med Inda-kursen, böcker är dyra!
  • Tydlig. Välldigt bra kopplad till kursinnehållet.
Jag har valt ut vilka kapitel boken ska bestå av för att precis täcka kursinnehållet, men jag själv tjänar inte ett öre på boken. På grund av labbarna och samordning med andra kurser läses inte kapitlen i bokens ordning. Nästa år kommer boken att samordnas med Indakursen, vilket innebär att Indakursens bok Algorithm Design används i ADK och kompletteras med ett supplement med dom cirka 80 sidor ur andra böcker som inte ingår i Indaboken. Då minskar kostnaden till omkring 120 kronor.

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% (samma som förra året). Föreläsningsanteckningarna ingick i kursbunten som såldes vid kursstart.

  • Mycket bra, mycket användbara. Kan påpekas för senare studenter dock att de bör kompletteras (och kanske bör det ges lite mer plats för det i anteckningarna) med lite egna förklaringar för att man ska kunna komma ihåg inför mästarprov, tenta, labbar osv.
  • Lite otydliga ibland, eller rättare sagt när man har föreläsningen samtidigt så är de lätta att förstå men när man ska komma ihåg vad de handlade om senare kan det vara lite knepigt. Men överlag bra.
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.

Undervisningen

Kursen är upplagd så att den som vill läsa in den själv ska kunna göra det. Trots detta gick hälften på i stort sett alla föreläsningarna. 8% gick nästan inte på några föreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 60% (81% förra året) medan 9% ansåg dom vara mindre bra eller dåliga.
  • Föreläsningarna var väldigt bra ibland vart det dock lite för mycket ibland men det kan kännas att jag som student bör ha läst mer utav materialet innan föreläsningen så man förstod mera.
  • Algoritmer brukar förklaras med tydliga och bra exempel, däremot tycker jag för mycket tid lades på sådant som är lätt jämfört med hur mycket tid som lades på sådant som var svårt (t.ex. FFT, undre gränser etc)
  • Ibland för monotont.
  • vigga är en väldigt pedagogiskt lärare. toppklass
62% av eleverna gick på minst 60% av övningarna, något mer än förra året. Leo hade flest elever. 69% tyckte att övningarna pedagogiskt sett var mycket bra eller bra.
  • Det kändes som det var på övningarna man verkligen förstod vad kursen handlade om och hur man använder kunskaperna i praktiken.
  • alla assar var bra
  • Jag skulle personligen föredragit mer genomgång och mindre diskussion.
Elevernas olika nivå, förkunskaper och behov gör att det inte går att tillfredsställa alla på föreläsningarna. Jag går igenom dom viktiga grunderna och nya begreppen grundligt, vilket vissa tycker går för långsamt. Sedan ägnar jag mindre tid åt vissa algoritmer och bevis som man kan läsa detaljerat om i boken, vilket en del elever tycker går för snabbt.
På övningarna går det bättre 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 (37%) eller bra (43%) 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.

75% var positiva till kamraträttning av teoritentan och bara 2% var negativa. Det är bättre omdöme än förra året, och uppseendeväckande gott med tanke på att tentaformen skiljer sig dramatiskt från vanliga tentor på KTH.

  • Tyckte det var intressant att se hur rättningen går till och samtidigt få inblick i hur resterade del av kursdeltagarna svarat jämtemot en själv.
  • Snabbt och effektivt metod, lagom svårt och väldigt relevant.
  • Jag hade föredragit ett "snällare" system, där kanske medelbetyg istället för min-betyg sätter kurs-betyget. Labbarna var mest givande i hela kursen.
  • Mästarproven var irriterande och kändes som en KS som gjorts onödigt komplicerad. Gör dem till icke-obligatoriska (de kan t.ex. ge bonuspoäng istället) och testa kunskaperna på tentan. Betygssystemet är alldeles för invecklat och den mängd arbete som krävs för A resp. C är helt oproportionerlig.
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. Ingen har klagat på sin rättning efteråt.
Jag valde förra året att inte ha kompensatorisk betygsättning i kursen. Jag tycker att det är mycket tilltalande, men det gör att snittbetyget blir lägre och att betygsfördelningen förändras från en normalfördelning till en nästan likformig fördelning.
Det ska inte kräva mycket mer arbete att lösa uppgifterna för betyg A och C på mästarproven än E-uppgifterna. Däremot kräver dom svårare uppgifterna mer problemlösningsförmåga.

Komplexitetslabben

Den nya labb 4 infördes för att ge bättre förståelse för NP-reduktioner. Fyra av fem elever ansåg att labben också gjorde det. Bara 5% ansåg att labben var för arbetskrävande. Jag tror att labb 4 var en förklaring till att resultatet på andra mästarprovet blev bättre än på det första.

Kattis

Det automatiska programtestningssystemet Kattis används för tredje året i kursen. Kattis fick helhetsbetyget mycket bra eller bra av 65% (mot 80% förra året). Endast 5% ansåg det vara dåligt.
  • Det var ju bra att veta att ens program funkade för det flesta indata innan man redovisade. annars kan det hända att man ibland glömmer konstiga fall.
  • Kattis rättar juh snabbt dock så känns det som man borde ha fått lite mer info om vad det var för fel, fast det var juh en poäng i sig att försöka debugga sig själv.
  • Bra att Kattis ger ledtrådar om vad som är fel.
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.

Feedback på mästarproven

De flesta tyckte att lärarens feedback vid muntliga redovisningarna av mästarproven var mycket bra eller bra. Bara 14% ansåg att feedbacken var mindre bra eller dålig.
  • MP1 var för svårt. Dessutom tycker jag att svårighetsgraderna på båda mästerproven var missvisande. På MP1 var 2an mycket lättare än 1an, på MP2 var 3an mycket lättare än 1an och 2an. Jag tror det vore bättre att skippa svårighetsgraderingen helt då det troligen är väldigt induviduellt vilka uppgifter som man har lätt/svårt för.
  • Jag hade ju gjort rätt på mina mästarprov så var inte så mycket att säga om dem. Bra och avslappnat förhör.
  • Olika assar var olika hårda med bedömning.
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 har alltid varit svårt att få fram till eleverna, men jag tror att jag lyckats bättre med det i år än förra året. Flera klagade på att svårighetsmärkningen på mästarproven inte stämde. Olika personer tycker att olika uppgifter är svåra. Jag har utgått från betygskriterierna när jag gjort märkningen. Nästa år ska jag sätta ut betygskriteriet istället för svårighetsmärkningen. Att andra mästarprovet ansågs lättare än det första beror nog på att labb 4 var en förövning för mästarprov 2. Teoriuppgifterna till labb 2 borde kunna fungera på motsvarande sätt som en förövning till mästarprov 1, men det har dom tydligen inte gjort.

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 hade varit bra med en kvinnlig övningsassistent. Det håller jag med om, men det är svårt att rekrytera det.

Glädje av kursinnehållet

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

Samma litteratur som i indan. Du och snilsson borde prata er samman och välja samma bok, vilken av dem har jag ingen synpunkt på, även om jag nog föredrog den vi hade i indan lite mer, men den täckte inte heller lika mycket. Att ni borde använda samma bok har jag två skäl till.
1) Det blir billigare för studenterna
2) Varje bok man läser har en viss inkörningstid innan man lär sig förstå pedagogiken och hur man ska sålla när man läser, dessutom är det lättare att hitta i en bok man läst innan. Detta gör att med samma bok skulle antagligen fler studenter nyttja boken, nu är det ju många som inte ens köpt den som du säkert ser i statistiken.

Jag håller med, så nästa år kommer Indakursens bok att användas tillsammans med ett supplement med dom delar som inte täcks av Indaboken.

Bättre förklaring av hur man får de olika betygen, vilka möjligheter och så vidare. Kanske flytta / lägg till ett par extra labbtillfällen till så att det finns lite mer tid för att slutföra extralabbar och sådant, blev väldigt stressigt på slutet, speciellt för de som gärna redovisar en labb för att få lite bättre betyg än att göra teoretiska problemuppgifter som i mästarproven.
Lägg inte ommästarproven dagen innan/samma dag som tentan, något av momenten kommer få mindre tid.
Första föreläsningen ägnar jag redan mycket tid åt att förklara betygskriterier och examination. Alla detaljer om hur betygsättningen går till står i kurs-PM och på kurswebbsidan. Jag ska skriva en tydligare text på webbsidan som ger några exempel på hur man får olika betyg.
Det vore möjligt att flytta ommästarproven till omtentaveckan i augusti, men jag tror att det blir bättre resultat om dom ligger kvar där dom ligger. Extralabbarna vill jag ska ligga före muntan så att slutbetygen är klara då muntan genomförts.

Tycker det är roligt med problemuppgifter så lägg in några fler problem i kattis som man kanske kan få några extra bonuspoäng för. Att lösa problem med programmering tycker jag är det bästa sättet att lära sig algoritmer.
Det finns redan många problem i Kattis som elever skulle kunna lösa för att få mer erfarenhet. Jag kan lista några lämpliga problem på kurswebben nästa år.

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

  • 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.
  • Lista några lämpliga övningsproblem i Kattis på kurswebbsidan.
Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2008-07-09