Avancerade algoritmer

Kursanalys för avalg09

Kursdata

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

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 delvis annorlunda mot förra året men projektuppgifterna var de samma: den första uppgiften handlade om faktorisering och den andra om TSP i planet. Som vanligt använde vi Kattis för projektinlämningarna. Nya moment för i år var: amorterad analys, splayträd och union-find. För att ge plats till detta så tog jag inte bort några moment men gick igenom vissa delar mera översiktligt, särskilt då den grundläggande talteorin.

Sammanfattning

Antalet elever som påbörjade kursen (79) var betydligt större än förra året (59). Examinationsgraden var oförändrad men andelen höga betyg var lägre.

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.

Undervisningen

Deltagandet på föreläsningarna varierade kraftigt.

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 i stort sett detsamma som förra året vilket är väntat eftersom kurseninnehållet var likartat. 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 någorlunda väl och experimentet med att låta kursen gå över en och en halv läsperiod var lyckat.

Planerade förändringar

Kursen kommer att bli obligatorisk på masterprogrammet i datalogi och kursinnehållet kan komma att behöva anpassas för detta. Förändringarna i kursinnehåll i år var ett steg i denna riktning.