Advanced Topics on Algorithms

This course studies fundamental algorithmic problems with the objective of developing a deep understanding of the basic and advanced techniques for design and analysis of algorithms. The topics of the course include basic algorithms for graph problems such as coloring, Hamilton cycle, traveling salesman problem and others; network flow problems; matching; arithmetic techniques such as Fast Fourier Transform; and computational problems in geometry. We study deterministic, randomized, and approximation algorithms, as well as, the basic complexity theory for complexity classes such as P, NP, and PSPACE. The prerequisites for the course are some introductory course on algorithms and a strong mathematical background.