Courses
  /  
Descriptions
EECS 496: Graduate Algorithms

Quarter Offered

Spring : 2-3:20 TuTh ; Vijayaraghavan

Description

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.

INSTRUCTOR: Prof. Aravindan Vijayaraghavan (aravindv@eecs.northwestern.edu)

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).