Nada

^ Upp till kursens ingångssida.

Information om DD1352, Algoritmer, datastrukturer och komplexitet våren 2002

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

Extra labbredovisningstid för labb 1-3 var det tisdag den 13 augusti 2002 klockan 10-12 i Vit sal. Nästa chans att redovisa labbarna blir under ordinarie labbpass för 2003 års kursomgång.

Kursanalysen 2002 finns nu.

Extra labbredovisningstid för labb 1-3 blir det torsdag den 30 maj 2002 klockan 10-12 i Grå sal. Nästa chans att redovisa labbarna blir i augusti.

Information om fördelning av labb 4-uppgifterna och specifikationer av in- och utdata i labb 4.

Nu går det bra att boka in sig för muntlig redovisning av mästarprov 2. Gör telnet till datorn my och ge där kommandot

bok new adk02

Den som har bestämda önskemål om särskilda redovisningstider måste boka in sig genast medan det finns tider kvar alla dagar.

I labb 2 saknas bokstaven é i alfabetet vilket gör att ord som innehåller den bokstaven inte kan nås. Det går bra att ha det på det sättet, men den som vill får gärna lägga till é i alfabetet.

Nu går det bra att boka in sig för muntlig redovisning av mästarprov 1. Gör telnet till datorn my och ge där kommandot

bok new adk02

Den som har bestämda önskemål om särskilda redovisningstider måste boka in sig genast medan det finns tider kvar alla dagar.

För att ingen ska behöva idiotoptimera sitt Javaprogram i labb 1 har jag slöat ner referensprogrammet /info/adk02/labb1/bipmatch (som också är skrivet i Java) ytterligare, vilket gör att tiden har förlängts med drygt 40%. Du ska alltså inte behöva spara tid genom att arbeta bort alla funktionsanrop utan genom förändringar i algoritmer och datastrukturer.

Under gamla Solaris 2.6 som körs till exempel på datorn My finns inte samma Javaversion, så där kan inte bipmatch och matchtest i labb 1 köras. Logga in på en nyare dator eller använd istället /info/adk01/labb1/matchtest (adk01 istället för adk02).

Som kösystem vid terminalövningarna i ADK/SUALKO använder vi i år på prov det nya 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.

Notera att torsdagsföreläsningarna under kursens första fem veckor är i sal D1 och ingen annanstans.

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@nada.kth.se. Övningsassistenter för dom fyra grupperna är
  1. Rafael Pass, rafael@nada.kth.se
  2. Gustav Hast, ghast@nada.kth.se
  3. Fredrik Niemelä, d00-fni@nada.kth.se
  4. (SU) Jonas Holmerin, joho@nada.kth.se

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 med över 200 kronor till cirka 690 kronor.

Dessutom ingår 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 50 kr. Papper som delas ut under kursens gång kommer i slutet av veckan att finnas på kurswebbsidan.

Schema

KTHs centrala schema gäller med två undantag. Föreläsningarna på torsdagarna i period 3 (vecka 3-7) är flyttade till sal D1 och labbredovisningen den 14 mars är flyttad till Spel- och Sporthallen.

Schema för period 3, 2002

v3 Mån 14/1 Tis Ons Tor 17/1 Fre
9:00F
M1
10:00
11:00
12:00F
D1
13:00
14:00Ö
Q32,33,35
15:00
v4 Mån 21/1 Tis Ons Tor 24/1 Fre
9:00F
M1
10:00
11:00
12:00F
D1
13:00
v5 Mån 28/1 Tis Ons Tor 31/1 Fre 1/2
8:00L Grå, Vit,
Karmosin
9:00F
M1
10:00
11:00
12:00F
D1
13:00
14:00Ö
Q31,32,33
L Grå, Vit,
Karmosin
15:00
v6 Mån 4/2 Tis Ons Tor 7/2 Fre 8/2
8:00L Grå, Vit,
Karmosin
9:00F
M1
10:00
11:00
12:00F
D1
13:00
14:00Ö
Q31,32,25
L Grå, Vit,
Karmosin
15:00
v7 Mån 11/2 Tis Ons Tor 14/2 Fre 15/2
8:00L Grå, Vit,
Karmosin
9:00F
M1
10:00
11:00
12:00F
D1
13:00
14:00Ö
Q33,34,35
L Grå, Vit,
Karmosin
15:00
v8 Mån 18/2 Tis Ons Tor 21/2 Fre 22/2
8:00L Grå, Vit,
Karmosin
9:00F
M1
10:00
11:00
12:00
13:00
14:00Ö
Q33,34,35
L Grå, Vit,
Karmosin
15:00
v9 Mån 25/2 Tis Ons 27/2 Tor Fre
9:00F
M1
10:00
11:00
12:00
13:00L Grå, Vit,
Karmosin
14:00
15:00Ö
Q32,33,34
L Grå, Vit,
Karmosin
16:00

Schema för period 4, 2002

v11 Mån 11/3 Tis Ons Tor 14/3 Fre 15/3
9:00F
D1
10:00F
M1
L Grå, Vit,
Karmosin
11:00
12:00
13:00Ö
Q24,25,34
14:00
15:00L Sporthallen,
Spelhallen
16:00
v12 Mån 18/3 Tis Ons Tor 21/3 Fre 22/3
9:00F
D1
10:00F
E1
L Grå, Vit,
Karmosin
11:00
12:00
13:00Ö
Q33,25,34
L Grå, Vit,
Karmosin
14:00
v16 Mån 15/4 Tis Ons Tor 18/4 Fre 19/4
9:00F
D1
10:00L Grå, Vit,
Karmosin
11:00F
D1
12:00
13:00
14:00Ö
Q12,13,14
15:00
16:00L Orange,
Gul, Grön
17:00
v17 Mån 22/4 Tis Ons Tor 25/4 Fre 26/4
9:00F
D1
10:00L Grå, Vit,
Karmosin
11:00F
D1
12:00
13:00
14:00Ö
Q12,13,14
15:00
16:00L Magenta,
Orange, Röd
17:00
v19 Mån 6/5 Tis Ons 8/5 Tor Fre
9:00F
D1
10:00Ö
Q32,33,34
11:00
v20 Mån 13/5 Tis Ons 15/5 Tor Fre
9:00F
D1
10:00Ö
Q32,33,34
11:00

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

Kursregistrering

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

res checkin adk01

(res checkin sualko02 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. Det finns möjlighet att få betyg 6 på kursen. Du måste uppfylla två krav för att få betyg 6: dels måste du göra den frivilliga labbuppgiften 4 och redovisa före tentan, och dels måste du få minst 50 poäng på ordinarietentan eller någon av det närmaste årets omtentor.

Tenta

Ordinarietentan går lördagen den 1 juni 2002 klockan 14-19 i sal E31-36, E51-52 och D34. Omtentatillfällen blir måndagen den 12 augusti klockan 8-13 i sal L51 samt 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 (rakt under studentexpeditionen). 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.

Labb 4 ska bara göras av den som aspirerar på att få betyg 6. Den ger inga poäng till tentan. Ett speciellt redovisningstillfälle för labb 4 kommer att anordnas i slutet av maj.

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! Mer om fusk vid examination kan du läsa om här.

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.

Kursanalysen 2001.

Diverse länkar

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

^ Upp till kursens ingångssida.


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