Eksamensspørgsmål
- Sorting (heapsort and quicksort in particular)
- Binary Search Trees (red-black trees in particular)
- Divide-and-Conquer (general principles and their
application to the Closest Pair Problem)
- Minimum Spanning Trees and use of heaps, disjoint sets
- Segment Intersection Problem using Plane Sweep
- Strongly connected components
- Single-source shortest paths: Bellman-Ford's algorithm
- Single-source shortest paths: Dijkstra's algorithm
- All-pairs shortest paths
- Maximum flow
- NP-completeness: concepts and definitions
- NP-completeness: an example of a proof
- Branch-and-bound
- Approximation algorithms
- 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
- Non-computable problems (halting, totality,
equivalence)
- Heuristics (simulated annealing, tabu search,
genetic algorithms)
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.