Nada

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

Tid

Kursen gick i period 3-4 2000/2001, dvs januari-maj 2001.

Lärare

Kursledare och föreläsare: Viggo Kann (professor i datalogi)
Övningsassistenter: Jonas Holmerin (SU), Gustav Hast, Öjvind Johansson, Mårten Larsson (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.1-5.3, 5.6
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 Harel, kapitel 8 Noncomputability and undecidability
2 Pugh, artikel om skipplistor
2 Ausiello, kapitel 6.1
2 Biggs, kapitel 11 alternativt 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 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.

^ Upp till kursomgångar.


Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 11 februari 2007
Tekniskt stöd: <webmaster@nada.kth.se>