bild
Skolan för
datavetenskap
och kommunikation

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

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å labbkursen och betygen. Labbkursen för KTH-kursen är 2 poäng och består av tre labbar. Labbkursen för SU-kursen är 1 poäng och består av två labbar. 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

Tid: period 3-period 4 läsåret 2005/2006 dvs januari-maj 2006
Poängantal KTH: 6 (varav 2 på labb, 1 på mästarprov, 3 på tenta)
Poängantal SU: 5 (varav 1 på labb, 1 på mästarprov, 3 på tenta)
Tenta: ordinarietenta efter period, omtenta i augusti
Föreläsningar: 44 timmar.
Övningar: 24 timmar.
Kursledare och föreläsare: Viggo Kann
Övningsassistenter: Jakob Nordström, Isaac Elias, Martin Rehn (alla doktorander i datalogi) och Öjvind Johansson (forskare på SBC, endast period 3).
Antal registrerade elever, KTH: 128 varav 117 från D, 6 från magisterprogrammet i datalogi, 2 från CL, 1 från Media, 1 utbytesstudent och 1 fristående kurs.
Antal registrerade elever, SU: 5.
Prestationsgrad KTH: 68%
Examinationsgrad KTH: 55% (70 godkända av 128 registrerade)
Prestationsgrad SU: 64%
Examinationsgrad SU: 40%, (2 godkända av 5 registrerade)

STATISTIK efter ordinarietentan (inklusive äldre elever)

TENTASTATISTIK (KTH)
 19 x U (15%)   66 x 3 (54%)   28 x 4 (23%)  5 x 5 (4%)   5 x 6 (4%)
 Totalt 104 godkända av 123 tentander (85%)

TENTASTATISTIK (SU)
 1 x U (25%)  1 x G (25%)   2 x VG (50%)
 Totalt 3 godkända av 4 tentander (75%)

LABBSTATISTIK (KTH)
  Labb nr 1: 127, 2: 96, 3: 116
  Hela labbkursen: 94 st

LABBSTATISTIK (SU)
  Labb nr 1: 5, 2: 3
  Hela labbkursen: 3 st

MÄSTARPROV (KTH)
Prov  Antal inl  Medelp
 1      141        4.0
 2      124        4.2
Betyg på mästarprovsmomentet:
 83 x 3 (73%)   14 x 4 (12%)  17 x 5 (15%)
 Totalt 114 godkända.

MÄSTARPROV (SU)
Prov  Antal inl  Medelp
 1        6        4.0
 2        2        6.0
Betyg på mästarprovsmomentet:
 2 x G (50%)   2 x VG (50%)
 Totalt 4 godkända av 5 (80%)

SLUTBETYG (KTH)
 78 x 3 (76%)   16 x 4 (16%)  8 x 5 (8%)
 

Lärandemål

Kursens lärandemål är från och med i år att studenten efter kursen ska 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

  • Ny kursbok (val mellan Levitin och Kleinberg-Tardos).
  • Ändrad ordning (datastrukturer för algoritmer) för att kursen ska passa ihop med den utdragna kursen i diskret matematik.
  • Omarbetade labbar. Labb 2 och 3 testas automatiskt med Kattis.
  • Redovisning av labbteori på övningstid.
  • Betygsviktningen har modifierats.

Sammanfattning

Prestationsgrad och examinationsgrad var samma som förra året, men medelbetyget var lägre. Särskilt har antalet fyror minskat kraftigt. En orsak är den ändrade betygsavrundningen. Genomförandet av mästarprovet gick lika bra som förra året. Försöket med redovisning av labbteori på övningstid slog huvudsakligen väl ut. Efter första uppståndelsen gick redovisningarna smidigt. Försöket med datorrättade labbar (Kattis) föll också väl ut, trots vissa inkörningsproblem.

Till nästa år ska examinationen av kursen läggas om och tydliga betygskriterier införas. Det innebär bland annat att kraven på mästarprovsuppgifterna modifieras och att problemdelen av tentan byts ut mot en munta för den som vill ha högre betyg.

Faktiskt innehåll i kursen

Kursens faktiska innehåll finns beskrivet. Omfattande dokumentation av kursen finns också tillgänglig på kursomgångens webbsida.

Elevernas synpunkter

Jag gjorde en kursutvärdering på webben efter undervisningens slut och mästarprovens redovisningar men före tentan. Den besvarades av 78 elever, varav 4 SU-studenter, 76 D-teknologer och 4 andra, vilket är 61% av antalet registrerade kursdeltagare, lite fler än förra året.

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

Kursinnehåll

Kursen ansågs vara ganska svår (58%) eller mycket svår (15%) av tre fjärdedelar, medan 21% tyckte den var medelsvår. År 2005 var det bara hälften som ansåg kursen vara svår.

69% fick i början av kursen klart för sig vad kursens mål var, 26% var tveksamma och 5% svarade nej. Det är lite färre som svarat nej än förra året, men jag hade hoppats att dom nya tydligare målen skulle vara ännu lättare att förstå.

82% tyckte kursen var intressant (jämfört med 93% 2005 och 72% 2004).

Kurslitteratur

55% har läst Levitin som kursbok och 31% har använt Kleinberg-Tardos. Omdömena om båda böckerna var i stort sett normalfördelade. Många har valt att plugga enbart med föreläsningsanteckningarna. Det är svårt att hitta en bok som håller lagom nivå. Nästa år ska troligen utdrag ur Kleinberg-Tardos sammansatta till ett kompendium användas som kursbok.
  • Jag förstår att ni bytte, den gamla var mycket träigare men den här (Kleinberg-Tardos) var bra. Tar sig tid att förklara.
  • Föreläsningsanteckningar gör kurslitteraturen överflödig.
  • Tyckte inte att någon av böckerna var optmial för kursen. Levitin var för generell och gav inte svar på specifika frågor om kursmateriallet som dök upp under kursens gång. Google och wikipedia var nästan mer till hjälp.
  • Bra som introduktion men saknar det djupet jag är intresserad av. Jag vill nog ha en bok med fler algoritmer.

Föreläsningsanteckningarna (cirka 140 sidor), med kopior på alla stordiabilder som visades samt alla övningsuppgifter med lösningar, ansågs vara mycket bra (18%) eller bra (52%) av dom flesta. Veckans föreläsningsanteckningar delades ut i början av första föreläsningen varje vecka och fanns sedan tillgängliga inskannade på webben.

  • Suveränt! En fördel att de är handskrivna, det är trevligare att läsa.
  • Vissa var lite svåra att förstå om man inte hade varit med på föreläsningen i fråga.
  • Handskrivna inscannade anteckningar där det är en pdf för varje sida är dåligt bara det. Sen kan det vara svårt att läsa dem också. Bättre föreläsningsanteckningar!
  • Underbart att man kan koncentrera sig på att lyssna istället för att anteckna hela tiden.
Jag har inte tänkt att föreläsningsanteckningarna ska vara självförklarande och ersätta kursboken. Jag kommer att undersöka om det till nästa år är möjligt att göra en specialkomponerad bok som bygger på Kleinberg-Tardos.

Undervisningen

Kursen är upplagd så att den som vill läsa in den själv ska kunna göra det. Trots detta gick 43% 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 58% medan 9% ansåg dom vara mindre bra eller dåliga.
  • I början hade du med några lådor för att visa en sorteringsalgoritm. Det blev väldigt tydligt och skulle egentligen behövas mer längre fram i kursen.
  • Systematiskt. Ibland kan man lite mer om något, då blir det en låång väntan på nästa ämne, men det är uppenbart att förklaringarna behövs - en del frågor visar det. Bra hantering av frågor, både alltför avancerade frågor och alltför "dumma" frågor om något som nyss sagts.
  • Viggo är den första föreläsare (talare över huvud taget) jag haft som hållit bra föreläsningar trots att han anväder OH-bilder i stor utsträckning
  • Ibland ganska torra och svåra att hänga med på pga att materialet ju tar lite tid att smälta. men det är ok. Vad jag saknade var, som på alla kurser på kth, koppling till användningsområdeni verkligheten. du ga exempel, men vill ha massor fler, gärna lite coola exempel eller sådana där man stimuleras att använda kunskaper på nytt sätt.
39% av eleverna gick på minst 60% av övningarna. Det är betydligt mindre än förra året. Isaac Elias hade flest elever. 53% tyckte att övningarna pedagogiskt sett var mycket bra eller bra.
  • Martin är duktig och en väldigt pedagogisk övningsassistent
  • Jacob höll hög klass, även dicander.
  • Isaac var väldigt bra på att förklara och gav flera exempel. Dessutom var han duktig på att motivera oss elever och han var mån om att vi faktiskt förstod
  • Ojämn pedagogisk kvalitet på övningsassistenterna.
Alla assistenter får bra kritik av dom flesta. Omdömena varierar förstås, men det är fritt gruppval. Antalet övningsgrupper kan minska till nästa år eftersom så många väljer att inte följa övningarna.

Examinationsformen

Examinationsformen med till hälften tenta och till hälften labbar och mästarprov ansågs mycket bra (40%) eller bra (43%).
  • Det känns som att tyngdpunkterna i den här kursen var den informationen som man behåller för resten av arbetslivet och inte sånt som man lär sig på en tenta och sedan glömmer bort igen. Därför är det bra att vi får researcha inför mästarprov och labba med de algoritmerna vi lärt oss.
  • Det kan bli väldigt jobbigt om man inte klarar tentan men klarar mästarprov och labbar. Med tanke på upplägget tycker jag det verkar som om man nästan måste ha bonuspoängen för att ta tentan. Alltså måste man göra om labbar och mästarprov.
  • Mästarproven borde dock läggas upp annorlunda. Först lösa 3-uppgifterna, sedan 5-uppgifterna. Den som hade mest poäng var den som "gissade" rätt på vilken man skulle välja för att få flest bonuspoäng och högst betyg.
  • Mästarprovet är uruselt utformat! Det är värdelöst att behöva satsa på 5:a utan att först kunna trygga en 3:a (dvs 3 p. på mästarprovet)
  • Konstigt sätt att räkna fram slutbetyg: den enda kursen där man avrundar nedåt!
Förra året var nästan alla eniga om att mästarprov i två nivåer var bra. I år har många kritiserat det, mestadels för att man måste välja nivå och inte kan lämna in båda nivåerna. Nästa år kommer jag därför att tillåta att man lämnar in alla uppgifterna, se nedan om det nya examinationssystemet i kursen.

Teoriuppgifterna

Teoriuppgifterna på labbarna redovisades på prov på övningarna för en kompis, varefter assistenten tittade på den inlämnade lösningen och fastställde poängen. Denna modell ansågs mycket bra eller bra av 61%. 7% tyckte den var dålig.
  • Först ovant men sedan väldigt bra, kanske lite kort tid.
  • Bra att förklara för det krävs att man tänker till då.
  • Det är svårt att bedöma en annan persons svar utifrån de facit som givits. Ibland stämmer facit och svar inte exakt överens och då är det svårt att bedöma korrektheten, särskilt som man är nybörjare på området. Självklart förstår jag att det är ett sätt att minska lärarnas arbetsbörda.
  • Laborationernas teoriredovisningar på övningarna fungerade mycket dåligt. Varför ska studenter förhöra varandra? Och frågorna var ibland orelevanta och svårtydliga.
I huvudsak har modellen fungerat bra. Första gången var det lite stökigt på grund av elevers och assistenters ovana. Jag tror det är bra med flera olika examinationsformer så jag kommer att behålla modellen nästa år.

Kattis

I labb 2 och labb 3 användes för första gången det automatiska programtestningssystemet Kattis. Kattis är utvecklat inom ett pedagogiskt projekt stött av KTH Learning Lab och kommer att utvärderas och analyseras i större detalj där. ADK-eleverna gav Kattis helhetsbetyget mycket bra eller bra (51%) eller acceptabelt (29%). Endast 6% ansåg det vara dåligt.
  • Mera information om vad som krävs av programmet för att Kattis ska kunna köra det.
  • Ett väldigt smart och smidigt rättningssystem som gynnar både studenter och lärarna. Man får snabba svar på korrekthet, men även en tidtagning som uppmanar till att skriva smart och snabb kod.
  • Problemet med Kattis är när man gör något i Java. För det första finns ingen information om hur man skall arbeta med växelvis inläsning/utskrift, vilket blir mycket trial-and-error. Ett riktigt exempelprogram bör finnas.
  • När kattis säger "Wrong Answer" så skulle jag vilja ha mer information, allra helst den indata som gav felet så att jag kan testa själv. Det tog t.ex. lång tid för mig att hitta ett ord som gav fel svar i ordkedjor (för 99% av orden var svaret korrekt)
Införandet av Kattis gjorde att betydligt färre än tidigare år klarade matchningslabben (labb 2 i år, tidigare labb 1) i tid. Jag tror att det främst beror på att Kattis helt enkelt testar lösningarna mycket noggrannare än tidigare och att inte helt korrekta lösningar tidigare släpptes igenom. Totalt sett har Kattis varit mycket positivt för kursen och systemet kommer att användas även nästa år. Några modifieringar måste göras. Till exempel bör ett exempeljavaprogram finnas som visar principen för läsning och skrivning i första uppgiften på labb 2. 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 (varje testfall måste förses med ett tips som visas för den som missar det testfallet) så bör det bli lättare att hitta felen i felaktiga program. Föreläsningen om effektiv Java ska kompletteras med tips om hur man avlusar program.

Feedback på mästarproven

10% tyckte att lärarens feedback vid muntliga redovisningarna av mästarproven var mycket bra, 45% att den var bra och 30% att den var acceptabel. Bara 11% ansåg att feedbacken var mindre bra eller dålig.
  • Jag redovisade båda tillfällen för Per Austrin. Han hade läst igenom de inlämnade proven noga och påpekade brister. Dessa fick man under redovisningen en chans att rätta till. Det känndes som att man lärde sig något och fick en chans att redovisa sina kunskaper.
  • Jag fick inte veta de riktiga svaren på det jag svarat fel på. Så feedbacken var inte särskilt bra
  • Eftersom att man lämnar in något som man tror är rätt, så är det väldigt svårt att på en kvart förstå exakt vad man gjort fel och under samma tid försöka få fram vad man menade. För som det kändes nu var det bara att gå dit för att se om man gjort rätt eller inte.
  • Kul och bra övning. Bra att få diskutera övningen vid redovisningen!
Assistenten ska vid redovisningen koncentrera sig dels på dom felaktigheter som finns i den inlämnade lösningen och på elevens förståelse av sina egna lösningar. Det är eleven som ska kunna motivera att lösningen är korrekt. Assistenten får gärna tipsa om hur en riktig lösning ser ut, men ofta hinner man inte gå igenom hela den riktiga lösningen. Lösningsförslag läggs upp på webbsidan efter det att alla mästarprov redovisats.

Glädje av kursinnehållet

74% tror sig ha nytta av hela eller en hel del av kursinnehållet i framtiden (87% förra året). 4% tror sig inte ha nytta av mer än någon enstaka del av kursen (17% förra året). Detta visar att kursen är och uppfattas som central för utbildningen, villket är glädjande.

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

Den är mycket bra som den är.

Mer om HUR man motiverar att reduktionen är korrekt. När jag väl fattat hur man ska göra, åker jag dit på att jag ska motivera något annat...
Varje reduktion som gås igenom i kursen motiveras också. Jag är mycket noga med att gå igenom vad som ska bevisas i en reduktion. Hur ett bevis går till ska vara känt från mattekurserna. Det är svårt att göra mer åt denna synpunkt.

Kanske ha lite fler labbar, de var väldigt givande och motivarande.
Jag skulle gärna ha en labb på komplexitet. Förhoppningsvis kan en sån labb utvecklas inom ett exjobb parallellt med nästa kursomgång och testas på intresserade kursdeltagare.

Det största problemet är att det inte finns någon möjlighet att egentligen träna på liknande problemuppgifter som i tentamens andra del. Upplägget på föreläsningarna och övningarna är att föreläsaren/assistenten talar om lösningen. Knappt vid ett enda tillfälle i kursen beskrivs och diskuteras själva tankegången bakom lösningen. Detta medför att när det på tentan kommer problem som aldrig stötts på tidigare finns det ingen grund att börja bygga en lösning på. Huruvida uppgifterna klaras av eller inte beror inte på hur man hänger med i pluggandet utan snarare på tidigare erfarenheter utanför kursen.
Första delen av kursen innehåller en mycket ordentlig genomgång av algoritmkonstruktionsmetoder. För reduktioner görs ingen motsvarande genomgång av metoder, men dom problem som ges är så standardiserade att en genomgång av vanliga reduktionsmetoder skulle vara för avancerad för kursen. Jag har tänkt att övningarna ska vara påverkbara, så att den som har åsikter om hur assistenten ska gå igenom uppgifterna ska säga det och ofta kunna få sin vilja fram.

Mästarprovet tycker jag borde delas in i två delar, en för 3:a och en för 5:a. Där man måste göra och klara den för 3:a först. Delen för 5:a ger inga ytterligare bonuspoäng men ger möjligheten att lättare få 5:a totalt i kursen.
Nästa år kommer examinationen att ändras så att varje mästarprov blir obligatoriskt och betygsatt men inte ge några bonuspoäng. Varje prov får uppgifter av olika svårighetsgrad och man kan lämna in lösningar på alla om man vill.

Väldigt väl hållen kurs. Viggo borde ta en kurs med många på NADA om hur man lägger upp kurser. Jag har sällan lärt mig så mkt på en enda kurs. Otroligt välplanerad. Fortsätt så!

Anpassning till andra kurser

Kursen samordnades med Diskret matematik för D2 som i år gick över både period 3 och 4. Det gjorde att ordningen i ADK måste läggas om för att grafteorin skulle hinna gås igenom i matten innan den användes i ADK. 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

  • Undersök möjligheterna att göra en specialkomponerad bok som bygger på Kleinberg-Tardos kompletterad med annat material.
  • Den nyformulerade matchningslabben ska förtydligas i några detaljer.
  • Visa upp ett exempelprogram som visar hur inläsning och utskrift ska göras i första uppgiften i matchningslabben. Föreläsningen om effektiv Java ska kompletteras med tips om hur man avlusar program.
  • Målrelaterade betygskriterier ska införas och examinationen läggas om så att den uppfyller betygskriterierna. Mästarproven blir två obligatoriska moment om en poäng var. Varje mästarprov består av flera uppgifter med stigande svårighetsgrad, värda betyg 3, 4, 5. För att få ett betyg krävs helt rätt på den motsvarande uppgiften. Mästarproven ger inte bonus, men labbteoriuppgifterna ger bonuspoäng precis som i år. Den som missar ett mästarprov kan göra om det vid ett senare tillfälle i kursen. Tentan delas upp i en teoritenta (som kan ge betyg 3 eller 4) och en muntlig problemtenta för den som vill ha högre slutbetyg. För att få gå upp på muntan krävs högre betyg än 3 på minst två av dom tre momenten. Man kan få slutbetyg 4 utan att gå upp på muntan om man har fått minst 4 på alla tre moment. När man går upp på muntan får man tala om ifall man satsar på att få betyg 4 eller betyg 5.

^ Upp till kursomgången våren 2006.

Sidansvarig: <viggo@nada.kth.se>
Uppdaterad 2006-07-10