Nada

^ Upp till kursens ingångssida.

Information om adk04, Algoritmer, datastrukturer och komplexitet våren 2004

ADK samläses med kursen Algoritmer och komplexitet (SUALKO) på matte-datalinjens årskurs 3 på SU. SUALKO har en egen övningsgrupp och 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

Omtenta 15 januari 2005
Nästa omtentatillfälle är lördag 15 januari 2005 klockan 8.00-13.00 i sal Q22 och Q23. Johan Karlander konstruerar tentan.

Restlabbsredovisning
Nästa tillfälle att redovisa restlabbar är under ordinarie kursomgång i vår.

Kursanalys.

Tenta 2004-06-01
Tentan är nu rättad och resultatet är anslaget på Nadas tentaanslagstavla på plan 3 och är inrapporterat i res. Dina resultat syns med

res show adk04


Valinformation: kurser i teoretisk datalogi som följer på ADK.

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. Övningsassistenter för dom fyra grupperna är
  1. Gustav Hast,
  2. Rafael Pass (period 3), Jon Larsson (period 4),
  3. Jakob Nordström,
  4. (SU) Johan Thuresson.

Kurslitteratur

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

Kursbok

Baase och Gelder: Computer Algorithms - Introduction to Design & Analysis, upplaga 3, 2000, Addison-Wesley, ISBN 0-201-61244-5. Efter förhandlingar med förlaget har kursledaren lyckats sänka priset på boken i kårbokhandeln till 520 kronor.

Dessutom ingår 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

Kursbunten kommer att kunna köpas på Nadas studentexpedition för 80 kr. Papper som delas ut under kursens gång kommer senast i slutet av veckan att finnas på kurswebbsidan.

Schema

Här finns aktuella schemat för kursen. Det skiljer sig från KTHs centrala schema på några punkter.

För det första är följande labbsalar ändrade (men tiderna är oförändrade):

fredag   6/2 kl 10-12 Spel, Sport, Musik
fredag   6/2 kl 13-15 Spel, Sport, Musik
fredag  13/2 kl 10-12 Spel, Sport, Musik
fredag  13/2 kl 13-15 Spel, Sport, Musik
fredag  20/2 kl 10-12 Spel, Sport, Musik
fredag  20/2 kl 13-15 Spel, Sport, Musik
fredag  27/2 kl 10-12 Spel, Sport, Musik
fredag  27/2 kl 13-15 Spel, Sport, Musik
måndag   1/3 kl 10-12 Konst, Mat, Sport, Musik
tisdag   2/3 kl 13-15 Magenta, Karmosin, Grå (som i KTH-schemat)
torsdag 18/3 kl 13-15 Spel, Sport, Mat (som i KTH-schemat)
fredag  19/3 kl 10-12 Magenta, Karmosin, Grå (som i KTH-schemat)
torsdag 25/3 kl 15-17 Konst, Mat, Musik, Grå  
fredag  26/3 kl 10-12 Spel, Sport, Musik
torsdag  1/4 kl 15-17 Spel, Sport, Musik
fredag   2/4 kl 10-12 Spel, Sport, Musik
torsdag 29/4 kl 15-17 Spel, Sport, Musik
fredag  30/4 kl 10-12 Magenta, Karmosin, Grå (som i KTH-schemat)
Dessutom är första övningen för grupp 1 (Gustav Hasts grupp) senarelagd en vecka. Den flyttas från fredag 23 januari kl 10-12 i Q34 till torsdag 29 januari kl 15-17 i rum 4523, plan 5 i D-huset på Nada (gå in i Nadakorridoren, ta till vänster och gå runt ljusgården).

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. CA står för kursboken Computer Algorithms.
Period 3: algoritmer
F1 19 januari
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (CA 1)
F2 22 januari
Repetition av sortering och datastrukturer. (CA 4.1-4.6, 4.8-4.9, 2, 6.1-6.5)
Ö1 23 januari
Algoritmanalys.
F3 26 januari
Undre gräns för sortering. Andra undre gränser. (CA 4.7, 5)
F4 29 januari
Grafer: sökning, maximala flöden. (CA 7, Biggs 18)
F5 2 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (CA 8)
F6 5 februari
Effektiv kodning. Gästföreläsning av Stefan Nilsson.
Ö2 5 februari
Grafalgoritmer.
F7 12 februari
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (bl a CA 12.3)
Ö3 12 februari
Dekomposition och lådpackning
F8 6 februari
Algoritmkonstruktion: dynamisk programmering. (CA 10)
F9 19 februari
Algoritmkonstruktion: mer dynamisk programmering. (CA 9.1-9.5)
Ö4 19 februari
Dynamisk programmering.
Labb 1 20 februari
Flöden och matchningar, sista redovisningstillfälle.
F10 23 februari
Algoritmkonstruktion: sortering i linjär tid, textsökning. (CA 4.11, 11.1-11.3)
Ö5 25 februari
Algoritmkonstruktion.
F11 26 februari
Algoritmkonstruktion: polynomberäkningar och FFT. (CA 12.2, 12.4)
Mästarprov 1, senast måndag 1 mars klockan 10.00
Algoritmer.
Period 4: datastrukturer, komplexitet
F12 15 mars
Datastrukturer: skipplistor, praktiska datastrukturer. (Pugh, artikel i kursbunten)
F13 17 mars
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 18 mars
Genomgång av lösning till mästarprov 1. Datastrukturer.
Labb 2 18 och 19 mars
Optimering av ordkedja, redovisning.
F14 22 mars
Introduktion till komplexitet. (CA 13.1-13.2)
F15 24 mars
Reduktioner. (CA 13.3)
Ö7 25 mars
Reduktioner.
F16 29 mars
Oavgörbarhet. (Harel, artikel i kursbunten)
F17 31 mars
Turingmaskiner och Cooks sats. (Ausiello, artikel i kursbunten)
Ö8 1 april
Oavgörbarhet.
F18 26 april
NP-fullständighetsbevis.
F19 28 april
NP-fullständighetsreduktioner.
Ö9 29 april
NP-fullständighetsbevis.
Labb 3 29 och 30 april
Konkordans, redovisning.
F20 3 maj
Approximationsalgoritmer. (CA 13.4-13.5)
Ö10 5 maj
NP-fullständighetsbevis.
F21 10 maj
Probabilistiska och parallella algoritmer. (CA 14)
Ö11 12 maj
Approximationsalgoritmer.
Mästarprov 2, senast måndag 17 maj klockan 8.15
Komplexitet.
F22 17 maj
Komplexitetsklasser, repetition.
Ö12 19 maj
Repetition.
Tenta 1 juni
klockan 8-13

Kursregistrering

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

res checkin adk04

(res checkin sualko04 för SU) på någon av Nadas Unixdatorer. Registrera dig så snart som möjligt efter att kursen börjat!

Du bör också ge kommandot

course join adk01

Detta kommando gör två saker:

När du är klar med kursen ger du kommandot

course leave adk01

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 betyget på tentan. Försöket med betyg 6 har avslutats. Det går alltså inte att få högre betyg än 5 på kursen i år.

Tenta

Ordinarietentan går tisdagen den 1 juni 2004 klockan 8-13 i sal Q22-36. Omtentatillfällen blir i augustitentaperioden och efter jul. Det är också möjligt att gå upp på tentorna på kursen 2D1354 (Algoritmer och komplexitet för F); dessa tentors upplägg är likadant, men det är en annan kursledare som har kursen.

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.

Anmälan till tentan

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

Individuella uppgifter

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 adk01

på någon av Nadas 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. Den som vid redovisningen av en labb kan redogöra för lösningarna på teoriuppgifterna får två bonuspoäng. Teoriuppgifterna måste redovisas tillsammans med labben och senast bonusdatumet.

Sammanlagt kan alltså labbarna 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:

Alla labbar har givna effektivitetskrav och utförs som lagarbete (labbgrupper), precis som i verkliga 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å Nadas Unixdatorer: /info/adk01. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

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 utföras. Synpunkter kan lämnas till lärarna.

I kursanalysen 2003 kan man se hur kursen gick förra året. På tentan klarade sig 147 av 160. Eleverna var mestadels positiva. Största klagomålet var på att de var för få handledare som tog emot labbredovisningar. Det blir förhoppningsvis tillräckligt många nu i vår. Vidare tyckte några att handledarna hade olika krav vid labbredovisningarna. I år kommer handledarna att få noggranna beskrivningar av vad som krävs och diskutera det på ett handledarmöte.

Kursanalys 2004.

Diverse länkar

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

Handledarschema

^ Upp till kursens ingångssida.


Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Senast ändrad 16 januari 2010
Tekniskt stöd: <webmaster@nada.kth.se>