Kurs-PM för DD1352 Algoritmer, datastrukturer och komplexitet (ADK)
och Algoritmer och komplexitet för SU (SUALKO), våren 2009
På kurswebbsidan http://www.csc.kth.se/DD1352/adk09 finns
aktuell information om kursen.
ADK för datateknikprogrammets årskurs 2 och SUALKO för
matte-datalinjens årskurs 3 samläses. SUALKO har
en mindre labbkurs än ADK (och får 7,5 hp istället för 9).
I övrigt är kurserna identiska.
Lärare
Kursledare och föreläsare är
Viggo Kann,
viggo@nada.kth.se
.
Det står var och en fritt att välja övningsgrupp eller byta grupp under kursens gång.
Övningsassistenter är:
- Torbjörn Granlund, E31, normalsvår grupp
- Marcus Dicander, E35, lite svårare grupp
- Leo Giertz, E36, lite enklare grupp
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
Jag har försökt minimera kostnaden för kursböcker. Därför finns det tre
alternativa uppsättningar kursböcker. Vilken som passar bäst
beror på om du har någon av böckerna sedan tidigare.
-
Algorithm Design av Goodrich-Tamassia, 2001, Wiley, ISBN 978-0471383659 (Indakursboken 07/08), kompletterad
med det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, 2009, Pearson Custom Publishing, ISBN 978-1847764126, som finns att köpa i kårbokhandeln för 120 kronor.
-
Algorithm Design av Kleinberg-Tardos, 2005, Pearson, ISBN 978-0321372918 (Indakursboken 08/09), kompletterad
med det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, 2009, Pearson Custom Publishing, ISBN 978-1847764126. Dessa till i ett inplastat bokpaket på kårbokhandeln.
-
Specialtryckta kursboken för ADK07 och ADK08 Algorithms and Complexity, 2007, Pearson Custom Publication, ISBN 1-84658-626-7.
Läsanvisningar finns till alla tre alternativen. Alla tre fungerar
i stort sett lika bra, men den specialtryckta kursboken från 2007/2008 saknar
tyvärr index.
Kursbunt
- Fyra laborationsuppgifter
- Två mästarprov (individuella uppgifter) som delas ut under kursens gång
- Övningsanteckningar
- Två exempeltentor (2008-05-13 och 2007-05-16)
- Föreläsningsanteckningar
- Utdrag ur Algorithm Design av Kleinberg-Tardos
Kursbunten säljs på första föreläsningen och kan därefter köpas på
studentexpeditionen på Osquars backe 2, plan 2, för 70 kr.
Schema
Schemat i KTHs schemasystem TimeEdit stämmer. En länk till det finns på kurswebbsidan.
SU-studenterna redovisar sista labben 20 mars. Labbtiderna därefter är
enbart för teknologerna.
Detaljschema
Kursen består av 22 föreläsningar och 12 övningar.
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
det behandlas i kursböckena. GT=Goodrich-Tamassia, KT=Kleinberg-Tardos,
Moln=Algorithms and Complexity 2007 som användes föregående kursomgångar,
Sup=Supplementet Algorithms and Complexity 2009.
- Period 3: algoritmer och datastrukturer
- F1 19 januari
-
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller,
bitkostnad och enhetskostnad. (GT: 3-46, 268-270, 686-688, KT/Moln: 29-56, 214-221)
- F2 22 januari
-
Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson.
- F3 26 januari
-
Repetition av sortering och datastrukturer. (GT: 55-130, 141-151, 217-238, KT/Moln: 57-65, 209-214)
- F4 29 januari
-
Datastrukturer: skipplistor, praktiska datastrukturer. (GT: 429-439, Sup: 77-83, KT/Moln: 595-602)
- Ö1 29 januari
-
Algoritmanalys.
- F5 2 februari
-
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
- F6 5 februari
-
Undre gränser. Korrekthetsbevis. (Sup: 17-29, KT/Moln: 535-547)
- Ö2 5 februari
-
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
- F7 9 februari
-
Grafer: sökning, maximala flöden. (GT: 287-334, 381-397, KT/Moln: 73-107, 337-357, 367-373)
- F8 12 februari
-
Giriga grafalgoritmer: minimala spännande träd, kortaste stigar. (GT: 339-353, 360-375, KT/Moln: 137-157)
- Ö3 12 februari
-
Grafalgoritmer.
- F9 16 februari
-
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (GT: 257-273, AC: 31-48, KT/Moln: 115-177, 183-188, 221-234, 242-246, Moln: 549-566)
- F10 19 februari
-
Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, 354-359, KT/Moln: 251-311)
- Ö4 19 februari
-
Dekomposition och lådpackning
- Labb 1 19-20 februari
-
Konkordans, redovisning.
- F11 23 februari
-
Algoritmkonstruktion: mer dynamisk programmering, geometriska algoritmer. (GT: 572-586)
- F12 26 februari
-
Algoritmkonstruktion: sortering i linjär tid, textsökning. (GT: 241-244, Sup: 1-16, Moln: 519-534)
- Ö5 26 februari
-
Dynamisk programmering. Teoriredovisning för labb 2.
- F13 2 mars
-
Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
- Mästarprov 1, senast måndag 2 mars klockan 10.15
-
Algoritmer.
- Ö6 5 mars
-
Algoritmkonstruktion.
- Period 4: komplexitet
- F14 16 mars
-
Reduktioner. (KT: 451-459, Moln: 375-383)
- Ö7 19 mars
-
Genomgång av lösning till mästarprov 1.
Reduktioner.
- Labb 2 19-20 mars
-
Flöden och matchningar, sista redovisningstillfälle.
- F15 23 mars
-
Introduktion till komplexitet. (GT: 592-599, KT: 463-466, Moln: 387-390)
- F16 26 mars
-
Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
- Ö8 26 mars
-
Oavgörbarhet. Teoriredovisning för labb 3.
- F17 30 mars
-
Turingmaskiner och Cooks sats.
- F18 2 april
-
NP-fullständighetsbevis. (GT: 600-602, KT: 466-495, Moln: 390-419)
- Ö9 2 april
-
NP-fullständighetsbevis.
- Labb 3 2-3 april
-
Ordkedjor, redovisning.
- F19 16 april
-
NP-fullständighetsreduktioner. (GT: 603-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
- Ö10 16 april
-
NP-fullständiga problem. Teoriredovisning för labb 4.
- F20 20 april
-
Approximationsalgoritmer. (GT: 618-626, KT: 599-630, Moln: 477-508)
- Ö11 23 april
-
Approximationsalgoritmer.
- Labb 4 23 april
-
NP-fullständighetsreduktioner, redovisning.
- F21 27 april
-
Heuristiska algoritmer, komplexitetsklasser. (KT: 495-497, 531-534, 661-670, Moln: 419-421, 455-471, 509-518)
- Mästarprov 2, senast 27 april klockan 10.15
-
Komplexitet.
- F22 4 maj
-
Repetition.
- Ö12 7 maj
-
Komplexitetsklasser och repetition.
- Teoritenta 25 maj klockan 9-12 i sal F1
Kursregistrering
Alla som vill gå kursen måste registrera sig på den. Detta görs med
kommandot
res checkin adk09
på någon av skolans Unixdatorer.
Registrera dig så snart som möjligt efter att kursen börjat!
Du bör också ge kommandot
course join adk09
Detta kommando gör två saker:
- Du får se eventuella nya meddelanden från kursledaren varje gång du
loggar in.
- Du får kursens användarmiljö, det vill säga alla initieringar
som kursledaren tycker att kursdeltagarna bör ha görs vid varje inloggning.
När du är klar med kursen ger du kommandot
course leave adk09
för att återställa allt.
Endast dom elever som studievägledningen lagt in i Ladok som
studerande på en kurs kan godkännas på kursen. Vill du läsa en kurs
som inte är obligatorisk för dig måste du alltså först välja kursen
i KTHs valsystem eller vid ditt programs studievägledning.
Du kan se dina resultat på redovisade uppgifter i kursen med kommandot
res show adk09
på någon av skolans Unixdatorer.
Kurskatalog
Kursen har en katalog på skolans Unixdatorer:
/info/adk09
.
På denna katalog finns textfiler, programskelett, program och liknande
som har med kursen att göra.
Examination
Följande betygskriterier kommer i år att 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 (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 (för SUALKO: ALKL, 1,5 hp)
- MAS1, mästarprov 1, 1,5 hp (för SUALKO: ALKA, 1,5 hp)
- MAS2, mästarprov 2, 1,5 hp (för SUALKO: ALKK, 1,5 hp)
- TEN2, tenta, 3 hp (för SUALKO: ALKE, 3 hp)
Nedan finns detaljerad information om dessa moment.
Labbar
Fyra obligatoriska datorlabbar ingår i kursen (två för SUALKO).
Dessa utgör momentet LAB1 (ALKL för SUALKO). Labbarna ska helst göras
i tvåpersonsgrupper. En- och trepersonsgrupper 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 tredje veckan av kursen
och till och med den vecka då labb 4 ska redovisas. Två labbpass i veckan
är schemalagda, och det är tänkt att halva gruppen ska gå på vardera
passet.
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 kan bara den labben redovisas.
Om du tappat ditt labbhäfte så finns labbframsida med plats för
underskrifter på kurswebbsidan.
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 någon av lärarna
eller lämnas in på
studentexpeditionen
senast den tid som anges på uppgiftslydelsen.
Den muntliga redovisningen kommer att ske senare samma vecka för
någon av assistenterna på en tid som ska bokas i förväg
med
bok
-kommandot.
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.
Du kan se dina resultat på redovisade uppgifter i kursen med kommandot
res show adk09
på någon av skolans Unixdatorer.
Tenta
Ordinarietentan går måndagen den 25 maj 2009 klockan 9 i sal F1.
Närmaste omtentatillfälle blir i augustiperioden.
Nästa tillfälle är i december på ordinarietentan för kursen DD2354 Algoritmer och komplexitet för F.
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.
Du behöver inte anmäla dig till tentan.
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 före tentan.
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 (efter att teoritentan är rättad) på tider den 1 juni.
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
|
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 programmering efter en detaljerad algoritmisk specifikation.
- Labb 3 (inte obligatorisk på SUALKO) är omprogrammering av ett existerande program så att det ska
fungera likadant fast effektivare.
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 programmeringsprojekt.
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.
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 2008
Antalet registrerade kursdeltagare var 152. Prestationsgraden var 85%.
68% var klara med hela labbkursen. 83% var klara med alla labbar utom labb 2.
76% var godkända på mästarprov 1 och 87% på mästarprov 2.
90% gick upp på ordinarietentan och 96% av dessa fick godkänt på den.
Elevsynpunkter 2008
Kursen ansågs vara ganska svår (46%) eller mycket svår (16%) av lite mer än
hälften, medan en resten tyckte den var medelsvår.
Examinationsformen med en tredjedel av vardera labbar, mästarprov och tenta
ansågs mycket bra (37%) eller bra (43%) av nästan alla.
75% var positiva till kamraträttning av teoritentan och bara 2% var negativa.
Det automatiska programtestningssystemet Kattis
fick helhetsbetyget mycket bra eller bra av 65%.
Endast 5% ansåg det vara dåligt.
De flesta tyckte att lärarens feedback vid muntliga redovisningarna av mästarproven var mycket bra eller bra. Bara 14% ansåg att feedbacken var
mindre bra eller dålig.
Planerade förändringar till 2009
-
Använd Indakursens bok som kursbok tillsammans med ett supplement med dom delar som inte täcks av Indaboken.
-
Sätt ut betygskriterierna istället för svårighetsmärkningen på mästarproven.
-
Skriv en tydligare text på
webbsidan som ger några exempel på hur man får olika betyg.
-
Lista några lämpliga övningsproblem i Kattis på kurswebbsidan.
Hederskodex
Skolan tillämpar en
hederskodex
i alla sina kurser och varje student förutsätts tillämpa
hederskodexen. Om du inte har läst den eller inte minns den: läs den på webben!