Courses
  /  
Descriptions
COMP_SCI 496: Graduate Algorithms

Quarter Offered

Winter : 3:30-4:50 TuTh ; Vijayaraghavan
Spring : 11-11:50 MWF ; Makarychev

Prerequisites

The pre-requisites for the course includes the undergraduate Algorithms course (COMP_SCI 336 or equivalent) and COMP_SCI 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 (Winter) & Prof. Konstantin Makarychev (Spring)

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