Nada

Faktiskt innehåll i adk02, Algoritmer, datastrukturer och komplexitet 2002

Tid

Kursen gick i period 3-4 2001/2002, dvs januari-1 juni 2002.

Lärare

Kursledare och föreläsare: Viggo Kann (professor i datalogi)
Övningsassistenter: Jonas Holmerin (SU), Gustav Hast, Rafael Pass, Fredrik Niemelä (alla utom Fredrik doktorander i teoretisk datalogi).

Kurslitteratur

Kursbok

Baase och Gelder: Computer Algorithms - Introduction to Design & Analysis, upplaga 3, 2000, Addison-Wesley.

Kursbunt

Läsanvisning

CA står för "Baase: Computer algorithms".

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. Följande tabell visar vad som behandlades under föreläsningarna och övningarna.
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 (lösning i Postscript)
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.
Labb 4 31 maj
Hörntäckning, överkurs, redovisning.

^ Upp till kursomgångar.


Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 27 juli 2004
Tekniskt stöd: <webmaster@nada.kth.se>