CSE 291 - Advanced techniques in algorithm design (Spring 2016)
Time: Tuesdays & Thursdays 3:30-4:50
Room: CSE (EBU3B) 2154
Instructor: Shachar Lovett, email: slovett@ucsd.edu
Office hours: Thursdays 5-7pm, CSE 4234
TA: Kaave Hosseini, email: skhossei@ucsd.edu
Office hours: Mondays 3-5pm, CSE 4232
Overview
The class will focus on two themes: linear algebra and probability, and their many applications in algorithm design. We will cover a number of classical examples, including: fast matrix multiplication, FFT, error correcting codes, cryptography, efficient data structures, combinatorial optimization, routing, and more. We assume basic familiarity (undergraduate level) with linear algebra, probability, discrete mathematics and graph theory.
Grading: Homework and take-home exam.
Homework can be done individually or in pairs. Please write your solutions in latex/word, save as pdf, and email to Kaave (skhossei@ucsd.edu) by the due date.
We will follow the class notes.
Topics
- Mathematical review: linear algebra, finite fields, polynomials, probability theory
- Fast matrix multiplication, verifying matrix multiplication, finding triangles in graphs
- The Fast Fourier Transform (FFT), fast polynomial multiplication
- Secret sharing schemes
- Introduction to error correcting codes, basic bounds for codes
- Reed-Solomon codes, Berlekamp-Welch algorithm for decoding
- Polynomial identity testing, finding perfect matchings in graphs
- Solving satisfiability via random walks
- Pairwise independent hash functions and applications
- Cuts in graphs: randomized algorithms for computing min-cut and approximating max-cut
- Random routing
- Expander graphs, expander mixing lemma, applications
Related material
- Randomized algorithms, by Motwani and Raghavan [Amazon]
- Pairwise independence and its applications, by Luby and Wigderson [download]
- Expander graphs and their applications, by Hoory, Linial and Wigderson [download]
- Survey on fast matrix multiplication, by Filmus [download part 1] [download part 2]