Läsanvisningar anges med fetstil. Läs alltid inledningen till de kapitel som anges, dvs om det står att 26.2 ska läsas, läs då också inledningen till kapitel 26.
Du får ut betydligt mer av föreläsningarna om du läser i förväg!

Uppgifter anges med kursiv stil. Uppgifterna rekommenderas och kommer till en del att behandlas på övningar.
Du får ut betydligt mer av övningarna om du tittar på uppgifterna i förväg!

'CLR' åsyftar kursboken
'Öuppg' åsyftar häftet med övningsuppgifter.
'Håstad' och 'Harel' finns i kursbunten.

Vecka 3
F1: Kursinformation, algoritmanalys, beräkningsmodeller, enhets- och bitkostnad, O-notation, korrekthet och komplexitet.
CLR 1-3. CLR 2-1, 2-2.
F2: Sorteringsalgoritmer, undre gräns för sortering.
CLR 4, 6, 8, 9.
Ö1: Algoritmanalys.
CLR 2-1, 2-2, 2-3, 2-4, 4-3.

Vecka 4
F3: Listor, heapar, (balanserade) sökträd. Heapsort. Prioritetskö.
CLR 7, 11, 13.1-13.3, 14.
F4: Grafer, definitioner, representation, sökning och flöden.
CLR 5.4, 5.5, 23, 27.1-27.3.
Ö2: Datastrukturer, grafalgoritmer.
Öuppg 1, 2, 3, 4

Vecka 5
F5: Mininmala spännande träd, kortaste stigar.
CLR 24, 25.1-25.2, 26.2.
Labhandledning 2/2 i Orange kl 15-17
F6: Algoritmkonstruktion. Giriga algoritmer, dekomposition och dynamisk programmering.
CLR 4, 16, 17.1-17.2.
Ö3: Grafalgoritmer. Algoritmkonstruktion.
CLR 8-3, 7.5-6; Öuppg 6, 7, 9

Vecka 6
F7: Algoritmkonstruktion. Polynommultiplikation. LCS.
CLR 16, 32
Labhandledning 9/2 i Orange kl 8-10
F8: FFT
CLR 32
Ö4: Dekomposition och dynamisk programmering.
Öuppg 10, 11, 12, 13, 14.
Laboration 1 (Flöden och matchningar) redovisas fredag 12 februari och måndag 15 februari (deadline för bonus).

Vecka 7
F9: Hashtabeller och skiplistor.
CLR 6.1-6.4, 12, utdelat material.
F10: Introduktion till komplexitet, Turingmaskiner.
Harel, Håstad
Ö5: Algoritmkonstruktion.
Öuppg 15; CLR 12.3-2; Multiplikation av stora heltal.

Vecka 8
F11: Reduktioner.
Inlämningsuppgift 1 lämnas in senast 17.00 måndag 22 februari.
F12: Beräkningsbarhet, oavgörbara problem.
Harel, Håstad
Ö6: Reduktioner, beräkningsbarhet.
Öuppg 8, 16.

Vecka 9
F13: Icke-determinism, P och NP.
CLR 36.
F14: Cooks sats, NP-fullständighet.
CLR 36.
Labhandledning 4/3 i Orange kl 15-17
Ö7: Oavgörbarhet, NP-fullständighetsbevis.
Öuppg 17; andra exempel.
Muntlig redovisning av inlämningsuppgift 1.

Vecka 10
F15: NP-fullständighetsbevis.
CLR 36
F16: Komplexitetsklasser.
CLR 36, Håstad
Labhandledning 11/3 i Orange kl 15-17
Ö8: NP-fullständighetsbevis.
Öuppg 18, 19; andra exempel

Vecka 11
F17: Approximationsalgoritmer.
CLR 37
Inlämningsuppgift 2 lämnas in senast 17.00 måndag 15 mars.
F18: Repetition / Tentaräkning.
Ö9: Repetition / Tentaräkning.
Redovisning av laboration 2 (Multiplikation av stora heltal??) senast fredag 19 mars.

Vecka 12
Muntlig redovisning av inlämningsuppgift 2.