Course info:
|
|
Class: |
TTh 12:30-1:45pm,
Hylan Room 203 |
Instructor: |
Kaave Hosseini
Email:
kaave.hosseini (rochester.edu) |
Office hours: |
T 2:00-3:00pm, Wegmans 2507 |
Course material:
Course Description:
This course is an overview of modern algorithmic techniques, with a focus on randomized, approximation, and algebraic algorithms. | | |
Evaluation:
is based on five homework assignments and class attendance. | | |
al-Jabr by al-Khwarizmi;
Algebra by Algorithm
Topics:
Part 1: Oblivious randomized algorithms; randomly pick and hope for the best.
Deviation Bounds
Ball in Bins and Load Balancing
Hashing
Estimate the Size of a Set and applications in Streaming
Set Membership tests and Bloom filters
Routing
Finding Large Primes
Polynomial Identity Testing and Finding Perfect Matchings
Dimensionality reduction
Part 2: Adaptive randomized algorithms; gradually improve by taking random steps.
Min-Cut and clustering
Singular Value Decomposition, Low Rank approximation, Max-Cut, Power Method
Expanders, Random walks on graphs, Mixing of Markov Chains, Error reduction of randomized algorithms
Counting, Sampling, and Markov Chain Monte Carlo Methods
Sparsest cut, Cheeger's inequality, and Spectral Clustering
Satisfiability
Entropy compression and Satisfiability
Linear and Semidefinite programming
Gradient descent, Ellipsoid algorithm, Interior methods
Experts and multiplicative weight update
Duality: LP duality, Max-Flow Min-Cut, Minmax theorem
Part 3: Algebraic Algorithms
Matrix Multiplication
Fast Fourier Transform
Fast polynomial multiplication
Construction of good hash functions
Error Correcting Codes
Secret Sharing
Resources:
We will use a number of different resources. Here are some fantastic lecture notes from a similar courses taught at other institutions that we will heavily draw from.
[A15] |
|
Advanced Algorithm Design by Sanjeev Arora (Princeton) |
[KM18] |
|
Advanced Algorithm Design by Pravesh Kothari, Christopher Musco (Princeton) |
[O20] |
|
Design and Analysis of Algorithms by Shayan Oveis-Gharan (U of Washington) |
[L16] |
|
Advanced techniques in algorithm design by Shachar Lovett (UC San Diego) |
[G20] |
|
by Anupam Gupta (CMU) |
[T11] |
|
Combinatorial Optimization by Luca Trevisan (Stanford) |
[GK12] |
|
Computer Science Theory for the Information Age by Venkatesan Guruswami and Ravi Kannan (CMU) |
[MR] |
|
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan |
[MU] |
|
Probability and Computing by Michael Mitzenmacher and Eli Upfal |
[BHK] |
|
Foundations of Data Science by Avrim Blum, John Hopcroft, and Ravi Kannan |
[KV] |
|
Spectral Algorithms by Ravi Kannan and Santosh Vempala |