• Pensum li>
• Eksamination i gammelt pensum li>
• Eksamination i nyt pensum (kun for studerende der tidligere har fulgt kurset) li>
• Eksamens-HOWTO

Eksamen 2002

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. Single-source shortest paths: Bellman-Ford's algorithm
7. Single-source shortest paths: Dijkstra's algorithm
8. All-pairs shortest paths
9. Maximum flow: Edmond-Karp
10. Maximum flow: Push-relabel algorithms (main ideas only)
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.
- Greedy Paradigm
- Dynamic Programming
- Amortized analysis
- Heaps
- Depth-first search and strongly connected components
- Non-computable problems (halting, totality, equivalence)
- Heuristics (simulated annealing, tabu search, genetic algorithms)

Pensum

Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms"
Kapitel: 1, 2, 3, 4.1-4.3, 6, 7, 8.1, 12.1-12.3, 13, 15.1-15.4, 16.1-16.3, 17, 19, 20, 21.1-21.3, 22.3-5, 23, 24.1-24.3, 24.5, 25.1-25.2, 26.1-26.3, 26.4 (til og med Lemma 26.15), 26.5 (kun fig. 26.9 og 26.10 samt definition af de deri benyttede begreber) 33, 34 (ej Lemma 34.6), 35.0-35.3, 35.5.

Goldschlager, Lister: "Computer Science"
Afsnit 3.1.1-3.1.4.

Kursusbog 1:
del 1

Kursorisk stof:

Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms"
Kapitel: 8, 9.
Bevis for Lemma 34.6

kursusbog 1:
del 2