bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2440 / avalg10 / Kursanalys

Kursanalys: Avancerade algoritmer, avalg10

Kursdata

Tid: period 1-2 läsåret 2010-2011
Poängantal: 6hp
Examination: 2 projekt, 4 hemuppgifter
Föreläsningar: 30 timmar
Kursledare och föreläsare: Stefan Nilsson
Kursassistent Karl Palmskog, Cenny Wenner
Kurslitteratur: Utdelade artiklar. Se webbsidan.
Prestations- och examinationsgrad: 79% (73 av 92)

Mål

Kursens mål är att

  • öka förståelsen för effektiva beräkningar genom att förmedla metoder för att konstruera effektiva algoritmer för centrala beräkningsproblem
för att eleverna ska
  • kunna konstruera datorprogram som effektivt utnyttjar datorresurser samt
  • utvärdera huruvida givna datorprogram är effektiva.

Förändringar inför denna kursomgång

Examinationen var oförändrad och bestod av fyra hemuppgifter utöver de två projekten. Projekten lämnades in med hjälp av Kattis. Projekten innehöll huvudsakligen implementations- och experimentuppgifter. Teoriuppgifterna finns huvudsakligen på de fyra hemuppgifterna.

Kursinnehållet var i stort sett det samma som förra året och vi använde Kattis för projektinlämningarna.

Sammanfattning

Antalet elever som påbörjade kursen (92) var större än förra året (79). Examinationsgraden (79%) var något lägre än förra året (85%).

Kursinnehåll

Aritmetik med stora heltal, kodoptimering, primtalstestning och faktorisering, aritmetik med stora heltal, snabba fouriertransformen, RSA, radixsortering på nloglogn tid, Alan Turings liv och vetenskapliga insatser, kvantberäkningar, TSP, amorterad analys med tillämpning på splayträd och union-find. Torbjörn Granlund höll en föreläsning om GMP.

Hemtalen

Hemtalen lämnades in individuellt och rättades skriftligt. Projekten gjordes i grupp och redovisades både skriftligt och muntligt.

Kursens nivå

Resultatet var aningen sämre än förra året trots att kurseninnehållet var likartat. Detta kan möjligen förklaras av att kursen nu är obligatorisk på masterprogrammet i datalogi. Kraven för godkänt är ganska låga men kräver att man har goda kunskaper från ADK. Nivån för högsta betyg ligger fortfarande betydligt högre.

Anpassning till andra kurser

Anpassningen till andra kurser fungerade tämligen väl. Detta beror delvis på att det är möjligt att vara flexibel med datum för inlämningsuppgifter eftersom kursen går över en och en halv läsperiod.

Planerade förändringar

Kursen är nu obligatorisk på masterprogrammet i datalogi och kursinnehållet kan komma att behöva anpassas för detta. Kursen kommer att byta kursledare till Mikael Goldmann.

Ytterligare kommentarer från kursassisterna

Kursens svårighetsgrad

  • projektrapporternas ingenjörsmässiga standard har varit varierande - många studenter har inte funderat på vad som är intressant och relevant att ta med i rapporterna, eller hur materialet kan presenteras på ett strukturerat sätt. Speciellt har det ofta saknats data från prestandatester för olika algoritmer (med och utan optimeringar) som faktiskt utförts; hade detta gjorts på ett systematiskt sätt hade rimligen både implementationen och rapportläsandet förenklats.
  • när explicita krav inte ges tar många studenter den "enkla" vägen på hemuppgifter, t ex när beräkning av FFT görs endast med symbolisk expansion; i allmänhet kan detta kanske undvikas om kraven på uppgiftsvar formaliseras. Vidare efterfrågas detta av minst en student och skulle förenkla och effektivisera rättningen. En potentiell nackdel är att övandet av problem/kravanalys blir mindre.
  • studenterna upplevde att svårighet, förväntningar, och utförlighet skilde sig åt mellan de olika hemuppgifterna och mellan de två projekten. Måhända vill man förtydliga vad som förväntas/bör fokuseras på och kanske till och med ge en exempelhemuppgift med exempel på medel respektive bra lösningar.

Kurslitteratur

  • bokutdragen om DFT/FFT och amorterad analys är mycket bra.
  • studenterna bör varnas för att inte lägga för mycket tid på det ganska avancerade och kompakta kompendiet av Johan Håstad.

Projekt

  • att administrera redovisningsbokning elektroniskt är att rekommendera eftersom det lätt blir problem när studenterna byter tider/assistent i sista stund och den analoga bokningslistan måste konsulteras.
  • i projektrapporterna har det varit möjoligt att få poäng för algoritmer som beskrivs men inte implementeras. En konsekvens är att en del studenter gör ytliga omarbetningar av algoritmbeskrivningar från Wikipedia och liknande. För att undvika tidskrävande bedömningar om studenterna verkligen förstått de beskrivna algoritmerna vore det rimligt att antingen inte ge några poäng alls, eller endast delpoäng, för ej implementerade algoritmer.
  • om studenter arbetar i grupp om tre borde det rimligen framgå att de måste presentera mer än tvåmannagrupper.
  • måhända bör man länka till en simpel beskrivning av vad som förväntas av projektrapporten för att förtydliga vad förväntningarna är, i stil med, men inte exakt, http://www.math.kth.se/math/GRU/2007.2008/SF2708/assignment eller www2.informatik.hu-berlin.de/~antoniad/files/guidelines.pdf. Man kan även visa upp en eller ett par rapporter från tidigare år på andra uppgifter. Vidare vill man knakse vara tydlig med vad som förväntas för olika poäng/betyg på rapporten då vissa studenter inte verkar särskilt nöjda.
  • många studenter förfular sina implementationer genom att specialanpassa dem för Kattis indata (t.ex. skippa instanser som är svåra), detta orsakar förseningar i Kattis när många grupper gör inskickningar för att analysera specialla instanser; flera olika möjliga lösningar finns:
    • förbjuda optimeringar som tar hänsyn till specifika testfall
    • slutgiltig poängsättning görs på en indatamängd som inte är tillgänglig för studenterna
    • instansordningen slumpas för varje inskickning
    • tiden begränsas per instans och inte för hela mängden instanser
    • inskickningar från en person som redan har många inskickningar i Kattis kö får låg prioritet
  • studenterna borde avrådas för att överhuvudtaget implementera det kvadratiska sållet av annat än intresse, eftersom det kräver mycket tid och kunskap om en implementation ska få höga poäng i Kattis.
  • genom att använda Pollards rho-algoritm och trial division kan studenterna ganska lätt komma upp i 40+ poäng på faktoriseringsprojektet, kanske kan detta åtgärdas genom en översyn av testfallen.

Hemuppgifter

  • det är oklart hur mycket studenterna hjälper varandra med hemuppgifter, många lösningar är ganska lika vilket tyder på informella diskussioner mellan studenterna. Kraven på individuella lösningar bör måhända förtydligas muntligt.
  • ett sätt att addressera klagomål på inkonsekvent rättning mellan studenter på en uppgift är att låta en ensam assistent rätta en hel omgång hemuppgifter.
  • vissa studenter klagar på att det är svårt att veta på förhand hur utförligt de ska skriva sina svar på uppgifterna, en del utelämnar vad de uppfattar som triviala steg, men det gör det svårt för rättaren att bedöma om de verkligen förstått.
Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2011-06-21