Nada

^ Upp till kursanalysen.

Faktiskt innehåll i adk05, Algoritmer, datastrukturer och komplexitet våren 2005

ADK samlästes med kursen Algoritmer och komplexitet (SUALKO) på matte-datalinjens årskurs 3 på SU. SUALKO hade 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 2004/2005, dvs januari-4 juni 2005.

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. Martin Rehn,
  3. Jakob Nordström,
  4. Fredrik Niemelä (endast period 3).

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

^ Upp till kursanalysen.


Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Senast ändrad 12 september 2005
Tekniskt stöd: <webmaster@nada.kth.se>