Sidst opdateret: 13. maj af SL

Datalogisk Institut
Københavns Universitet

Datalogi 2A: Algoritmik
2003-2004

Datalogi 2A er en fortsættelse fra efteråret 2003

Undervisere

Lærebøger

[CLRS] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Second Edition, MIT Press, Cambridge (2001).
[KB1] Kursusbog bind 1: Branch-and-bound Algorithms & Generelle Optimeringsheuristikker (Fås i 1. delen).
rettelser til [KB1] (ps, pdf)

Skemaoplysninger

Forelæsninger:
Tirsdag 11-13 i aud. 4 (HCØ)
Øvelseshold:
Hold 1: NEDLAGT!
Hold 2: Torsdag 11-13 i N010. Mads
Hold 3: Onsdag 9-11 i N018, Stinus
Hold 4: Mandag 12-14 i A105, Mads
Mads: di03i023@diku.dk
Stinus: stinus@diku.dk

Instruktorvagter under G2

Bemærk ændring: Onsdag den 21. april: Instruktorvagt 9-10 og 15-16 i Midgård (Stinus)
Uge 16: Ingen instruktorvagter.
Uge 17: Instruktorvagter i terminalrummet (Midgård) i stedet for øvelser.
Uge 18: Almindelige øvelser.
I opfordres til at benytte nyhedsgruppen.

Eksamensøvelser

Tilføjet d. 2. april: Næste gang eksamensøvelser for HOLD 3 er onsdag den 5. maj (efter I har afleveret G2).
Tilføjet d. 2. april: Næste gang eksamensøvelser for HOLD 2 er Torsdag den 6. maj

Som annonceret til de almindelige øvelsestimer vil der blive afholdt nogle eksamensøvelser, hvor der gennemgås eksamensspørgsmål. Formålet er at forberede jer så godt som muligt til den mundtlige eksamen. Det er jeres chance for at vænne jer til at stå ved tavlen, få styr på stoffet og få struktureret de enkelte spørgsmål.
Disse ekstra øvelser vil blive afholdt 5 gange på følgende tidspunkter:
Hold 2: Torsdag kl. 13-14 i lokale N030 (Mads)
Hold 3: Onsdag kl. 11-12 i lokale N018 (Stinus)
Hold 4: Mandag kl. 14-15 i lokale A105 (Mads)

Ideen er som følger:
Hver gang gennemgås to eksamensspørgsmål. Det forventes, at alle, der møder op til timerne, har set på spørgsmålene og forsøgt at strukturere dem, så de i princippet ville kunne gennemgå dem ved tavlen. Da der kun er tale om 45 min., skal man have struktureret gennemgangen så meget, at man har valgt det centrale stof ud - der bruges 15-20 min. på hvert spørgsmål, og det er ikke muligt at nå det hele på den tid. Efterfølgende kan man tale om, hvorvidt de andre er enige i prioriteringen. Husk på, at det er jeres chance for at blive klar til eksamen - hvis ingen har forberedt sig, vil der ikke blive nogen gennemgang.
Første gang er i uge 12.
Hold 3: Vi gennemgår spørgsmål 5 (Segment Intersection Problem using Plane Sweep) og 6 (Strongly connected components).
I er som altid velkomne til at sende spørgsmål eller kommentarer til instruktorerne.

Punktsætning

Kursets omfang svarer til 4 punkter (10 ECTS).

Bedømmelse

Der stilles i løbet af kurset to G-opgaver (en i hvert semester), der skal godkendes (med mulighed for genaflevering). Godkendelse er en forudsætning for at kunne gå til eksamen!

Kurset afsluttes med en mundtlig, karaktergivende eksamen (i på forhånd kendte spørgsmål).

Forelæsningsplan

Opgaver gennemgås ved øvelserne den følgende uge.

Forelæsningsplanen er vejledende og ret til ændringer forbeholdes!

Uge Lærer Emne [CLRS] [KB1] Supplement Opgaver
6 JK Single-source shortest paths 24

24.5-1, 24.5-8, 24.1-1, 24.1-3, 24.3-1, 24.3-3, 24.3-4
7 JK All-pairs shortest paths 25.1-25.2

25.1-8, 25.1-9, 25.1-10
Eksamensspørgsmål 7, 8 og 9 (indtil Floyd-Warshall)
8 JK Maximum flow: classical algorithms 26.1-26.3

25.2-1, 25.2-4 ,26,1-4, 26.1-6, 26.2-1, 26.2-7
Eksamensspørgsmål 1 og 9 (Floyd-Warshall)
9 JK Maximum flow: push-relabel algorithms 26.4-26.5

26.5-1, 26-1, 26-3
Eksamensspørgsmål 2 og 3
10 JK Graph algorithms: summing up


26-4, 26-5
Eksamensspørgsmål 4 og 10
11 DP The class NP and NP-completeness 34-34.3
Plancher [ ps | pdf | ps4 | pdf4 ] 34.1-1, 34.1-2, 34.1-4, 34.1-6, 34.2-1, 34.2-2, 34.2-4, 34.2-6, 34.2-8, 34-3 a)+b)
12 DP Reduction among NP-complete problems 34.4-34.5
Plancher [ ps | pdf | ps4 | pdf4 ] 34.2-9, 34.2-10, 34.3-3, 34.3-6, 34.3-7, 34.4-4, 34-3 c)+d)
13 DP More NP-complete problems 34.4-34.5
Plancher [ ps | pdf | ps4 | pdf4 ] 34.4-5, 34.4-6, 34.4-7, 34.5-1, 34.5-5, 34.5-6, 34-2, 34-3 e)+f)
14 DP The Branch-and-Bound paradigm
Del 1 Plancher [ ps | pdf | ps4 | pdf4 ] [KB1] Opgave 1-6
15 DP Design issues for branch-and-bound algorithms
Del 1 Plancher [ ps | pdf | ps4 | pdf4 ]
NP-kompendium
Knapsack-demo

16
Påske
G2 stilles 14. april kl. 11



17
G2 (ingen forelæsning)


[KB1] Opgave 7-11
Knapsack-opgaver [ ps | pdf ]
Gennemgås ved øvelserne i uge 19
18
DP 		Forelæsninger 10-12
Approximation algorithms: the vertex-cover, travelling-salesman problem, and set covering
G2 afleveres 30. april kl. 11
35-35.3

Plancher [ ps | pdf | ps4 | pdf4 ] 		[KB1] Opgave 7-11
Knapsack-opgaver [ ps | pdf ]
19 DP Approximation algorithms: the subset-sum problem 35.4-35.5

Plancher [ ps | pdf | ps4 | pdf4 ] 		35.1-1, 35.1-2, 35.1-4, 35.1-5, 35-1
Eksamensspørgsmål
20 JK bemærk ændret rækkefølge
Computability, eksamensforberedelse


FPTAS-opgave [ ps | pdf ]
Eksamensspørgsmål
21 DP Heuristics
Del 2 Plancher [ ps | pdf | ps4 | pdf4 ] Ingen øvelser pga. eksamen - held og lykke!
22
23
Eksamen 27/5-4/6




Eksamensspørgsmål

Eksamens-HOWTO [ ps | pdf ]

  1. Sorting (heapsort and quicksort in particular)
  2. Binary Search Trees (red-black trees in particular)
  3. Divide-and-Conquer (general principles and their application to the Closest Pair Problem)
  4. Minimum Spanning Trees and use of heaps, disjoint sets
  5. Segment Intersection Problem using Plane Sweep
  6. Strongly connected components
  7. Single-source shortest paths: Bellman-Ford's algorithm
  8. Single-source shortest paths: Dijkstra's algorithm
  9. All-pairs shortest paths
  10. Maximum flow
  11. NP-completeness: concepts and definitions
  12. NP-completeness: an example of a proof
  13. Branch-and-bound
  14. Approximation algorithms
  15. A fully-polynomial-time approximation scheme
Supplerende spørgsmål:

Der kan ved eksamen stilles supplerende spørgsmål indenfor alle dele af pensum, f.eks.

Dispositioner

Forslag til dispositioner til spørgsmålene 1-5 udarbejdet af Pawel Winter.
Forslag til dispositioner til spørgsmålene 6-10 udarbejdet af Jakob Krarup.
Forslag til dispositioner til spørgsmålene 11-15 udarbejdet af David Pisinger.


Pensum: Kursorisk stof