Kursanalys f�r DD1352 Algoritmer (datastrukturer) och komplexitet, v�ren 2010

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.

Kursdata per 7 juni 2010

Tid: period 3-period 4 l�s�ret 2009/2010 dvs januari-maj 2010
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: 34 timmar.
�vningar: 24 timmar.
Kursledare och f�rel�sare: Viggo Kann
�vningsassistenter: Torbj�rn Granlund (doktorand i datalogi), Marcus Dicander och Jonas Sundberg (D-teknologer).
Antal registrerade elever, KTH: 139 varav 136 fr�n D, 2 fr�n CL, 1 fr�n Media.
Antal registrerade elever, SU: 10.
Prestationsgrad f�rstag�ngsregistrerade KTH: 72% (jfr 75% �r 2009)
Prestationsgrad totalt KTH: 86% (85% �r 2009)
Examinationsgrad f�rstag�ngsregistrerade KTH: 53% (74 stycken; jfr 60% �r 2009)
Prestationsgrad SU: 82%
Examinationsgrad SU: 70% (7 godk�nda av 10 aktiva)

STATISTIK efter ordinarietentan (inklusive �ldre elever)

LABBSTATISTIK
  Labb nr 1: 148, 2: 133, 3: 136, 4: 141
  Hela labbkursen: 119 st (jfr 111 st �r 2009)

M�STARPROV, TEORITENTA OCH MUNTA
Prov  Antal inl  Betygsf�rdelning                                 Medelbetyg
mas1    155      17 x F   75 x E   12 x D   43 x C    2 x B    6 x A    1,9
mas2    144      17 x F   79 x E    7 x D   19 x C    2 x B   20 x A    2,0
tenta   150      30 x F   53 x E   40 x D   27 x C      -        -      1,6
x-labb4  30         -        -        -        -      4 x B   26 x A    4,9
munta    21         -        -        -      4 x C    6 x B    9 x A    3,9

22 anm�lde sig till muntan. 19 klarade den (varav tv� med l�gre betyg), tv� missade,
en d�k inte upp.

SLUTBETYG
 59 x E    6 x D    11 x C     7 x B    14 x A
medelbetyg: 2,1 (jfr 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

Tre av fyra f�r�ndringar som planerades i f�reg�ende �rs kursanalys genomf�rdes:

N�stan alla f�rel�sningar har varit entimmespass f�r att b�de elevernas och f�rel�sarens koncentration ska vara h�g.
P� f�rel�sningarna har algoritmsimuleringar p� dator visats n�r det �r m�jligt.
Labblydelserna, m�starprovslydelserna och tentalydelsen har g�tts igenom noggrant s� att formuleringarna ska vara entydiga.
En f�r alla tillg�nglig upps�ttning testfall har genererats f�r labb 2, 3 och 4X.

Sammanfattning

Kursen fungerar bra rent praktiskt, men det h�ga antalet elever som bara f�r betyg E liksom flera kommentarer p� kursenk�ten visar att en betydande del av D-teknologerna inte �r mogna att tillgodog�ra sig kursen v�l. Kursen kommer d�rf�r att flytta fr�n v�ren i �rskurs 2 till h�sten i �rskurs 3 p� D. �ven kursen Diskret matematik g�r samma flytt. D�rmed ligger ADK efter Matematisk statistik och Databasteknik, varf�r det finns sk�l att tro att mognaden och motivationen hos D-teknologerna kommer att vara st�rre n�sta g�ng kursen g�r. I och med detta kommer det ocks� att vara m�jligt att g� in mer p� probabilistisk algoritmanalys och probabilistiska algoritmer.

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 65 elever, varav fyra SU-studenter, 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 (55%) eller mycket sv�r (11%) av lite mer �n h�lften, medan 3% 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, j�mf�rt med 8% f�rra �ret.

80% tyckte kursen var intressant (j�mf�rt med 88% 2009, 81% 2008 och 91% 2007).

Kurslitteratur

Indakursens kursb�cker f�rra �ret kunde anv�ndas som ADK-kursb�cker, varf�r dom flesta inte beh�vde skaffa n�gon ny bok. 60% har anv�nt kursboken. En fj�rdedel tyckte att boken �r mindre bra eller d�lig. Kommentarerna �r mots�gelsefulla - vissa skriver att boken �r enkel att l�sa och f�rst� och andra att den �r torr och tr�kig. Flera kommenterar att man kan klara sig l�ngt med anteckningarna och Wikipedia.

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 45%, j�mf�rt med 74% f�rra �ret. Anteckningarna var i stort sett samma - enda v�sentliga skillnaden var att dom fanns p� papper i kursbunten f�rra �ret.

lite tydligare f�rklaringar skulle vara bra. om man missat en f�rel�sning kan det ibland vara sv�rt att f�rst� allting.
V�ldigt helt�ckande och mycket bra att ha om man missat m�nga f�rel�sningar.
Bra att de finns, men de �r ganska sv�rl�sta. Det �r ocks� sv�rt att hitta det man letar efter, man f�r ofta g� in i m�nga olika pdf:er och leta.
Jag tror mer p� en samlad lista �ver problem, algoritmer respektive datastrukturer med beskrivning, komplexitet, m.m.
Handskriva anteckningar g�r att det k�nns mer personligt. Grafer och liknande blir �ven mer tydliga.

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. 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. Inget viktigt �mnesinneh�ll fr�n f�rel�sningarna saknas i f�rel�sningsanteckningarna.
Jag gillar handskrivna anteckningar. En lista �ver kursens algoritmer och problem med komplexiteter finns p� kurswebbsidan. Det tycks som om kritiken mot anteckningarna till st�rsta delen �r ett informationsproblem: vissa elever har inte f�rst�tt hur f�rel�sningsanteckningarna �r t�nkta att anv�ndas.
N�sta �r ska jag vid kursstart erbjuda alla f�rel�sningsanteckningar och �vningsanteckingar p� papper f�r sj�lvkostnadspris.

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. 14% gick n�stan inte p� n�gra f�rel�sningar. Pedagogiskt sett ans�gs f�rel�sningarna mycket bra eller bra av 59% (52% f�rra �ret och 60% f�r tv� �r sen) medan 23% ans�g dom vara mindre bra eller d�liga (10% f�rra �ret).
65% f�redrar entimmesf�rel�sningar i kursen och 18% f�redrar tv�timmesf�rel�sningar.

Viggo �r strukturerad, talar tydligt, f�rklarar koncist och kommer i tid. En m�nsterl�rare! :-)
Lite b�ttre "fart", k�nns som att det inte riktigt hinns med pga av fr�gor.
Har varit en del kr�ngel med java-applets f�r demonstration av olika algoritmer, testa mer i f�rv�g och spara ner dem p� f�rel�sarens dator s� att de alltid �r �tkomliga p� f�rel�sningen.
F�r l�nga exempel. Du hinner med 1 max 2 exempel p� dessa korta lektioner.
Mer korta och olika exempel. Ingen vill veta om TSP 700 g�nger.
Korta koncisa f�rel�sningar �r l�ttare att ta till sig �n tunga tv�timmarsoreringar. Ett bra initiativ som b�r spridas genom svenska h�gskolor.
Jag har inte orkat �ka in till skolan bara f�r en entimmesf�rel�sning. Id�n �r bra, men den funkar inte om det inte �r s� att alla kurser p� KTH �r entimmespass. Dessutom har det tydligen ofta varit s� att lektionen dragit �ver f�r att du (Viggo) inte hunnit med allt i tid.

F�rel�sningarna har i �r strukturerats om helt och h�llet och gjorts om till mestadels entimmespass. Dessutom har algoritmvisualisering p� dator gjorts d�r det �r m�jligt. Dessa visualiseringar strulade vid n�gra tillf�llen, mestadels i b�rjan av kursen och delvis p� grund av orutin - jag hade f�rberett noga men inte insett att sj�lva projektorinkopplingen ocks� kan p�verka animationerna. Det kommer nog att fungera b�ttre n�sta g�ng - jag tycker att det har varit givande n�r det fungerat, och det har det oftast gjort.
Jag tycker att entimmesf�rel�sningar �r mycket mer stimulerande �n tv�timmesf�rel�sningar och jag ser betydligt f�rre sovande elever i f�rel�sningssalen.
St�rsta problemet �r som vanligt spridningen i niv�, f�rkunskaper och behov hos eleverna som g�r det om�jligt att tillfredsst�lla alla. Med entimmesf�rel�sningarna har jag kunnat st�lla h�gre krav p� att eleverna f�rberett sig till f�rel�sningarna. Det tycks vara dom som inte f�rberett sig som tycker f�rel�sningarna �r f�r sv�ra.

67% av eleverna gick p� minst 60% av �vningarna, mot 55% f�rra �ret. Grupperna var n�gorlunda j�mnstora. 64% tyckte att �vningarna pedagogiskt sett var mycket bra eller bra, en liten minskning mot f�rra �ret, men � andra sidan var det flera som gick p� �vningarna.

Jag tycker att Jonas va v�ldigt duktig och pedagogisk. Det var mycket man inte f�rstod p� f�rel�sningarna som blev klarare p� �vningarna.
Mycket b�ttre och l�rorikare �n f�rel�sningarna! Tyv�rr har jag inte haft tid att g� p� alla, men de jag har varit p� har varit v�ldigt bra. Jag har varit p� �vningar hos alla tre och de �r riktigt bra hela bunten!

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 eller bra av n�stan alla (81%). Majoriteten 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 (89%) tyckte att kamratr�ttning av teoritentan var bra eller �tminstone acceptabelt.

J�ttebra att f� flera m�jligheter. Betygssystemet var lite r�rigt i b�rjan och det var sv�rt att f�rst�, men nu i slutet �r jag glad �ver det. Det g�r att det fokuseras med p� att faktiskt kunna saker �n att f� flest po�ng p� tentan, och man �r inte helt k�rd om man missar ett moment i b�rjan p� kursen. Systemet med bonuspo�ng g�r att man faktiskt g�r labbar i tid och hj�lper p� s� s�tt med planeringen.
Jag anser att det �r ganska h�rt att ha tre moment p� kursen, och slutbetyget blir det l�gsta av de tre. Ett snittv�rde hade varit mer representativt f�r elevens kunskaper. Tentorna anser jag vara f�r inriktade p� smala kunskaper som visar att man har koll p� sm� algoritmer som g�tts igenom p� n�gon f�rel�sning under kursens g�ng. En tenta som �r utformad f�r att testa eleven p� mer djupg�ende teoretiska kunskaper som �r kursens egentliga budskap.
Lite h�rt att betyget enbart s�tts av l�gsta betyget, det borde viktas. Bra att man kan plussa muntligt dock. Extralabben borde kunna redovisas under labbveckan ocks�.

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 7 fall. I tv� fall har ett betyg dragit ner fr�n A till C, i fyra fall har ett betyg dragit ner fr�n C till E. I ett enda fall har slutbetyget dragits ner mer �n tv� 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. M�nga har ocks� gjort det. 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.

Jag utformade tentan f�r att den till allra st�rsta delen skulle testa de viktigaste teoridelarna av kursen. Bara en delfr�ga (v�rd 2 po�ng) testade kunskap om en specifik datastruktur (Bloomfilter och hashning). Jag h�ller allts� inte med om att tentan testade detaljkunskaper.

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 3% ans�g att labben var f�r arbetskr�vande. Komplexitetslabbens inverkan har studerats i ett nyligen presenterat konferensbidrag 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 83% (mot 71% f�rra �ret och 65% �ret innan). Endast 6% ans�g systemet vara mindre bra eller d�ligt. Trenden �r att eleverna uppskattar Kattis allt mer.

J�ttebra att Kattis anv�nds! Det �r v�ldigt sk�nt att f� svart p� vitt att man har klarat uppgiften.
Ganska roliga labbar faktiskt. Kattis g�r sitt jobb men �r sjukt tr�g p� att beskriva vad som g�tt fel. N�gra till testfall hade nog varit bra till hands till labbarna.
Som flera s�kert sagt s� skulle mer information sitta fint. Det var tr�kigt att missa en bonuspo�ng och tid f�r att fastna p� ett problem som ingen annan st�tte p� eller kunde f�rklara.

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! I �r la jag till en helt �ppen extra upps�ttning testfall f�r varje labb. D� kunde eleverna testa och avlusa programmet mot dessa testfall f�rst. Jag tror att detta har hj�lpt, men det finns fortfarande elever som fastnar f�r l�nge p� vissa testfall n�r programmet �r fel eller f�r l�ngsamt. Kattis kommer att uppdateras och feedbacken fr�n testfallen kommer att ses �ver till n�sta kursomg�ng.

Feedback p� m�starproven

De flesta tyckte att l�rarens feedback vid muntliga redovisningarna av m�starproven var mycket bra eller bra. Bara 11% (mot 16% f�rra �ret) ans�g att feedbacken var mindre bra eller d�lig.

Mycket bra s�tt att examinera. Man f�r tid till att t�nka sj�lvst�ndigt och hitta egna l�sningar till problem, bra att sedan f� diskutera sina l�sningar med en assistent f�r att f� ytterliggare f�rst�else. Mycket bra!
Efter att ha diskuterat m�starproven (i efterhand :P) verkar det som om assarnas bed�mningar av m�starproven har varit olika h�rda. En bekant till mig hade i princip identisk l�sning men blev underk�nd d� jag blev godk�nd.
Jag k�nde att jag fick brottom p� redovisningarna. Att f�rl�nga tiden kanske inte �r l�sningen. Men det kan vara bra att understryka att man ska kunna redovisa allt p� utsatt tid, och att man ser till att l�mna in l�sningar som inte blir f�r tidskr�vande att f�rsvara.
Jag gjorde omm�starprov 2 och klarade inte det p.g.a. att det var ett optimeringsproblem som man skulle g�ra om till ett beslutsproblem och sedan bevisa NP-fullst�ndighet. D� det f�rsta m�starprovet gav dig ett beslutsproblem s� borde �ven omm�starprovet ge dig ett beslutsproblem och inte n�got "nytt".

Med assistentm�ten och bed�mningsregler f�rs�ker jag f� bed�mningarna s� lika som m�jligt. Jag har studerat assistenternas genomsnittsbed�mningar, och de skiljer sig inte �t p� n�got misst�nkt s�tt. 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 redovisningarna �r olika. Detta har alltid varit sv�rt att f� fram till alla elever.

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�.

Problemet i omm�starprov 2 var ett optimeringsproblem som f�rst skulle skrivas om till ett beslutsproblem. Detta �r en standardtransformation som �r en viktig del av kursen och som alla som blir godk�nda p� kursen ska beh�rska. Jag ska inf�ra extra �vningsuppgifter specifikt om detta.

S�rbehandling och genus

Bara en ans�g sig ha blivit utsatt f�r s�rbehandling, och den personen gav kommentaren: algoritmerna fucked min hj�rna ibland (dvs psykologiisk sexualitet). Dom flesta hade inte funderat �ver kursens genusperspektiv eller tyckte ens att det var n�got som hade med kursen att g�ra. En positiv kommentar var: Det �r trevligt med en kurs i programmering d�r man inte behandlas speciellt bara f�r att man �r tjej, utan folk ses som m�nniskor i st�rre utstr�ckning. Tummen upp!

Gl�dje av kursinneh�llet

67% tror sig ha nytta av hela eller en hel del av kursinneh�llet i framtiden. En enda person tror sig inte ha nytta av kursen alls. 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

Intressant kurs och ett uppl�gg som st�ller krav p� eleverna. Bra allt som allt!
v�ldigt sv�r kurs. men att den �r intressant och rolig v�ger upp.
En riktig kvalitetskurs. F�rmodligen den b�sta jag l�st p� KTH hittills.
Vi �r flera som g�r SU-varianten av kursen som tycker att v�r s�rbehandling minskar v�ra chanser att f� h�ga betyg p� kursen, j�mf�rt med KTH:arna. Vi resonerar s� h�r:

Vi f�r bara 7,5 hp f�r kursen. De moment vi "slipper" m�ste kth:arna g�ra, men om vi vill ha extra bonus m�ste vi ocks� g�ra dessa moment. F�ljaktligen f�r vi antingen sv�rare �n de andra att f� h�gre betyg eller s� m�ste vi g�ra lika mycket arbete som de andra - men f�r fortfarande mindre antal po�ng. Observera att vi antagligen har mer att g�ra utanf�r adk:kursen �n de som f�r mer po�ng f�r kursen, eftersom att vi ocks� l�ser p� heltid!
Kanske skulle ha n�gon labb d�r man f�r prova p� att l�sa problem med dekomposition och dynamisk programmering i praktiken, g�r just nu bara igenom det teoretiskt.

Dynamisk programmering brukar vara sv�rt att l�ra sig. Det finns flera uppgifter i Kattis som tr�nar dynamisk programmering, s� till n�sta g�ng f�resl�r jag n�gra s�na uppgifter.

SU kommer inte att l�sa kursen tillsammans med ADK n�sta g�ng utan ist�llet tillsammans med Algoritmer och komplexitet f�r F med flera. Den kursen �r utan labbkurs, s� problemet med bonuspo�ng kommer att finnas kvar men vara till SU-studenternas f�rdel i framtiden.

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

Kursen flyttas till h�sten i �rskurs 3 och ges n�sta g�ng h�sten 2011.
Ta upp probabilistisk algoritmanalys och probabilistiska algoritmer i kursen.
Vid kursstart erbjuda alla f�rel�sningsanteckningar och �vningsanteckingar p� papper f�r sj�lvkostnadspris.
Kattis kommer att uppdateras och feedbacken fr�n testfallen kommer att ses �ver.
N�gra enkla �vningsuppgifter ska l�ggas till. Tips p� fler �vningsuppgifter och programmerings�vningar f�r den som vill �va mer kommer att ges.