Nada

^ Upp till kursens ingångssida.

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

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. I övrigt är kurserna identiska.

Klicka här för information om SU-kursen Algoritmer och komplexitet

Senaste nytt

Kursanalysen är klar.

Nästa labbredovisningstid för labb 1-3 blir i februari 2002 på ADK-kursens ordinarie labbtider. Se KTH-schemat för våren 2002 för exakta tider och platser.

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

Övningsgrupp 2 (Öjvinds) är inställd från och med vecka 14.

I den version av hemtal 2 som finns i föreläsningsanteckningarna finns det fel:

Minskat tidskrav i labb 1: programmet får vara dubbelt så långsamt som bipmatch.

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@nada.kth.se. Mottagningstid är onsdagar klockan 10.00-11.00, telefon 08-790 62 92. Övningsassistenter för dom fyra grupperna är
  1. (SU) Jonas Holmerin, joho@nada.kth.se
  2. Öjvind Johansson, ojvind@nada.kth.se
  3. Gustav Hast, ghast@nada.kth.se
  4. Mårten Trolin, marten@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.

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 att finnas i en pärm i hyllan i entrérummet utanför expeditionen.

Schema

Schema för period 3, 2001

v3 Mån 15/1 Tis 16/1 Ons 17/1 Tor 18/1 Fre 19/1
10:00F
F2		F
D1
11:00
12:00
13:00Ö
E31, 35, 51
14:00
v4 Mån 22/1 Tis 23/1 Ons 24/1 Tor 25/1 Fre 26/1
10:00F
F2
11:00
v5-8 Mån Tis Ons Tor Fre
10:00F
F2		F
D1
11:00
12:00L Magenta,
Karmosin, Grå
13:00Ö
E51-52, Q12
14:00
15:00L Magenta,
Karmosin, Grå
16:00
v9 Mån 26/2 Tis 27/2 Ons 28/2 Tor 1/3 Fre 2/3
10:00F
M1
11:00
12:00
13:00Ö
B22-24		L Magenta,
Karmosin, Grå
14:00
15:00L Magenta,
Karmosin, Grå
16:00

Schema för period 4, 2001

v11-12 Mån Tis Ons Tor Fre
10:00F
M1		F
D1
11:00
12:00
13:00Ö
E31, 35, 51
14:00L Magenta,
Karmosin, Grå
15:00L Magenta,
Karmosin, Grå
16:00
v13 Mån 26/3 Tis 27/3 Ons 28/3 Tor 29/3 Fre 30/3
10:00F
M1		F
M1
11:00
12:00
13:00
14:00L Magenta,
Karmosin, Grå
15:00L Magenta,
Karmosin, Grå		Ö
E31, 35-36
16:00
v14 Mån 2/4 Tis 3/4 Ons 4/4 Tor 5/4 Fre 6/4
10:00F
M1		F
M1
11:00
12:00
13:00Ö
E31, 35, 51
14:00L Magenta,
Karmosin, Grå
15:00L Magenta,
Karmosin, Grå
16:00
v19 Mån Tis Ons Tor Fre
10:00F
M1
11:00
12:00
13:00
14:00
15:00Ö
E32-33
16:00
v20 Mån Tis Ons Tor Fre
10:00F
M1
11:00
12:00
13:00
14:00
15:00Ö
Q31-32
16: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 15 januari
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (CA 1)
F2 18 januari
Repetition av sortering, undre gräns för sortering, repetition av datastrukturer. (CA 4.1-4.9, 2, 6.1-6.5)
Ö1 18 januari
Algoritmanalys.
F3 22 januari
Genomgång av programspråket C för den som kan Java. Häftet C för den som kan Java kan köpas på Nadas expedition för 20 kronor.
F4 29 januari
Grafer: sökning, maximala flöden. (CA 7, Biggs 11, även 9.4-9.5)
F5 1 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (CA 8, även Biggs 9.3, 9.6)
Ö2 1 februari
Grafalgoritmer.
F6 5 februari
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (bl a CA 12.3)
F7 8 februari
Algoritmkonstruktion: dynamisk programmering. (CA 10, även Biggs 12.4-12.6)
Ö3 8 februari
Dekomposition och lådpackning
F8 12 februari
Algoritmkonstruktion: Mer dynamisk programmering. (CA 9.1-9.5)
F9 15 februari
Algoritmkonstruktion: sortering i linjär tid, textsökning. (CA 4.11, 11.1-11.3)
Ö4 15 februari
Dynamisk programmering.
Labb 1 15 och 16 februari
Flöden och matchningar, redovisning.
F10 19 februari
Algoritmkonstruktion: polynomberäkningar och FFT. (CA 12.2, 12.4)
F11 22 februari
Datastrukturer: skipplistor, praktiska datastrukturer. (Pugh, artikel i kursbunten)
Ö5 22 februari
Algoritmkonstruktion.
Hemtal 1, senast måndag 26 februari klockan 10.15
Algoritmer.
F12 26 februari
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 26 februari
Datastrukturer.
Period 4
F13 12 mars
Introduktion till komplexitet. (CA 13.1-13.2)
F14 15 mars
Reduktioner. (CA 13.3)
Ö7 15 mars
Reduktioner.
Labb 2 13 och 16 mars
Optimering av ordkedja, redovisning.
F15 19 mars
Oavgörbarhet. (Harel, artikel i kursbunten)
F16 22 mars
Turingmaskiner och Cooks sats. (Ausiello, artikel i kursbunten)
Ö8 22 mars
Oavgörbarhet.
F17 26 mars
NP-fullständighetsbevis.
F18 29 mars
NP-fullständighetsreduktioner.
Ö9 29 mars
NP-fullständighetsbevis.
F19 2 april
Approximationsalgoritmer. (CA 13.4-13.5)
F20 5 april
Approximationsscheman och heurestiker. (CA 13.6-13.8)
Ö10 5 april
NP-fullständighetsbevis.
Labb 3 3 och 6 april
Konkordans, redovisning.
F21 7 maj
Probabilistiska och parallella algoritmer. (CA 14)
Ö11 7 maj
Approximationsalgoritmer.
F22 14 maj
Komplexitetsklasser, repetition.
Ö12 14 maj
Repetition.
Hemtal 2, senast måndag 14 maj klockan 10.15
Komplexitet.

Kursregistrering

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

res checkin adk01

(res checkin sualko01 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
Hemtal, 1 poäng
LAB1
Datorlaborationer, 2 poäng
Nedan finns detaljerad information om dessa moment. Kursens slutbetyg är betyget på tentan. Det finns från och med i år 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 26 maj 2001 klockan 8-13 i sal Q11-15, Q21-23. Omtentatillfällen blir i augustiperioden och efter jul.

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 hemtalen 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 elevexpeditionen). Klagomål på rättning av tentan görs till kursledaren.

Anmälan till tentan

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

Hemtal

Två obligatoriska hemtal 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 hemtal 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 hemtal motsvarar också ett 6-poängstal på problemdelen av tentan. Poängen från motsvarande hemtal adderas till problemdelstalet, men mer än 6 poäng ges inte. Den som har full poäng på ett hemtal 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å hemtalen 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å hemtalen 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.

Hemtalen 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.

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>