Advanced Graduate Algorithms

CS 6550 - Spring 2019


[ Home | Lectures | Homeworks ]

COURSE INFO



CLASS TIMES: TuTh 1:30-2:45pm in Klaus 2447

INSTRUCTOR:   Eric Vigoda
Eric's office: Klaus 2222  
Email:
Office Hours: M/W 10-11am at Klaus 2222


TA:   Zongchen Chen
Email:
Office Hours: Tu/Th 4-5pm at Klaus 2222


GRADING:
  • Homeworks: 25%
  • Lecture notes: 20%
  • Midterm (in-class, week of March 12/14): 25%
  • Final project: 30%

TEXTBOOK:

TOPICS COVERED:
The course will focus on randomized algorithms.
Tentative list of topics:
  • Cute randomized algorithms, e.g., Karger's min-cut alg.
  • First moment method
  • Lovasz Local Lemma
  • Simple LP and SDP approximation algorithms
  • Balls into bins and hashing
  • Limited independence and applications (maximal independent sets and streaming)
  • Polynomial identity testing
  • Approximate counting and sampling
  • Markov Chain Monte Carlo (MCMC) algorithms

    • HOMEWORK POLICIES:
     Submissions:
    You need to type up your homework solutions using Latex. Homeworks are submitted via Gradescope.

    Collaboration:
    Homework solutions must be in your own words.
    It is probably best to try the homework on your own first. For the challenging problems, it might be useful to work together with other students. However, you should redo the solution from scratch by yourself, and write it up in your own words.
    List at the top of your homework who you collaborated with.
    You cannot consult outside sources, other than the above textbooks.