Courses
  /  
Descriptions
EECS 496: Graduate Algorithms

Quarter Offered

Winter : 3:30-4:50 TuTh ; Vijayaraghavan

Prerequisites

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.

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)

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