Nada

Faktiskt innehåll i 2D1352, Algoritmer, datastrukturer och komplexitet 1999

Tid

Kursen gick i period 3-4 1998/1999, dvs januari-maj 1999.

Lärare

Kursledare och föreläsare var Viggo Kann, lektor på Nada, datorpost viggo@nada.kth.se. Övningsassistenter: Lars Ivansson, Öjvind Johansson, Staffan Ulfberg (alla doktorander i teoretisk datalogi)

Kurslitteratur

David Harel: Algorithmics - the spirit of computing, Addison-Wesley, ISBN 0-201-50401-4.

Dessutom användes för algoritmdelen boken Cormen, Leiserson, Rivest: Introduction to Algorithms, McGraw-Hill, ISBN 0-07-013143-0, som användes i Indakursen.

Läsanvisning

NivåKapitel/avsnitt
1 Har 1-3
3 Har 4-9
2 Har 10-11
0 Har 12
1 Sortering, sökning (CLR 1,7-8)
2 Sortering, sökning (CLR 9)
1 Enkla datastrukturer (CLR 11-13)
2 Balanserade träd (CLR 14)
3 Dynamisk programmering (CLR 16)
2 Grafalgoritmer (CLR 23-24, 25.1-25.2, 26.2, 27.1-27.3)
2 FFT (CLR 32)
2 Kinesiska restsatsen (CLR 33.5)
2 Geometriska algoritmer (CLR 35)
3 NP-fullständighet (CLR 36.3-36.5)
2 Approximationsalgoritmer (CLR 37)
2 Skipplistor (utdelad artikel)
0. Ingår inte alls.

1. Ingick i tidigare kurser, läs som repetition.

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

3. Läs i detalj.

Kursbunt

Kursinnehåll

Kursen består av 24 föreläsningar och 12 övningar. Följande tabell visar vad som behandlades under föreläsningarna och övningarna.
Period 3
F1 19 januari
Introduktion, repetition av algoritmanalys, beräkningsmodeller, bitkostnad och enhetskostnad, undre och övre gränser. (Har 6)
F2 20 januari
Repetition av sortering, undre gräns för sortering, korrekthet. (Har 5)
Ö1 20 januari
Algoritmanalys.
F3 26 januari
Repetition av datastrukturer (heapar, binära träd), balanserade träd. (CLR 14)
F4 27 januari
Grafer: representation, sökning, maximala flöden. (CLR 23,25.1-25.2, se också Biggs)
Ö2 27 januari
Grafalgoritmer.
F5 2 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (CLR 24,27.1-27.3, se också Biggs)
F6 3 februari
Algoritmkonstruktion: dekomposition, dynamisk programmering och giriga algoritmer. (Har 4 samt CLR 16)
Ö3 3 februari
Dekomposition och dynamisk programmering.
F7 9 februari
Algoritmkonstruktion: totalsökning, exempel på dekomposition och dynamisk programmering. Sortering i linjär tid. (Har 4 samt CLR 16)
F8 10 februari
Geometriska algoritmer. (CLR 35)
Ö4 10 februari
Dekomposition och dynamisk programmering.
Labb 1 17 och 19 februari
Flöden och matchningar, redovisning.
F9 16 februari
FFT - snabb Fouriertransform. (CLR 32)
F10 17 februari
Kinesiska restsatsen, översikt över algoritmer. (CLR 33.5)
Ö5 17 februari
Algoritmkonstruktion.
Hemtal 1, senast måndag 22 februari
Algoritmer.
F11 23 februari
Datastrukturer: skipplistor, praktiska datastrukturer.
F12 24 februari
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 24 februari
Datastrukturer.
Period 4
F13 16 mars
Introduktion till komplexitet. (Har 7)
F14 17 mars
Reduktioner.
Ö7 17 mars
Reduktioner.
Labb 2 17 och 18 mars
Skärning mellan linjesegment, redovisning.
F15 23 mars
Oavgörbarhet. (Har 8)
F16 24 mars
Enkla beräkningsmodeller (turingmaskiner, ändliga automater) och deras kraftfullhet. (Har 9)
Ö8 24 mars
Oavgörbarhet.
F17 20 april
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (Har 7 samt CLR 36.3-36.4)
F18 21 april
NP-fullständighetsbevis.
Ö9 21 april
NP-fullständighetsbevis.
Labb 3 21 och 22 april
Konkordans, redovisning.
F19 27 april
NP-fullständighetsreduktioner.
F20 28 april
Komplexitetsklasser.
Ö10 28 april
NP-fullständighetsbevis.
F21 4 maj
Approximationsalgoritmer. (CLR 37)
F22 5 maj
Mer om approximation. (CLR 37)
Ö11 5 maj
Komplexitetsklasser, approximationsalgoritmer.
Hemtal 2, senast måndag 10 maj
Komplexitet.
F23 11 maj
Parallella och probabilistiska algoritmer och komplexitet. (Har 10-11)
F24 12 maj
Repetition.
Ö12 12 maj
Repetition.

^ Upp till kursomgångar.


Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 12 augusti 1999
Tekniskt stöd: <webmaster@nada.kth.se>