CMPT 409/CMPT 815/MATH 796 - Approximation/Randomized Algorithms - Fall 2019
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:
Books for reference:
Grading:
Final Exam - 65%
Homework assignments - 30%
Participation - 5%