CMPT 409/CMPT 815/MATH 796 - Approximation/Randomized Algorithms - Fall 2019

Course Information Syllabus Lectures Assignments Exams


Course outline:

SFU course outlines

Syllabus:

  • Approximation algorithms
  • Randomized algorithms
  • Linearity of expectation
  • Concentration inequalities
  • Color coding (for finding longest path)
  • Polynomial method
  • Linear programming
  • Semidefinite programming
  • Random walks
  • Expander graphs
  • Sublinear time algorithms
  • The PCP theorem
  • Hardness of approximation

Related courses:

Lap Chi Lau's course notes
Anna Karlin's course notes
Chandra Chekuri's course notes
Luca Trevisan's course notes

Books for reference:

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal

Grading:

Final Exam - 65%
Homework assignments - 30%
Participation - 5%