CS7800: Advanced Algorithms

[Home] [Schedule]
The schedule is tentative and subjects to change (e.g. snow days)
Date Topic Reading Additional readings/references (optional)
Sep 5
Introduction, probability, hashing
Lecture notes 1
Sep 9
Load balancing
Lecture notes 2 High Speed Hashing for Integers and Strings by Thorup.
Sep 12
Large deviation bounds and applications
Lecture notes 3 Concentration of Measure for the Analysis of Randomised Algorithms by Dubhashi and Panconesi.
Sep 16
Power of two choices
Lecture notes 4 Power of two choices survey by Mitzenmacher et al.
Sep 19
Hashing to real numbers and applications
Lecture notes 5
Sep 23
Linear programming
Lecture notes on linear programming
Sep 26
Linear programming duality
Sep 30
Provable approximation via linear programming
The design of approximation algorithms by Williamson and Shmoys.
Oct 3
Decision-making under uncertainty 1: dynamic programming and linear programming
Lecture notes 9
Oct 7
Decision-making under uncertainty 2: the multiplicative weight algorithm
Lecture notes on multiplicative weights A survey on multiplicative weights by Arora, Hazan, and Kale.
Oct 10
Applications of the multiplicative weight algorithm
Oct 14
Columbus day, no class
Oct 17
Applications of the multiplicative weight algorithm
Oct 21
High dimensional geometry, dimension reduction
Lecture notes on high dimensional geometry
Oct 24
Locality sensitive hashing and nearest neighbor search
Oct 28
Low rank approximation
Lecture notes on SVD
Oct 31
SVD using power method, spectral clustering
Foundations of data science by Blum, Hopcroft, and Kannan. See chapter 3.
Nov 4
Properties of convex functions, gradient descent
Lecture notes on gradient descent Lectures on modern convex optimization by Ben-Tal and Nemirovski.
Nov 7
Constrained gradient descent
Nov 11
Veterans' day, no class
Nov 14
Online and stochastic gradient descent
Online learning and online convex optimization by Shalev-Shwartz.
Nov 18
Game theory and equilibria
Lecture notes on equilibria Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani.
Nov 21
Coding theory
Lecture notes on coding theory and secured computation Essential coding theory by Guruswami, Rudra, and Sudan.
Nov 25
Secret sharing and secured multiparty computation
A graduate course in applied cryptography by Boneh and Shoup.
The foundations of cryptography by Goldreich.
Nov 28
Dev 2
Intractability: NP-completeness and reductions
Computational complexity: a modern approach by Arora and Barak. See chapter 2.
Dec 5