Courses / DescriptionsEECS 495: Graduate Algorithms
Quarter OfferedWinter : 2-3:20 TuTh ; Vijayaraghavan
COURSE DESCRIPTION: This is an introductory graduate level course on Algorithms that will give broad exposure to recent advances in algorithms, yet cover the fundamental techniques needed to understand the recent advances in algorithms research. At the end of the course, students will be able to read and understand research papers in most recent areas of algorithms research.
PRE-REQUISITES: The pre-requisites for the course includes the undergraduate Algorithms course (EECS 336 or equivalent) and EECS 212 or equivalent. Some familiarity with linear algebra is useful, but not necessary strictly.
A TENTATIVE LIST OF TOPICS IS GIVEN BELOW:
1. Concentration bounds / Large deviations, Chernoff bounds.
2. Hashing, balls and bins, power of two choices.
3. Probabilistic method, random graphs, average-case analysis.
4. Linear programming (review) , LP Duality.
5. Ellipsoid Algorithm, convex programming.
6. Approximation algorithms, randomized rounding.
7. Eigenvalues, eigenvectors, random walks, expanders.
8. Dimension reduction (Johnson-Lindenstrauss), PCA/ SVD, Clustering in high dimensions.
9. Semi-definite programming, use in approximation algorithms.
10. Metric Embeddings, Locality Sensitive Hashing.
11. Competitive Analysis, Online algorithms
12. PAC learning, VC theory.
13. Multiplicative weights, applications (online learning, zero-sum games).