Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 436: Graduate Algorithms


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

CS 212 and CS 336 or CS MS or CS PhDs

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.

  • 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.
  • Formerly Comp_Sci 496 - last offer was Spring 2024

INSTRUCTOR: Prof. Konstantin Makarychev or Prof. Aravindan Vijayaraghavan

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