Nada

^ Upp till kursanalysen.

Faktiskt innehåll i adk04, Algoritmer, datastrukturer och komplexitet våren 2004

ADK samlästes med kursen Algoritmer och komplexitet (SUALKO) på matte-datalinjens årskurs 3 på SU. SUALKO hade en egen övningsgrupp och en mindre labbkurs än ADK (och får 5 poäng istället för 6). I övrigt var kurserna identiska.

Tid

Kursen gick i period 3-4 2003/2004, dvs januari-1 juni 2004.

Lärare

Kursledare och föreläsare var Viggo Kann, viggo@nada.kth.se. Övningsassistenter för dom fyra grupperna var
  1. Gustav Hast,
  2. Rafael Pass (period 3), Jon Larsson (period 4),
  3. Jakob Nordström,
  4. (SU) Johan Thuresson.

Kurslitteratur

Kursbok

Baase och Gelder: Computer Algorithms - Introduction to Design & Analysis, upplaga 3, 2000, Addison-Wesley, ISBN 0-201-61244-5.

Dessutom ingick kapitel 18 (i gamla upplagan kapitel 11) i Biggs: Discrete mathematics som var kursbok i kursen Diskret matematik som gick samtidigt som ADK för D2.

Kursbunt

Läsanvisning

CA står för "Baase: Computer algorithms". och Har står för "Harel: Algorithmics - the spirit of computing".
NivåKapitel/avsnitt
1 CA 1-3
1 CA 4.1-4.6, 4.8
3 CA 4.7, 4.9, 4.11
2 CA 5
2 CA 6.1-6.6
3 CA 7
2 CA 8-9
3 CA 10
2 CA 11.1-11.3
2 CA 12
3 CA 13.1-13.4
2 CA 13.5-13.8
2 CA 14
3 Har, kapitel 8 Noncomputability and undecidability
2 Pugh, artikel om skipplistor
2 Ausiello, kapitel 6.1
2 Maximala flöden med Ford-Fulkerson (t ex Biggs eller Grimaldi)

Nivåer

1. Läs som repetition.

2. Läs igenom, men detaljer och bevis är inte väsentliga.

3. Läs i detalj.

Kursinnehåll

Kursen består av 22 föreläsningar och 12 övningar.
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

^ Upp till kursanalysen.


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