## 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.