Design and Analysis of Algorithms

This course is designed for international students in USTC, and the language is English.

Syllabus

• Approximation algorithms
  • NP-completeness, computational complexity reduction, Cook’s theorem, etc
  • Basics of approximation of optimization problems
  • Basic algorithms: approximation algorithms for graph coloring, multi-machine scheduling, packing, traveling salesman, vertex cover, and maximum independent set problems
• Randomized algorithms
  • Probability review and concentration bounds
  • Las Vegas Algorithms, e.g., randomized quick sort
  • Monte Carlo Algorithms, e.g., primality testing, and matrix multiplication
  • Some other basic randomized algorithms
• Distributed algorithms
  • Basics of distributed computing models
  • Basics of distributed algorithms: synchronous and asynchronous network models, leader election, spanning tree construction, broadcast, breadth/depth-first search, shortest path, maximum independent set, and other distributed algorithms