Knowledge: Understand the mapping of problems to algorithmic solutions (such as graph problems). Understand the performance limitations of algorithms for specific problem categories. Understand different complexity classes (P, NP, NP hard, NP complete). Learn different techniques for solving difficult problems through the use of algorithms (such as exponential algorithms, randomized algorithms, approximation algorithms)
Skills: Understand algorithm reductions (the relationship between different problems with regards to their computational demands)
Course Content (Syllabus)
Linear Programming (e.g., duality, simplex method, interior point algorithms). Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization). Randomized algorithms. Approximation algorithms. Probabilistic analysis. Online algorithms and competitive analysis. Local Search.