Nada

^ Upp till kursens ingångssida.

Information om adk05, Algoritmer, datastrukturer och komplexitet våren 2005

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

Det går en omtenta 15 december 2005 klockan 14.00-19.00 i Q11-Q12. Därefter går bonuspoäng intjänade våren 2005 ut. Nästa tentamöjlighet är ordinarietentan 23 maj 2006.

Den som har labbar kvar och absolut vill redovisa före våren 2006 kan vända sej till Öjvind Johansson.

En kursanalys finns nu.

Omtentan måndag 29 augusti 2005 är rättad.

Ordinarietentan 2005-06-04 är rättad och betygen rapporterade i res. 78% klarade tentan. Här finns tentalydelse och lösningsförslag.

Lösningsförslag till mästarprov 2 finns nu.

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.

Övningsgrupperna har olika inriktningar, och det står var och en fritt att välja övningsgrupp eller byta grupp under kursens gång. Övningsassistent och inriktning för varje grupp är:

  1. Gustav Hast (enkel inriktning),
  2. Isaac Elias (mellansvår inriktning),
  3. Jakob Nordström (ännu lite svårare inriktning),
  4. Fredrik Niemelä (programmeringstävlingsinriktning, för den som vill kunna konstruera och implementera algoritmer snabbt och säkert; gruppen finns bara under algoritmdelen av kursen).
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.

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

Kursregistrering

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

res checkin adk05

(res checkin sualko05 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 adk05

Detta kommando gör två saker:

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

course leave adk05

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. Om medelbetyget blir 3,5 eller 4,5 bestäms betyget av tentan.

Tenta

Ordinarietentan går lördagen den 4 juni 2005 klockan 8-13 i sal Q25, Q32-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 adk05

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

Nada tillämpar en hederskodex i alla sina kurser och varje student som läser en Nadakurs 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/adk05. 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 har gjorts. Synpunkter kan lämnas till lärarna.

I kursanalysen kan man se hur kursen gick.

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 25 november 2005
Tekniskt stöd: <webmaster@nada.kth.se>