Applicants who intend to apply for master course studies in this lab are expected to have already mastered the following topics
Computer Science
- How to analyze the time and space complexity of algorithms, in particular the asymptotic notations O() - big O,
Ω() - big Omega, and
Θ() - big Theta.
- Data structures and their analysis, especially Binomial heaps,
Balanced binary trees, such as red-black trees.
- Sorting algorithms and their analysis, Merge Sort,
Quick Sort,
Bucket Sort.
- Linear time algorithm for finding the median.
- DFS and BFS on graphs/digraphs, a linear-time algorithms for finding all cut-vertices in a graph using DFS and its correctness.
- Computational complexity Polynomial-time reduction between problems,
class NP, NP-hardness, NP-completeness.
- Algorithm design schemes The Branch-and-Bound Method,
Dynamic Programming,
Divide and Conquer.
Operations Research
- Linear Programming The simplex algorithm and duality,
The weak duality theorem and its proof,
The strong duality theorem.
- Dijkstra's shortest path algorithm
(together with correctness proof and time complexity analysis).
- Bellman-Ford's shortest path algorithm
(together with correctness proof and time complexity analysis).
- Kruskal's minimum spanning tree algorithm
(together with correctness proof and time complexity analysis).
- Prim's minimum spanning tree algorithm
(together with correctness proof and time complexity analysis).
- Maximum flow algorithm
(together with correctness proof and time complexity analysis).
- Approximation Algorithms 1.5-approximation to the TSP,
PTAS for the knapsack problem
- Graph Theory Edge- and vertex-connectivity,
Planar graphs,
Menger's theorem.
Applicants who intend to apply to the PhD course, in addition to the requirements for the master course outlined above, should also have solid knowledge of
- Linear Programming The strong duality theorem and its proof
- Fixed Parameter Tractable Algorithms
- Matroid Theory Uniform matroid, graph matroid, partition matroid,
Matching matroid,
The greedy algorithm,
Matroid intersection.
- Graph Theory Menger's theorem and its proof
Kuratowski's theorem and its proof.
The following books are useful references that cover the above topics
- Introduction to Algorithms
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
- Combinatorial Optimization: Algorithms and Complexity
By Christos H. Papadimitriou and Kenneth Steiglitz,
Dover Publications (1998).
- The Design and Analysis of Algorithms
By Dexter C. Kozen
Monographs in Computer Science.