Kurs-PM för DD1352 Algoritmer, datastrukturer och komplexitet, adk13

Kursen ges i period 1-2 hösten 2013.
På kurswebben på https://www.kth.se/social/course/DD1352 finns all information om kursen.

Lärare

Kursledare och föreläsare är Viggo Kann.

Det står var och en fritt att välja övningsgrupp eller byta grupp under kursens gång. Övningsassistenter är:

1. Anders Ye, normalsvår grupp
2. Marcus Dicander, lite svårare grupp
3. Emma Enström, lite enklare grupp

Det finns också ett antal assistenter som är labbhandledare och tar emot mästarprovsredovisningar.

Lärandemål för kursen

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.

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet.

Kursböcker

• Algorithm Design av Kleinberg-Tardos, 2005, Pearson, ISBN 978-0321372918. Nytrycket från 2013 med ISBN 978-1292023946 går också bra.
• Det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126.

Dessa kan köpas i ett inplastat bokpaket på kårbokhandeln för 670 kr. Supplementet kan köpas löst för 100 kr.

Övrig litteratur

• Laborationer: labbkvitto och labblydelser för dom fyra labbarna finns på kurswebben under Kursinnehåll.
• Två mästarprov (individuella uppgifter) som läggs upp på kurswebben minst två veckor före mästarprovsinlämningsdagen.
• Föreläsningsanteckningar och övningsanteckningar som finns tillgängliga via länkar från kurswebbens detaljschema och kan en vecka efter kursstart köpas (med kort) på papper för 60 kronor på studerandeexpeditionen.
• Exempeltentor finns på webbsidan med gamla kursomgångar.

Det finns pekare till mer att läsa och prova på på länksidan.

Detaljschema

Kursen består av 33 föreläsningar och 12 övningar. Alla föreläsningar efter första veckans tre föreläsningar är entimmesföreläsningar (men av schematekniska skäl har två par av entimmesföreläsningar kommit att hamna direkt efter varandra). Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna och övningarna. För varje föreläsning anges vilka sidor i kursböckerna som du bör ha skummat innan du kommer till föreläsningen.
KT=Kleinberg-Tardos, Sup=supplementet Algorithms and Complexity.

Period 1

F1 5 september (2 timmar)

Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)

F2 6 september(2 timmar)

Repetition av sortering. (KT: 209-221)
Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även Diverse länkar i kurswebbens vänstermeny.

F3 6 september (2 timmar)

Datastrukturer: repetition, hashning, praktiska datastrukturer, trie. (KT: 57-65)
Latmanshashning, skipplistor. (Sup: 77-83)

Ö1 9 september

Algoritmanalys.

F4 9 september

Datastrukturer: bloomfilter. Tillämpning: rättstavning.

F5 10 september

Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)

F6 12 september

Korrekthetsbevis. (webbsida att läsa)

Ö2 12 september

Datastrukturer och grafer. Teoriredovisning för labb 1.

F7 16 september

Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KT: 115-136, 183-188)

F8 17 september

Algoritmkonstruktion: dekomposition. (KT: 221-234, 242-246)

F9 19 september

Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-290)

Ö3 19 september

Dekomposition och dynamisk programmering.

Labb 1 20 september

Konkordans, redovisning.

F10 23 september

Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-301)

F11 24 september

Exempel på motivering av korrekthet: dynamisk programmering. (KT: 307-311)

F12 25 september

Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KT: 137-157)

Ö4 26 september

Dynamisk programmering. Teoriredovisning för labb 2.

F13 30 september

Grafer: maximala flöden. (KT: 337-357, 367-373)

F14 1 oktober

Undre gränser. (Sup: 17-29)

F15 1 oktober

Algoritmkonstruktion: geometriska algoritmer. (webbsida om Grahamscan)

Ö5 3 oktober

Grafalgoritmer och undre gränser.

Labb 2 4 oktober

Rättstavning, redovisning.

F16 7 oktober

Algoritmkonstruktion: sortering i linjär tid. Räknesortering. (Sup: 1-6)

F17 8 oktober

Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)

F18 9 oktober

Algoritmkonstruktion: polynomberäkningar och FFT. (KT: 234-242)

Ö6 10 oktober

Algoritmkonstruktion. Teoriredovisning för labb 3.

Mästarprov 1, senast måndag 14 oktober klockan 11.15!

Algoritmer. Muntliga redovisningar sker 18-23 oktober.

F19 14 oktober

Probabilistiska algoritmer. (KT: 707-724 <avsnitt 12.1-12.3 i nytrycket>)

F20 15 oktober

Reduktioner. (KT: 451-459)

Ö7 17 oktober

Probabilistiska algoritmer. Reduktioner.

F21 17 oktober

Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)

Period 2

F22 4 november

Formella definitioner, turingmaskiner. (PDF att läsa)

F23 4 november

Oavgörbarhet. (Sup: 49-73)

F24 6 november

Cooks sats. (PDF att läsa)

Ö8 8 november

Genomgång av lösning till mästarprov 1. Oavgörbarhet.

Labb 3 8 november

Flöden och matchningar, sista redovisningstillfälle.

F25 11 november kl 13-14

NP-fullständighetsbevis. (KT: 466-495)

F26 11 november kl 14-15

NP-reduktionsvisualisering med Alvie.

F27 12 november

NP-fullständighetsreduktioner. (KT: 459-463)

Ö9 13 november

NP-fullständighetsbevis. Teoriredovisning för labb 4.

F28 18 november

Mer NP-fullständighetsreduktioner. (KT: 497-505)

F29 20 november

Approximationsalgoritmer. (KT: 599-630)

Ö10 20 november

NP-fullständiga problem.

Labb 4 22 november

NP-fullständighetsreduktioner, redovisning.

F30 25 november

Mer approximationsalgoritmer. (webbsida om Christofides algoritm)

Mästarprov 2, senast 27 november klockan 10.15!

Komplexitet. Muntliga redovisningar sker 3-6 december.

F31 27 november

Heuristiska algoritmer. Simulated annealing. (KT: 661-670 <avsnitt 13.1-13.2 i nytrycket>)

Ö11 29 november

Approximationsalgoritmer. (KT: 724-727 <avsnitt 12.4 i nytrycket>)

F32 2 december

Komplexitetsklasser. (KT: 495-497, 531-547)

F33 9 december

Repetition. Kursens betygssystem.

Ö12 9 december

Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.

Teoritenta 20 december klockan 9-12 i sal F1

Extralabb

Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, preliminärt 10 januari 2014.

Frivillig munta för högre betyg, 15-17 januari 2014

Kursregistrering och kursresultat

Alla som vill gå kursen för första gången måste registrera sig på den. Detta gör du i den personliga menyn på KTH-webben. Registrera dig så snart som möjligt efter att kursen börjat!

I Rappsystemet kommer dina resultat på redovisade uppgifter i kursen att matas in och bli synliga för dig. Om du är anmäld och registrerad ska adk13 finnas med bland dina kurser i Rapp.

Om adk13 inte finns med bland dina kurser i Rapp kan det bero på två saker:

1. Du har påbörjat kursen ett tidigare år och är registrerad på en tidigare kursomgång. Då finns dina gamla resultat antingen i adk11 eller adk12 i Rapp eller i kvar i res-systemet. Kontakta Viggo så kan han flytta dina resultat till adk13. Om du av CSN-skäl vill bli omregistrerad på den nya kursomgången i Ladok kontaktar du studerandeexpeditionen på Osquars backe 2, plan 4.
2. Du är inte antagen på kursen av din studievägledning. Gå till din studievägledning och be att få gå DD1352. Dagen efter att studievägledningen lagt in din kursanmälan i Ladok kommer kursen att komma upp i din lista i Rapp, så att du kan registrera dig.

Examination

Följande betygskriterier tillämpas i kursens examination. Du måste uppfylla alla kriterier på det betyg du ska få.

mål	E	D	C	B	A
utveckla algoritmer med datastrukturer	för enkla problem givet en konstruktionsmetod	för icketriviala problem givet ledtråd	för icketriviala problem	för svårare problem	för svårare problem med den metod som passar bäst
	examineras med labbar (för nivå E), mästarprov 1 och muntlig tenta
implementera algoritmer med datastrukturer	efter funktionsspecifikation och efter detaljerad algoritmisk specifikation, med hänsyn taget till effektivitet
	examineras med labbar
analysera algoritmer med avseende på effektivitet	förklara principerna, analysera enklare algoritmer	analysera rekursiva algoritmer med mästarsatsen	analysera svårare algoritmer
	examineras med labbar och teoritenta (för nivå E), mästarprov 1, teoritenta och muntlig tenta
analysera algoritmer med avseende på korrekthet	förklara principerna, förstå ett givet korrekthetsbevis	genomföra enklare korrekthetsbevis	resonera med invarianter och induktion
	examineras med mästarprov och muntlig tenta
jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet examineras med labbar och mästarprov 1
definiera begreppen P, NP, NP-fullständighet och oavgörbarhet examineras med teoritenta och mästarprov 2
jämföra problem med hänsyn till komplexitet med hjälp av reduktioner	förklara principerna, utföra enklare reduktioner mellan givna problem	visa NP-fullständighet givet ledtråd	visa NP-fullständighet och oavgörbarhet	göra konstruktionsreduktioner givet ledtråd	göra konstruktionsreduktioner
	examineras med labb 4 (för nivå E), mästarprov 2 och muntlig tenta
förklara hur man kan hantera problem med hög komplexitet	förklara behovet	förklara principerna	konstruera enkla heuristiker och totalsökningsalgoritmer	konstruera och analysera enklare approximationsalgoritmer eller heuristiker	konstruera och analysera approximationsalgoritmer eller heuristiker, eller visa undre gränser för approximation
	examineras med teoritenta (upp till betyg C) och muntlig tenta eller labb 4-extrauppgift (för betyg A+B)

Kursen har fyra obligatoriska moment i Ladok:

• LAB1, datorlaborationer, 3 hp
• MAS1, mästarprov 1, 1,5 hp
• MAS2, mästarprov 2, 1,5 hp
• TEN2, tenta, 3 hp

Labbar

Fyra obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. Labbarna ska göras i tvåpersonsgrupper, men enpersonsgrupper kan godkännas i undantagsfall. Varje labb som redovisas senast det labbtillfälle som finns angivet på labben ger en bonuspoäng på tentan. På varje labb finns dessutom ett antal frivilliga teoriuppgifter. Teoriuppgifterna redovisas på övningstillfällen och ger en bonuspoäng var.

Sammanlagt kan alltså labbarna och teoriuppgifterna ge åtta bonuspoäng på tentan. Bonuspoängen gäller på alla tentor på kursen som går inom ett kalenderår räknat från kursstart.

Det finns schemalagda labbtillfällen från och med andra veckan av kursen och till och med den vecka då labb 4 ska redovisas. Det kommer att finnas handledare tillgängliga på dessa labbpass. Börja att göra labbarna i god tid och fråga handledarna om du får problem. Du kan i princip redovisa alla labbarna vid alla labbtillfällen, men under det sista labbtillfället för varje labb prioriteras redovisningar av den labben.

Individuella uppgifter: mästarprov

Två obligatoriska individuella uppgifter, mästarprov, kommer att delas ut. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas till kursledaren eller lämnas in på studerandeexpeditionen senast den tid som anges på uppgiftslydelsen. Den muntliga redovisningen kommer att ske några dagar senare för någon av assistenterna på en tid som ska bokas i förväg på kurswebben.

Varje mästarprov består av tre uppgifter av olika svårighetsgrad. En rätt löst uppgift ger betyg E på momentet, två rätt lösta uppgifter ger betyg C och alla rätt ger betyg A.

Den som inte godkänts på ett mästarprov får möjlighet att göra ett nytt i slutet av kursen, men kan då bara få betyg E på mästarprovet.

Tenta

Ordinarietentan går den 20 december 2012 klockan 9.00 i sal F1. Nästa tillfälle är i vår vid ordinarietentan för kursen DD2352 Algoritmer och komplexitet för F. Därefter blir det en omtenta i augustiperioden.

Tentan är en teoritenta (om 20 poäng) utan hjälpmedel. För godkänt krävs minst 14 poäng. 17 poäng ger betyg D och 20 poäng ger betyg C. Betyg B och A delas inte ut på teoritentan. Den som redovisat datorlabbarna i tid och har svarat rätt på teoriuppgifterna på labbarna får 8 poängs bonus på tentan.

Skrivtiden är två timmar. Direkt efter tentan vidtar obligatorisk genomgång av lösningarna till tentan och kamraträttning. Rättningen kontrolleras sedan av lärarna och resultatet kungörs samma vecka. Klagomål på rättning av tentan görs till kursledaren. Den som hamnar under men tillräckligt nära gränsen för godkänt på tentan ges möjlighet att komplettera. Kursledaren avgör gränsen för komplettering liksom hur och när kompletteringsuppgifter ska redovisas.

Tentaanmälan ska göras.

Muntlig tenta och slutbetyg

Den som fått godkänt på labbarna, båda mästarproven och teoritentan får godkänt på kursen. Slutbetyget bestäms av betygen på samtliga tre betygsatta moment (mästarproven och teoritentan) eventuellt kompletterat med en muntlig tenta och/eller en extralabb (se tabellen med betygskriterier). Den som har fått minst betyg x på alla tre betygsatta moment är värd (minst) betyg x i slutbetyg. Betyget på teoritentan kan höjas till A eller B om man gör extralabben till labb 4 och redovisar på det särskilda redovisningstillfället som är omkring 10 januari 2014.

Den som fått minst betyg C på minst två av momenten och minst betyg E på det tredje har möjlighet att gå upp på en muntlig tenta för att få högre betyg. Den muntliga tentan kan bokas in (på kurswebben) på tider 15-17 januari 2014. Vid den muntliga tentan kommer läraren att kontrollera att du uppfyller alla betygskriterier för det betyg du aspirerar på. Kursböckerna (men inga kompendier eller anteckningar) är tillåtna hjälpmedel.

För att förtydliga slutbetygsberäkningen ges här några exempel på olika sätt att få betyg:

elev	mästarprov 1	mästarprov 2	teoritenta	extralabb	munta	slutbetyg	kommentar
Filemon	E	F	D	-	-	-	inte godkänd på mästarprov 2
Ebon	E	D	E	-	-	E	kan inte gå upp på muntan
Durian	D	C	D	-	-	D	kan inte gå upp på muntan
Cecil	B	D	C	-	C	C	muntade upp mästarprov 2
Beda	B	A	D	B	-	B	valde att inte munta till A
Asta	C	A	C	A	A	A	muntade upp mästarprov 1

Här är en beskrivning av examinationen som flödesschema (tack till Erik Fahlén).

Arbetssituationer

Det är meningen att arbetet med momenten i kursen ska motsvara olika arbetssituationer i arbetslivet.

Labbarna tränar olika typer av programutvecklingsarbete:

• Labb 1 är programmering efter en funktionsspecifikation.
• Labb 2 är omprogrammering av ett existerande program så att det ska fungera likadant fast effektivare.
• Labb 3 är programmering efter en detaljerad algoritmisk specifikation.

I alla labbar finns noggranna beskrivningar av format för indata och utdata. Alla labbar har givna effektivitetskrav och utförs som lagarbete (labbgrupper), precis som i arbetslivets parprogrammeringsprojekt.

Mästarproven tränar expertsituationen, alltså situationen som den som vet mest om något på en arbetsplats ställs inför när han får ett problem: det finns ingen att fråga, så han måste komma fram till svaret med egen tankekraft och genom att läsa litteratur. När problemet är löst ska experten förklara lösningen för chefen, både skriftligt och muntligt.

Tentan liknar tyvärr ingen verklig arbetssituation, men den följs av en kamraträttningssession som är mycket värdefull ur ett pedagogiskt perspektiv.

Kurskatalog

Kursen har en katalog på skolans Unixdatorer: /info/adk13. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Kursutveckling och synpunkter på kursen

Eftersom denna kurs kommer att ges för många elever under flera års tid är vi tacksamma för synpunkter på kursen. En datorstödd kursutvärdering kommer att göras. Synpunkter kan alltid lämnas direkt till lärarna.

I förra kursomgångens kursanalys kan man se hur kursen fungerade då och vilka ändringar som planerades att göras. Här är en kort sammanfattning:

Resultat efter ordinarietentan 2012

Antalet registrerade kursdeltagare var 165. Prestationsgraden var 85%.

Den målrelaterade examinationen i betygskalan A-F har fungerat väl. Eftersom alla lärandemål måste vara uppfyllda för slutbetygsnivån så blir betygsfördelningen förskjuten mot betygen E och A. Medelbetyget låg mellan D och C, något lägre än föregående år.

Elevsynpunkter 2012

Kursen ansågs vara ganska svår (51%) eller mycket svår (25%) av tre fjärdedelar, medan 4% tyckte den var lätt och resten medelsvår.

Föreläsningsanteckningarna på webben, med alla stordiabilder som visades samt alla övningsuppgifter med lösningar, ansågs vara mycket bra eller bra av två tredjedelar.

79% föredrog entimmesföreläsningar i kursen (infördes 2010) och 11% föredrog traditionella tvåtimmarsföreläsningar. Pedagogiskt sett ansågs föreläsningarna mycket bra eller bra av 94%.

Examinationsformen med en tredjedel av vardera labbar, mästarprov och tenta ansågs mycket bra eller bra av nästan alla (92%).

Det automatiska programtestningssystemet Kattis fick helhetsbetyget mycket bra eller bra av 80%.

Förändringar till 2013

Dynamisk programmering anses vara en svår del av kursen. Därför la Viggo i ett forskningsprojekt om avsnittet enligt den pedagogiska modellen mönsterorienterad undervisning. Detta genomfördes första gången 2012 och kommer att ytterligare förbättras och utvärderas i denna kursomgång.

Undervisningen av och träningen på pseudokod och korrekthetsmotivering kommer att utvecklas. Detta görs också i ett forskningsprojekt.

Tips om att man ska börja tidigt med mästarproven, avsätta en hel del tid till dom och studera gamla mästarprov kommer att ges på föreläsningarna.

Uppmaningar vad som ska läsas i kursboken kommer att lämnas vid föreläsningarna, så att föreläsningarna mer kan ägnas åt det som är känns oklart och svårt.

Hederskodex

Skolans hederskodex (se kurswebben) tillämpas i kursen. Varje student förutsätts känna till och tillämpa hederskodexen.








 .