bild
Skolan för
datavetenskap
och kommunikation

^ Upp till kursens ingångssida.

Information om adk06, Algoritmer, datastrukturer och komplexitet, våren 2006

ADK samläses med kursen Algoritmer och komplexitet (SUALKO) på matte-datalinjens årskurs 3 på SU. SUALKO har en mindre labbkurs än ADK (och får 5 poäng istället för 6). I övrigt är kurserna identiska. Klicka här för information om SU-kursen Algoritmer och komplexitet

Senaste nytt

Extra redovisningstid för labbarna blir det tisdag 22 augusti 2006 klockan 10-12 i Spelhallen. Detta blir sista tillfället att redovisa labbar före nästa kursomgång våren 2007. Ingen förhandsanmälan.

Omtentan i ADK är tillsammans med ordinarietentan i kursen 2D1354 Algoritmer och komplexitet lördag den 16 december 2006 klockan 8.00-13.00 i sal D31, D32, E31, E32. Johan Karlander gör tentan. Bonuspoäng från kursomgången adk06 räknas in i tentan. Den som behöver komplettera mästarproven kan gör hemtalen i 2D1354 under hösten. Viggo är bortrest hela hösten.

Kursanalysen finns här.

Extra redovisningstid för labbarna var det fredag 16 juni 2006 klockan 10-11 i Grå sal.

Ordinarietenta 2006-05-23: tentalydelse och lösningar.

Lösningsförslag till mästarprov 2.

Föreläsningen den 4 maj klockan 10-12 flyttas till sal K2 på grund av en konferens.

Mästarprov 2 ska redovisas skriftligt senast den 11 maj klockan 10 och muntligt i veckan efteråt. Mästarprovet ska göras strikt individuellt, utan något som helst samarbete.

Uppgifter på föreläsning 18: Delgrafsisomorfi - reducera klickproblemet. Mängdpartitionering - reducera delmängssumma.

Observera att sista labbtillfället är fredag 7 april kl 8-10. Det är sista tillfället att redovisa labb 3 för bonuspoäng. Det kommer att anordnas ett restredovisningstillfälle i tentaveckan.

Kattis hårdvara kommer att bytas under fredagen 10 mars. Under en del av fredagen kommer Kattis därför att vara ur drift.

Övningsgrupp 4 ställs in från och med 2 mars. Den 23 mars när det är teoriredovisning för labb 3 uppstår dock grupp 4 tillfälligt och träffas då i sal D35.

Mästarprov 1 ska redovisas skriftligt senast den 27 februari klockan 10 och muntligt i veckan efteråt. Mästarprovet ska göras strikt individuellt, utan något som helst samarbete. Boka in din redovisningstid så snart det går genom att ge kommandona

telnet hippograff
bok new adk06
Förtydligande till uppgift 1 för betyg 5 på mästarprov 1: personerna ska även efter förflyttningarna stå på heltalspunkter.

I labb 2 och 3 används det automatiska labbrättningssystemet Kattis (hette tidigare Marvin). Lösenord har skickats ut till alla registrerade på kursen.

Som kösystem vid terminalövningarna i ADK/SUALKO används SimaManager. Kösystemet startas med kommandot sm. Sedan väljer man kursen "adk" och kan ställa sig i kö för redovisning eller hjälp mycket enkelt.

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:

  1. Isaac Elias
  2. Jakob Nordström
  3. Martin Rehn
  4. Öjvind Johansson (gruppen upphör efter period 3)
Om övningsgrupp i har övning i sal x och grupp j har övning i sal y så gäller att i<j om och endast om x<y.

Nya må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.

Kursbok

Det finns två alternativa kursböcker:
  • Levitin: Introduction to The Design & Analysis of Algorithms, 2003, Addison-Wesley, ISBN 0-321-21076-X. Boken rekommenderas för den som redan har den från Indakursen.
  • Kleinberg och Tardos: Algorithm design, 2005, Pearson Addison Wesley, ISBN 0-321-29535-8. Boken rekommenderas för den som inte har Levitin redan. Den kan köpas i kårbokhandeln för 640 kronor.
Den som har förra årets kursbok (Computer Algorithms av Baase och Gelder) kan använda den istället för ovanstående böcker.

För den som har Levitin ingår dessutom kapitel 18 (i gamla upplagan kapitel 11) i Biggs: Discrete mathematics som är kursbok i kursen Diskret matematik som går samtidigt som ADK för D2.

Det finns en detaljerad läsanvisning inför tentan.

Kursbunt

  • Kursprogram (i stort sett denna text).
  • Tre obligatoriska laborationsuppgifter.
  • Två mästarprov (individuella uppgifter) som delas ut under kursens gång.
  • Föreläsnings- och övningsanteckningar (delas ut första föreläsningen varje vecka under kursens gång).
  • Artikel om skipplistor av Pugh.
  • Kapitel 8 ur Harel: Algorithmics - the spirit of computing.
  • Avsnitt 6.1 ur Ausiello m fl: Complexity and Approximation.
  • Kompletterande material beroende på kursbok, ur Kleinberg-Tardos för den som har Levitin och ur Levitin för den som har Kleinberg-Tardos (delas ut föreläsning 5).
  • Fyra exempeltentor.
Kursbunten kommer att kunna köpas på studentexpeditionen på Osquars backe 2, plan 2, för 100 kr. Föreläsningsanteckningar och uppgifter som delas ut under kursens gång kommer senast i slutet av veckan att finnas på kurswebbsidan.

Schema

Här finns schemat för kursen.

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 vilket avsnitt i kurslitteraturen som behandlas. Lev står för kursboken av Levitin och KT för kursboken av Kleinberg-Tardos.
Period 3: algoritmer och datastrukturer
F1 18 januari
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (Lev 2, appendix B; KT 2, 5.2)
F2 19 januari
Effektiv kodning. Gästföreläsning av Stefan Nilsson.
F3 23 januari
Repetition av sortering och datastrukturer. (Lev 1.4, 3.1, 4.1-4.4, 5.1, 6.4; KT 5.1)
F4 26 januari
Datastrukturer: skipplistor, praktiska datastrukturer. (Pugh - artikel i kursbunten, Lev 6.3, 7.3)
Ö1 26 januari
Algoritmanalys.
F5 30 januari
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F6 2 februari
Undre gräns för sortering. Andra undre gränser. (Lev 10.1-10.2)
Ö2 2 februari
Datastrukturer. Undre gränser. Teoriredovisning för labb 1.
F7 6 februari
Grafer: sökning, maximala flöden. (Lev 5.2-5.3, Biggs 18; KT 3, 7.1-7.3, 7.5)
F8 9 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (Lev 9.1-9.3; KT 4.4-4.6)
Ö3 9 februari
Grafalgoritmer.
F9 13 februari
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (Lev 3.4, 4.5, 5.4, 9.4, 11.1-11.2; KT 5.3-5.5, 4.1-4.3, 4.7-4.8)
F10 16 februari
Algoritmkonstruktion: dynamisk programmering. (Lev 8; KT 6.1-6.8)
Ö4 16 februari
Dekomposition och lådpackning
Labb 1 16-17 februari
Konkordans, redovisning.
F11 20 februari
Algoritmkonstruktion: mer dynamisk programmering.
F12 23 februari
Algoritmkonstruktion: sortering i linjär tid, textsökning. (Lev 3.2, 7.1-7.2)
Ö5 23 februari
Dynamisk programmering. Teoriredovisning för labb 2.
F13 27 februari
Algoritmkonstruktion: polynomberäkningar och FFT. (Lev 6.5; KT 5.6)
Mästarprov 1, senast måndag 27 februari klockan 10.15
Algoritmer.
Ö6 2 mars
Algoritmkonstruktion.
Period 4: komplexitet
F14 16 mars
Reduktioner. (Lev 6.6; KT 8.1)
Ö7 16 mars
Genomgång av lösning till mästarprov 1. Reduktioner.
Labb 2 16-17 mars
Flöden och matchningar, sista redovisningstillfälle.
F15 20 mars
Introduktion till komplexitet. (Lev 10.3; KT 8.3)
F16 23 mars
Oavgörbarhet. (Harel, artikel i kursbunten)
Ö8 23 mars
Oavgörbarhet. Teoriredovisning för labb 3.
F17 3 april
Turingmaskiner och Cooks sats. (Ausiello, artikel i kursbunten)
F18 6 april
NP-fullständighetsbevis. (KT 8.4-8.8)
Ö9 6 april
NP-fullständighetsbevis.
Labb 3 6-7 april
Optimering av ordkedja, redovisning.
F19 20 april
NP-fullständighetsreduktioner. (KT 8.2, 8.10)
Ö10 20 april
NP-fullständighetsbevis.
F20 24 april
Approximationsalgoritmer. (Lev 11.3; KT 11.1-11.5)
F21 4 maj
Heuristiska algoritmer, komplexitetsklasser. (KT 12.1-12.2, 8.9, 9.1-9.3)
Ö11 4 maj
Approximationsalgoritmer.
Mästarprov 2, senast 11 maj klockan 10.15
Komplexitet.
F22 11 maj
Repetition.
Ö12 11 maj
Repetition.
Tenta 23 maj
klockan 8-13

Kursregistrering

Alla som vill gå kursen måste registrera sig på den. Detta görs med kommandot

res checkin adk06

(res checkin sualko06 för SU) 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 adk06

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 adk06

för att återställa allt.

Endast dom teknologer 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.

Obligatoriska moment och slutbetyg

Kursen har tre obligatoriska moment i Ladok:
TEN1
Tenta, 3 poäng
HEM1
Mästarprov, 1 poäng
LAB1
Datorlaborationer, 2 poäng
Nedan finns detaljerad information om dessa moment. Kursens slutbetyg är medelbetyget på mästarprovet och tentan, avrundat nedåt.

Tenta

Ordinarietentan går tisdagen den 23 maj 2006 klockan 8-13 i sal Q11-15, Q22-24. Omtentatillfällen blir efter period 2, vid ordinarietentan för kursen 2D1354 (Algoritmer och komplexitet för F), som har samma upplägg på tentorna.

Tentan består av en teoridel (om 20 poäng) utan hjälpmedel och en problemdel (om 30 poäng) med kursböckerna, föreläsningsanteckningar och egna anteckningar som hjälpmedel (men inga lösta tentor). För godkänt krävs minst 25 poäng. Den som presterat bra lösningar till båda mästarproven kan ha klarat av 12 poäng på problemdelen i förväg. Den som redovisat datorlabbarna i tid och har svarat rätt på teoriuppgifterna på labbarna får 9 poängs bonus på tentan. Frågorna på teoridelen behandlar bara det som tagits upp på föreläsningarna och nämnts i dom utdelade föreläsningsanteckningarna.

Tentaresultatet anslås högst tre veckor efter tentan på institutionens anslagstavla på plan 3. 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.

Anmälan till tentan

Du behöver inte anmäla dig till tentan.

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 i bokhyllan utanför 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 två uppgifter. Varje uppgift ger upp till 3 poäng. För godkänt på det obligatoriska momentet HEM1 krävs minst hälften rätt (alltså 6 av totalt 12 poäng).

Varje mästarprov motsvarar också ett 6-poängstal på problemdelen av tentan. Poängen från motsvarande mästarprov adderas till problemdelstalet, men mer än 6 poäng ges inte. Den som har full poäng på ett mästarprov slipper alltså göra motsvarande tal på tentan. Detta gäller på alla tentor som går inom ett kalenderår räknat från kursstart.

Den som inte klarat momentet HEM1 på mästarproven kan istället få det godkänt genom att klara (eller komplettera med) motsvarande tal på tentan.

Du kan se hur många poäng du fått på mästarproven om du ger kommandot

res show adk06

på någon av skolans Unixdatorer.

Labbar

Tre obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. 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 var och en upp till två bonuspoäng.

Sammanlagt kan alltså labbarna och teoriuppgifterna ge 3+6=9 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 3 ska redovisas. Två labbpass i veckan är schemalagda, och det är tänkt att halva årskursen 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 här.

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 nu!

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 är omprogrammering av ett existerande program så att det ska fungera likadant fast effektivare.
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. På huvuddelen av tentan (problemdelen) är kurslitteraturen rekommenderat hjälpmedel så att det i alla fall inte ska krävas stora utantillkunskaper.

Kurskatalog

Kursen har en katalog på skolans Unixdatorer: /info/adk06. 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 har gjorts och redovisas i kursanalysen. 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 av ändringar införda i årets kurs:

  • Ny kursbok (val mellan Levitin och Kleinberg-Tardos).
  • Ändrad ordning (datastrukturer för algoritmer) för att kursen ska passa ihop med den utdragna kursen i diskret matematik.
  • Omarbetade labbar. Labb 2 och 3 testas automatiskt med Marvin.
  • Redovisning av labbteori på övningstid.
  • Betygsviktningen har modifierats.

Diverse länkar

Skicka gärna brev till Viggo om du har tips på lämpliga länkar för denna lista.

Handledarschema Tid

^ Upp till kursens ingångssida.

Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2006-07-12