sidst opdateret: 19-3-2002
Datalogisk Institut
Københavns Universitet

Datalogi 2A: Algoritmik

2001-2002


Kontaktperson
Andre Undervisere
Instruktorer

Forelæsningsplan forår 2002

Spørgetime på øvelsesholdene[New]

Uge Lærer Indhold/Emne Transparencies Opgaver (gennemgås ved øvelser i ugen efter forelæsningen) Beviser: (*) kun hovedtræk Opgaver for interesserede studerende
6 JK Depth-first search
Strongly connected components. 22.3-22.5		 Udleveres ved forelæsning
 Gennemgås ved Øvelserne i uge 7
22.1-1 22.1-3 22.1-5 22.2-1 22.2-3 22.2-6 22.5-1 22.5-2 22.5-3

7 JK Single-source shortest paths. 24 Udleveres ved forelæsning 24.5-1, 24.5-8, 24.1-3, 24.2-4, 24.3-1, 24.3-1 Lemma 24.1 Teorem 24.4 (*) Teorem 24.6 (*) 24.1-5, 24.3-6, 24.3-7, 24.2
18/02 MZ K1 stilles den 18. februar 2002, kl. 9.00
 K-opgave (ps) K-opgave (pdf) LEDA my_heap.h run_heaps.cc Spørgetime: onsdag 20. februar kl. 12.15 i Lille Aud.
8 JK All-pairs Shortest Paths. 25.1-25.2 Udleveres ved forelæsning 25.1-3 25.1-8 25.1-9 25.1-10
25.2-4 25.2-5 25.2-6 25.2-8		 Formuler ligning 25.2 og 25.5 25.2-9 25.1 25.2
9 JK Maximum flow: Classical algorithms. 26.1-26.3 Udleveres ved forelæsning 26.1-1 26.1-6 26.2-1 26.2-2 26.2-4 26.2-7 26.2-9 26.3-1 Theorem 26.726.1 26.2
10 JK Maximum Flow: Push - relable. 26.4-26.5
O1 stilles 		Udleveres ved forelæsning
O1-opgave (ps) 		26.5-1, 26.5-3
 Intuition bag push-relabel(699-671ø), PUSH(671n-672n), RELABEL(672n-67m), SCC(G), Bellman-Ford, Dijkstra, Edmonds-Karp 26-4, 26-6
11 JK Graph Algorithms: Summing up * Udleveres ved forelæsning


12 DP  The class NP and NP-completeness, Chapter 34-34.3.
O1 afleveres		 Plancher kan kopieres i 1.delen, plancher
1M$ prisopgaver
P versus NP
Minesweeper is NPC 		34.1-1, 34.1-2, 34.1-4, 34.1-5, 34.1-6, 34.2-1, 34.2-2, 34.2-3, 34.2-4, 34.2-5 To eksamensspørgsmål gennemgås
14 DP Reduction among NP-complete problems, Chapter 34.4-34.5 Plancher kan kopieres i 1.delen, plancher
 34.2-6, 34.2-9, 34.2-10, 34.3-2, 34.3-3, 34.3-6, 34.3-7, 34.4-1, 34.4-4 To eksamensspørgsmål gennemgås
15 DP More NP-complete problems, Chapter 34.4-34.5 Plancher kan kopieres i 1.delen, plancher
Kompendium over NP-fuldstændige problemer (pdf)		 34.4-5, 34.4-6, 34.4-7, 34.5-1, 34.5-5, 34.5-6 To eksamensspørgsmål gennemgås 34-3
16 DP The Branch-and-Bound Paradigm, kursusbog 1, del 1  Plancher kan kopieres i 1.delen, plancher
O1 genaflevering 		opgave 1,2,3,4,8,9 i spredningsproblemer To eksamensspørgsmål gennemgås opgave 5,6,7,10
17 DP Design issues for branch-and-bound algorithms,
Kursusbog 1, del 1.		 Plancher kan kopieres i 1.delen, plancher, plancher
O2 stilles		 Tentative
kursusbog 1.del: opg 1, 2, 3, 4 (skitser kun), 5, 6		 To eksamensspørgsmål gennemgås
18 DP 1.maj - undervisningsfri
O2-spørgetime 13-15 i lille auditorium DIKU

To eksamensspørgsmål gennemgås
19 DP Approximation algorithms: the vertex-cover and
travelling-salesman problems, 35-35.3		 Plancher kan kopieres i 1.delen

O2 afleveres		 35.1-1, 35.1-2, 35.1-4, 35.1-5 To eksamensspørgsmål gennemgås 35.1-3
20 DP Approximation algorithms; the set covering and subset-sum problem, 35.4-35.5.
Heuristics, kursusbog 1, del 2		 Plancher kan kopieres i 1.delen
plancher uge 19 og 20 [New] (bemærk: bevis for subset-sum efter gammel bog!)		 35.2-2, 35.2-5, 35.5-4 To eksamensspørgsmål gennemgås
21 DP/JK Heuristics, kursusbog 1, del 2
Computability		 Plancher kan kopieres i 1.delen
**udleveres senest ved forelæsning
To eksamensspørgsmål gennemgås
22 DP/JK Spørgetime Onsdag 13.15-14.00, auditorium 2, HCØ


Noter

* Diverse ikke-nået stof fra de første fem forelæsningsgange. ** Sections 3.2.1-3.2.4 in L. Goldschlager, A. Lister, "Computer Science", Prentice-Hall, 1982. Udleveres ved forelæsningen. Letlæst og ret underholdende