CSC 5160 - Topics in Algorithms

CSC5160 - Topics in Algorithms
This is an introductory graduate course on algorithm design. The aim is to provide a solid algorithmic background for researchers in computer science, engineering, or mathematics.

Lecture:	Thursday 1:30-2:15 LPN LT, Friday 9:30-11:15 ERB 712
Instructor:	Lap Chi Lau
Tutor:	Jerry J.L. Le

There are five major topics in this course. In each topic we'll study the most basic and important results (more specific or advanced materials are left for course projects). The purpose is to have a broad view on different algorithmic techniques. We'll start from the classical topics on polynomial time algorithms and linear and integer programming, to the modern topics on approximation algorithms, randomized algorithms, and applications of fixed point theorems.

Matchings and Network Flows - Two central problems in combinatorial optimization, which have many applications in different areas. The algorithmic techniques developed to solving them are the basic elements in algorithm design.

Stable matchings, Gale-Shapley algorithm.
Bipartite matchings, alternating paths, the Hungarian method.
Matchings in general graphs, Edmonds' theorem, Tutte's theorem.
Maximum flows, minimum cuts, min-max relations, Menger's theorem.
Minimum cost flows, submodular flows, graph orientations.

Linear and Integer Programming - A general and powerful tool for algorithm design. Many optimization problems can be modelled as linear programs, which can be solved in polynomial time. Sometimes this gives us polynomial time algorithms to solve the problems exactly; other times this gives us the best known approximation algorithms for NP-hard problems.

The duality theorem, complementary slackness.
The simplex method, the ellipsoid method, separation oracle.
Priaml-dual algorithms, the stable matching polytope, the matching polytope, path and flow polyhedra.
Integer programming, iterative rounding, totally dual integrality (TDI).

Approximation Algorithms - An approach to cope with NP-hard problems. We'll study many different techniques to design approximation algorithms, such as combinatorial techniques, greedy methods, dynamic programming, primal-dual methods, linear programming and semidefinite programming.

Combinatorial algorithms, minimum Steiner tree, the travelling salesman problem (TSP).
Dynamic programming, the knapsack problem.
Set cover, greedy algorithm, primal-dual algorithm, randomized rounding.
Maximum cut, semidefinite programming (SDP), Goemans-Williamson algorithm.

Randomized Algorithms - Learn how randomness can help computation. Randomized algorithms are often faster, or/and much simpler than deterministic algorithms. Sometimes randomized algorithms can even achieve what deterministic algorithms can not achieve yet (e.g. approximate counting).

Graph algorithms, minimum cuts, minimum spanning trees.
Probablistic methods, maximum satisfiability, the Ramsey number.
Packet routing, the Chernoff bound, the Lovász Local Lemma.
Balls and bins, martingales, the power of two choices.
Random sampling, approximate counting, random walks, Markov chains.

Applications of Fixed Point Theorems - Find out the surprising connections between mathematics and theoretical computer science. Fixed point theorems are mathematical theorems which show the existence of some "special points" of certain continuous functions. They have some fascinating applications in game theory (e.g. Nash-equilibrium), resource allocations, and even to combinatorial optimization problems!

Nash Equilibrium, Sperner's lemma, Brouwer's fixed point theorem.
The Ham Sandwich theorem, cake cutting, necklace, fair division, the Borsuk-Ulam theorem.

References: This course does not have a textbook. The following is a list of useful reference books.

	Alexander Schrijver Combinatorial Optimization: Polyhedra and Efficiency Springer, 2003
	Christos H. Papadimitriou, Kenneth Steiglitz Combinatorial Optimization: Algorithms and Complexity Dover Publications, 1998
	Alexander Schrijver Theory of Linear and Integer Programming John Wiley & Sons, 1998
	Vijay V. Vazirani Approximation Algorithms Springer, 2004
	Rajeev Motwani, Prabhakar Raghavan Randomized Algorithms Cambridge University Press, 1995
	Michael Mitzenmacher, Eli Upfal Probability and Computing: Randomized Algorithms and Probabilistic Analysis Cambridge University Press, 2005

Topics in Algorithms

Site menu: