CSC 484/284 Advanced Algorithms - Fall 2023

Course info:

Course syllabus
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:

are posted on Slack.


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.



image
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]

Lecture Notes:

Advanced Algorithm Design by Sanjeev Arora (Princeton)

[KM18]

Lecture Notes:

Advanced Algorithm Design by Pravesh Kothari, Christopher Musco (Princeton)

[O20]

Lecture Notes:

Design and Analysis of Algorithms by Shayan Oveis-Gharan (U of Washington)

[L16]

Lecture Notes:

Advanced techniques in algorithm design by Shachar Lovett (UC San Diego)

[G20]

Book Draft:

by Anupam Gupta (CMU)

[T11]

Book Draft:

Combinatorial Optimization by Luca Trevisan (Stanford)

[GK12]

Lecture notes:

Computer Science Theory for the Information Age by Venkatesan Guruswami and Ravi Kannan (CMU)

[MR]

Book:

Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan

[MU]

Book:

Probability and Computing by Michael Mitzenmacher and Eli Upfal

[BHK]

Book:

Foundations of Data Science by Avrim Blum, John Hopcroft, and Ravi Kannan

[KV]

Book:

Spectral Algorithms by Ravi Kannan and Santosh Vempala