CSC 484/284 Advanced Algorithms - Fall 2024

Course info:

Class:
 Mon/Wed 4:50-6:05pm, Dewey Room 2110D
Instructor:
 Kaave Hosseini    Email: kaave.hosseini@rochester.edu
Office hours:
 TBD
TA:
 Zahra Hadizadeh    Email: zhadizad@ur.rochester.edu




Course Description:

This course is an overview of modern algorithmic techniques, based on a variety of analytic, algebraic, and combinatorial ideas.



Evaluation:

is based on homework assignments, class attendance, and a final project.



image
The book al-Jabr (Algebra) by the 8-9th century polymath al-Khwarizmi. The latinization of his name evolved to the term "algorithm".

Topics:

Part 1: Oblivious randomized algorithms

  • Deviation Bounds

  • Hashing

  • Max-Cut

  • Finding Large Primes

  • Polynomial Identity Testing

  • Verifying matrix multiplication

  • Dimensionality reduction and the Johnsson-Lindenstrauss lemma

Part 2: Adaptive randomized algorithms

  • Min-Cut and clustering

  • Singular Value Decomposition

  • Expanders and applications

  • Satisfiability

  • Multiplicative weight updates

  • Linear and Semidefinite programming

  • Max-Flow Min-Cut

Part 3: Algebraic Algorithms

  • Fast Fourier Transform

  • Secret Sharing

  • Explicit algebraic constructions

Resources:

Here are some resources that we will use.
[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