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

Kursanalys: Avancerade algoritmer, avalg12

Kursdata

Tid: period 1-2 läsåret 2012-2013

Poängantal: 6hp

Examination: inlämningsuppgifter

Föreläsningar: 30 timmar

Kursledare och föreläsare: Stefan Nilsson

Övningsassistenter: Björn Terelius, Musard Balliu, Sangxia Huang.

Gästföreläsning: Torbjörn Grandlund.

Antal registrerade på kursen: 139

Antal som gjort något synligt på kursen: 126

Godkända: 121 (2013-05-30)

Prestations- och examinationsgrad: 87%

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 bestod av tre 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.

En av fyra planerade hemuppgifter fick ställas in under kursens gång eftersom studenterna plötsligt inte kunde komma in på plan 4 och därmed inte kunde lämna in sina uppgifter.

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

Sammanfattning

Kursen är nu obligatorisk på masterprogrammet i datalogi och kursinnehållet är tänkt att komplettera ADK. Antalet elever på kursen fortsätter att öka medan examinationsgraden ligger kvar på 80-90%.

Kursenkät

  • Upplever du kursen som lätt eller svår?

    1. 0% (0 st) Mycket lätt.
    2. 3% (1 st) Lätt.
    3. 34% (10 st) Medel.
    4. 59% (17 st) Ganska svår.
    5. 3% (1 st) Mycket svår.


  • Fick du i början av kursen tillräckligt klart för dig vad kursens mål är?

    1. 83% (24 st) Ja.
    2. 17% (5 st) Tveksam.
    3. 0% (0 st) Nej.


  • Tycker du att kursen är intressant?

    1. 66% (19 st) Ja, mycket.
    2. 34% (10 st) Ja.
    3. 0% (0 st) Neutral.
    4. 0% (0 st) Inte särskilt.
    5. 0% (0 st) Nej.


  • Förkunskapskraven för kursen är 5B1204/SF1631 Diskret matematik samt en av kurserna 2D1352/DD1352 Algoritmer, datastrukturer och komplexitet och 2D1354/DD2354 Algoritmer och komplexitet eller motsvarande kunskaper. Tycker du att dina förkunskaper var tillräckliga när kursen startade?

    1. 93% (27 st) Ja.
    2. 7% (2 st) Tveksam.
    3. 0% (0 st) Nej.


  • Ägnade vi lagom mycket tid åt repetion av stoff från andra kurser?

    1. 10% (3 st) För mycket.
    2. 79% (23 st) Lagom.
    3. 7% (2 st) För litet.


  • Vad tycker du om kompendiet (Håstad)?

    1. 10% (3 st) Mycket bra.
    2. 31% (9 st) Bra.
    3. 34% (10 st) Hyfsat.
    4. 3% (1 st) Mindre bra.
    5. 7% (2 st) Dåligt.
    6. 14% (4 st) Har inte använt det.

    Ev. kommentar om kompendiet:

    Tyckte inte det tillförde speciellt mycket. Den information jag använda kom från annan litteratur eller länkar på kurshemsidan eller på nätet.
    ---
    Bra del om TSP och faktorisering.
    ---
    Det var lättare att googla, och det gav också bättre info
    ---
    Inte särskilt djupgående i vissa fall men en bra början för att lära sig terminologin och så vidare.
    ---
    Alldeles för teoretiskt och matematiskt, för min del mer eller mindre oläsligt. Kompletteras dock bra av snilssons föreläsningar som är mer "praktiska".
    ---
    Mycket text som tar upp väldigt lite om väldigt mycket.
    ---
    Läste bara delarna om TSP och faktorisering
    ---
    Lite långt. Jag använda bara en bråkdel av det, det mesta var inte alls relevant.
    ---
    Det var som en typisk "svensk" lärobok, lite för kortfattat innan man kan ämnet, mycket bra som referenslitteratur eftersom inte har allt fluff runt omkring.
    ---
    Lite torftig information.
    ---
    Bra med mycket samlat på samma ställe.

    Vilka informationskällor har du använt förutom kompendiet?

    Använde mycket två böcker för projekten: Prime numbers: a computational perspective för kvadratiska sållet; och Traveling salesman problem: A computational study för Chained Lin-Kernighan. Samt kompendiet på hemsidan angående TSP. Sedan lite länkar och pdfer på nätet.
    ---
    Algorithm design av kleinberg (?) och Tardos (?) samt internet
    ---
    Kursboken och internet
    ---
    Vetenskapliga artiklar funna genom googling.
    ---
    Daz Internet
    ---
    Den rekommenderade kursboken samt papers och dyl. som hittats online
    ---
    Wikipedia, MathWorld/WolframAlpha
    ---
    Wikipedia och liknande sidor.
    ---
    Internet.
    ---
    Diverse Wikipedia-artiklar och en del annat material från nätet.
    ---
    Internet
    ---
    De dokument som fanns på webbsidan samt Wikipedia.
    ---
    Inget slår Wikipedia för beskrivning av algoritmer.
    ---
    Wikipedia Länkar på kurshemsidan.
    ---
    Länkarna från hemsidan, Google, Wikipedia.
    ---
    Hela internet samt flertalet böcker. Att finna nya böcker samt information för att hantera kursmaterialet var aldrig något problem.
    ---
    Kursboken från krypto12-kursen, papers jag hittade på internet.
    ---
    Introduction to Algorithms (Cormen)
    Internet

    ---
    Internet, PDF-filer från forskning och andra universitet


  • Hur stor del av de ordinarie föreläsningarna har du varit på?

    1. 7% (2 st) Mindre än 20%.
    2. 0% (0 st) 20-40%.
    3. 14% (4 st) 40-60%.
    4. 24% (7 st) 60-80%.
    5. 55% (16 st) Mer än 80%.


  • Vad tycker du om de ordinarie föreläsningarna pedagogiskt sett?

    1. 41% (12 st) Mycket bra.
    2. 28% (8 st) Bra.
    3. 21% (6 st) Acceptabelt.
    4. 3% (1 st) Mindre bra.
    5. 0% (0 st) Dåligt.
    6. 7% (2 st) Har inte deltagit.

    Ev. kommentar (gärna konstruktiv):

    Jag gillar att läsa och plugga själv, och därför går jag normalt sett inte på föreläsningar.
    ---
    Jag gillar anekdoter och kuriosa så om om det är någon som sagt någonting negativt angående är detta en röst emot den kommentaren. Detsamma gäller flexibla föreläsningslängder.
    ---
    Snilssons föreläsningar är alltid värda att gå på :)
    ---
    Stefan säger väldigt mycket, men väldigt lite som har någon betydelse för när man försöker lära sig.
    ---
    Även om föreläsaren befinner sig i undervisningstvång med ett flertal kurser samtidigt tycker jag ändå att han skött det utmärkt. Han har bra pedagogisk förmåga samt en djup kunskap om ämnet.
    ---
    Snilsson är en mycket bra och underhållande föreläsare. Vissa föreläsningar kändes dock mindre planerade, och ofta gicks algoritmer bara igenom på ytan, vilket inte gjorde dem så hjälpsamma till när man faktiskt skulle imlpementera dem. Det märktes speciellt runt den senare delen av kursen, t. ex. angående hemtal C och projekt 2. De första föreläsningarna hjälpte mycket mer!
    ---
    Would often stop the lectures very early, why not go deeper or talk about other stuff. Also felt that sometimes alot of time dissapeared (e.g., assignment hand in, or lecturer just talking about random stuff). So sometimes felt like I traveled an hour to school for 30 mins of relevant lecturing. Too bad, because the main lecturer is very good when he finally gets going.
    ---
    Intressant att lyssna på, men det känns som om det saknas lite substans och mer genomarbetade förklaringar och exempel. Lite mycket handviftande på ytan och skrapa på den övergripande idéen när det faktiskt är detaljer som känns som det svåra.
    ---
    Stefan har hållt väldigt hög klass på föreläsningarna. Bra förklaringar, bryter ned svåra problem på ett enkelt sätt.
    ---
    Kändes ofta oförberedda, lite tråkigt att snilsson inte använde all tid han hade när folk har tagit sig dit för att lyssna. Jag kan inte tänka mig att han sagt allt han kan om avancerade algoritmer.
    ---
    Stefan Nilsson är jättebra vet jag, men jag har för lång pendlingstid för att motivera att närvara på föreläsningar.


  • Förbereder du dig till föreläsningarna (läser igenom relevanta avsnitt i boken/kompendiet etc)?

    1. 0% (0 st) Ja, alltid.
    2. 7% (2 st) Ofta.
    3. 28% (8 st) Ibland.
    4. 34% (10 st) Sällan.
    5. 31% (9 st) Aldrig.


  • Vad tycker du om hemuppgifterna?

    1. 28% (8 st) Mycket bra.
    2. 48% (14 st) Bra.
    3. 17% (5 st) Acceptabelt.
    4. 3% (1 st) Mindre bra.
    5. 3% (1 st) Dåligt.
    6. 0% (0 st) Har inte deltagit.

    Ev. kommentar (gärna konstruktiv):

    Många av uppgifterna uppfattar jag som relevanta som amorterad analys och algoritmkonstruktion av vissa problem. En del problem kan dock vara lite sega att ta sig igenom, , det är väl inte lätt som lärare att bara ge intressanta uppgifter...
    ---
    Det var några som tyckte att det var inkonsekvent fördelning av poängen beroende på vilken asse som rättade, detta verkade stämma. Kanske kunde frågorna ha ställts på ett annat sätt som inte lämnade lika mkt rum för olika poängtolkning.
    ---
    Bra uppgifter, fast jag tyckte det var det svåraste på kursen.
    ---
    Rättningen var ibland lite överdrivet sträng (som t.ex. att hwb fråga 1 gav 0p med svar taget nästan rakt av ur det utdelade häftet om amorterad analys)
    ---
    Mer tidskrävande än de verkade vid första genomläsningen, men vi borde ha lärt oss det vid det här laget, kan man tycka.
    ---
    Vore bra om man lärde sig vad uppgifterna gick ut på, på föreläsningarna, innan man ska lämna in dom. Allt jag gjorde bara gissade jag på.
    ---
    Jag tyckte det räckte gott och väl med uppgifterna -- även fast det var en mindre än vanligt. Kanske något att fortsätta med?
    ---
    Generellt bra. Ett problem med dem var att vissa deluppgifter behövde man ha lite tur och bara komma på rätt idé för att lösa.
    ---
    Möjligen kan uppgift 1 på Homework C omformuleras till att man blott skall förklara snarare än att hjärndött räkna.

    Uppgift 3 på Homework 3 var fenomenal. Man satte sig verkligen in i hur Miller-Rabin fungerade. Uppgift 4 var också briljant, men då p.g.a. att man var tvungen att vara lite fyndig och kreativ (såvida man inte googlade på ämnet).

    ---
    Lite hårda rättningar ibland, åt det binära hållet 5 eller 0 poäng.
    ---
    Ofantligt svåra uppgifter i hemuppgifterna, vilket är passande för en kurs som är avancerad. Riktigt roliga var hemuppgifterna.
    ---
    Roligt att jobba mot kattis och tävla lite med kompisarna. Samtidigt bra och intressanta uppgifter, speciellt TSP-heuristikerna.


  • Vad tycker du om faktoriserings-projektet?

    1. 48% (14 st) Mycket bra.
    2. 45% (13 st) Bra.
    3. 7% (2 st) Acceptabelt.
    4. 0% (0 st) Mindre bra.
    5. 0% (0 st) Dåligt.
    6. 0% (0 st) Har inte deltagit.

    Ev. kommentar (gärna konstruktiv):

    Väldigt roligt och givande. Första gången jag implementerar och får lära mig en väldigt avancerad algorithm. Kul att få leta information själv och sedan programmera.
    ---
    Relevant och lagom utmanande.
    ---
    Mestadels bra. Lite tråkigt att det inte var lika fritt som TSP i vad man kunde göra. Det fanns inte så många olika saker att implementera.
    ---
    Riktigt kul projekt, förväntade mig inte att tycka det, men lyckades bra med den del jag kodade och vår rapport blev riktigt bra.
    ---
    Ingenting som man själv testade gav några resultat. Det hela verkade handla om att implementera andras idéer. Vore bra om man visste det.
    ---
    Det var intressant eftersom det finns många olika sätt att lösa det på. Som vanligt mycket bra med rättning via kattis eftersom man kan styra sitt eget betyg bra.
    ---
    Det kanske vore schysst att göra framtida studenter uppmärksamma på vissa Java-specifika problem som kan uppstå vid implementation av QS, men för min del får de gärna försöka klura ut det själva... ;)
    ---
    Det var väldigt bra då man själv kan lägga "ribban" för sina problemlösningar i projektet då detta inte är för mycket förbestämt.
    ---
    Kunde gått igenom den underliggande matematiken för exempelvis pollard-rho noggrannare.


  • Vad tycker du om TSP-projektet?

    1. 48% (14 st) Mycket bra.
    2. 38% (11 st) Bra.
    3. 14% (4 st) Acceptabelt.
    4. 0% (0 st) Mindre bra.
    5. 0% (0 st) Dåligt.
    6. 0% (0 st) Har inte deltagit.

    Ev. kommentar (gärna konstruktiv):

    Väldigt roliga och givande. Första gången jag får sätta mig in i och implementera en avancerad datastruktur (som visserligen inte blev klar...). Tycker även här att det är kul att få leta information och jobba självständigt med en kompanjon och "lösa" ett intressant problem.
    ---
    Det var svårt att begränsa sig av någon anledning. Jag tyckte det fanns så många olika tillvägagångssätt man kunde använda och det gjorde det svårt att avgöra vilket som skulle fungera bäst i Kattis. Men ett bra problem.
    ---
    Skulle vara bättre om man fick något skelett med några vettiga testfall. Nu tjänade Kattis som testmekanism.
    ---
    Mycket bra. Många olika algoritmer man kunde välja bland, alla med för- och nack-delar. Man var tvungen att prioritera vilka man ville använda eftersom det inte fanns tid att testa alla. Rapporten skrev sig själv eftersom man redan varit tvungen att motivera för sig själv vilka val man gjort.
    ---
    Trött på TSP eftersom vi tjatat om det i minst 3-4 kurser... dessutom skrev jag min diskmatteuppsats om TSP. Annars ok.
    ---
    Ingenting som man själv testade gav några resultat. Det hela verkade handla om att implementera andras idéer. Vore bra om man visste det.
    ---
    Utmanande. Kanske gå igenom teorin lite tidigare.
    ---
    Roligare än faktorisering, men lärde mig förmodligen mer på faktorisering.
    ---
    Inte lika kul som faktorisering, då problemet har en mer kontinuerlig natur snarare än diskret, men ändå skoj problem.

    Dock skulle 2-opt och 3-opt kunna gås igenom mer grundligt, då framförallt uppsnabbning av dessa metoder med hjälp av grannlistor. I synnerhet 3-opt, då det knappt finns beskrivet någonstans på internet om detta och den främsta källan (den som länkas via kurshemsidan) vill jag påstå innehåller felaktigheter när det gäller detta (bl.a. är argumentet angående optimering av 2-opt med grannlista felaktigt/bristfälligt).

    ---
    Det var väldigt bra då man själv kan lägga "ribban" för sina problemlösningar i projektet då detta inte är för mycket förbestämt.
    ---
    Roligt, ingenjörsmässigt och "hands on". Jag kan vara färgad av att det gick bättre för oss än i faktoriseringen.
    ---
    Lite svårt att veta om man går i rätt riktning i kodandet då det finns knappt med pseudokod på nätet oftast beskrivningar om hur saker och ting ska fungera men ingen praktiska implementeringar vilket är helt acceptabelt men svårt att debugga.


  • Kursen är på 6 hp. Vad tycker du om det jämfört med andra kursers poängantal?

    1. 52% (15 st) Lagom med 6 hp.
    2. 41% (12 st) Borde vara 7,5 hp.
    3. 3% (1 st) Borde vara 9 hp.
    4. 0% (0 st) 6 hp är för mycket.


  • Förbättringar: Vad borde läggas till i kursen?

    Kanske att man kan skala ned hemuppgifternas omfattning lite och endast ta de fundamentala saker. Därtill skulle man kunna lägga till ett tredje projekt om exempelvis grafalgoritmer, vilket kan vara givande och intressant. Dock borde då kursen kanske utökas lite.

    Ovan klickade jag i 7,5 hp, och det är med avseende på hur mycket tid jag har lagt ned. Jag kan å andra sidan ha lagt ned "för mycket" tid på kursen.

    ---
    Allmänt tycker jag att kursen skulle vara större (7,5-9 poäng) och då också mer omfattande. Kanske ett till projekt och ett till hemtal vore trevligt. En uppsats om ett datalogiskt problem som inte kräver implementation kanske också är en idé.
    ---
    Övningar skulle vara trevligt, men är inget måste.
    ---
    Jag tycker de olika delarna var givande, men FFT:n hade jag svårt att greppa. Kanske något mer om FFT.
    ---
    Kanske lite repetition kring sådant som komplexitetsklasserna osv, som man annars kanske glömt lite av sedan ADK:n.
    ---
    En till föreläsning om QS, det var omöjligt att förstå på den som var nu, p.g.a. alldeles för högt tempo.
    ---
    Det är svårt att föreslå det man inte har lärt sig. ;)

    Dock kan jag känna att mina medstudenter åtminstone borde känna till följande:
    Disjoint Set.
    Strongly Connected Components.
    2-SAT.

    ---
    Något som gör att den känns mer sammanhängande. Nu pratade vi om lite om sortering (vilket kändes som ett specialfall snarare än ett område vi behandlade), en hel del kring faktorisering mm. Men sen kom TSP lite adhoc på slutet, och då har jag glömt någon annan föreläsning som också kändes "fristående".
    ---
    Mer angående FFT då denna är en fantastisk algoritm för hantering av många problem.
    ---
    Algoritmkonstruktionsmetoder. Något om dynamisk programmering, divide & conquer osv.
    ---
    Gärna fler föreläsningar!
    ---
    Ingen åsikt då jag inte har närvarat på föreläsningarna.


  • Förbättringar: Vad borde tas bort ur kursen?

    Kanske minska omfattningen av hemuppgifterna till endast de fundamentala uppgifterna som är nödvändiga att kunna, även om alla säkerligen är väldigt bra att kunna. De som jag uppfattar är bra att kunna är algorithmkonstruktion och begrepp som amorterad analys.
    ---
    Ingenting, allt som är med borde vara kvar.
    ---
    Muntliga redovisningar.
    ---
    Genomgång av RSA kändes onödigt för oss som har gått datalogi, vi har redan fått det i både diskmatte och datorsäkerhetskursen.

    Det kändis väldigt bra med bara tre hemtal. Jag tror att den fjärde kan plockas bort permanent utan att man tappar så mycket, för det kändes verkligen inte som om vi missade något.

    ---
    De två delar man har minst praktisk användning av är helt klart sortering på O(n log log n) tid och faktorisering på kvantdator. Dock har ju båda sina intressanta aspekter.
    ---
    It seems strange to focus on number theoretic subjects when the majority of the students don't have enough math background and everything just turns into hand waving explanations. I think it would be better to foucs on other stuff, e.g., dynamic programming etc.
    ---
    -
    ---
    Inget
    ---
    Jag tycker kursen var bra upplagt.


  • Förbättringar: Vad borde förändras i kursen?

    Projekten var väldigt roliga. Skulle vara roligt med ett tredje projekt om grafalgoritmer, men då blir förmodligen kursen för stor.
    ---
    Jag tyckte att projekten var mycket roligare och mer lärorika än hemtalen. Skulle inte haft något emot att ha ett projekt till i stället för hemtalen kanske.
    ---
    Boken (Cormen et al) kanske borde vara mer obligatorisk och inkorporeras mer i kursen. Vi klarade oss bra med Wikipedia och liknande, men jag hade nog lärt mig mer om jag även köpt och läst boken. Om jag fick gå kursen igen skulle jag nog göra det :) Å andra sidan trevligt med en enda kurs utan bok, för en gångs skull en termin med mindre än 2000 riksdaler spenderade på måste-ha-böcker ;)
    ---
    Föreläsningarna. Vill ha mer genomgångar, förklaringar, definitioner, mm. Alltså, man behöver något att "ta" på, inte en massa muntliga resonemang med handviftningar.
    ---
    Föreläsningarna bör ses över så att de hjälper studenterna att implementera algoritmerna. Det är väldigt många algoritmer som ska gås igenom, så de flesta hann bara knappt introduceras, pseudokod t. ex. var inte vanligt. Pollard Rho och Euclides algoritm var några av de som verkligen förklarades bra. Tvåopt, och speciellt treopt och k-opt var väldigt ytligt. De är som tur ganska lätta att förstå ändå (men svåra att implementera...), så det gjorde inte så mycket.
    ---
    Null.
    ---
    For both projects I did 95% of the work, including all coding (even though I tried getting my partner involved). Had he been asked only a single semi-difficult questing during any of the two presentations he wouldn't have been able to answer properly. His grade is highly undeserved.
    ---
    -
    ---
    Använd hela föreläsningarna.
    ---
    Tycker bara att det var lite kärvt med homework B. Krockade med AI kursens inlämning och tenta veckan om jag inte kommer ihåg fel nu.


  • Ytterligare synpunkter på kursen:

    Givande kurs. Känns väldigt roligt att få läsa på självständigt om avancerade algoritmer och sedan få implementera dem.
    ---
    Bra kurs! Jag är nöjd.
    ---
    Heja Snilsson! Vad mer kan man säga? kKursen känns på något sätt mindre avancerad/skrämmande för att den blir lite som "välkommen tillbaka till inda09 vol. II" :)
    ---
    Dåligt att föreläsningarna inte gavs på engelska.
    ---
    Intressant kurs!
    ---
    Assistenterna rättade hemuppgifterna olika. Likadana lösningar kunde ge tre olika poäng beroende på vem som rättade.
    Berätta mer tydligt vad som gäller för 3-personsgrupper i de olika projekten.

    ---
    Amorterad tidskomplexitet tycker jag var det absolut viktigaste vi lärde oss. Jag är lite förvånad att det inte har dykt upp än, t. ex. i ADK:n. Jag skulle gärna se mer fokus på det, på något sätt! Det kändes betydligt mer användbart än t. ex. FFT eller olika speciella sorteringsalgoritmer för heltal, som båda är begränsade till ganska få användningsområden.
    ---
    Algoritmer är skoj!
    ---
    Antagligen den bästa/intressantaste kursen jag läst av mina 4 år hittils på KTH.
    ---
    Bra kurs! Väldigt värdefull, önska jag kunde ta till mig mer dock. Hade mycket som krockade.
    ---
    3 hemuppgifter fungerade galant. Kör så nästa år också: A, B och D!!!!!!

  • Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
    Uppdaterad 2013-05-30