CSE 190 - Great Ideas in Algorithms

Class: Tuesdays & Thursdays 11-12:20, CSE (EBU3B) 2154

Instructor: Shachar Lovett, email: slovett@ucsd.edu
Office hours: Thursdays after class (12:30-2pm), CSE 4234

TA: Jiapeng Zhang, email: jpeng.zhang@gmail.com
Office hours: Fridays 2-3p, CSE 4232

Homework (can solve in pairs):
Problem set 1, due April 21
Problem set 2, due May 5
Problem set 3, due May 28

Overview

The class will focus on two key themes, which have proven to be extremely powerful in several areas of computer science. The first is algebraic techniques. We will see many interesting and often surprising applications of linear algebra and polynomials in coding theory, cryptography, combinatorics, and algorithm design. We will develop all the algebraic tools that we need along the way. The second is the use of randomness in computation. We will explore both the power of randomized algorithms, and also of ways to eliminate or reduce randomness in algorithms. We will see applications in graph theory, data structures and complexity theory.

No specific background is necessary. However, it might be helpful to have some familiarity with discrete math/algorithms and linear algebra. The only real prerequisite is some mathematical maturity. Students with an interest in discrete mathematics and/or theoretical computer science are welcome.

Topics

• Mathematical review: linear algebra, finite fields, polynomials, probabiliy theory (throughout the class)
• Fast matrix multiplication (Strassen), verifying matrix multiplication, finding triangles in graphs [notes]
• Fast polynomial multiplication and FFT [notes]
• Secret sharing scheme [notes]
• Introduction to error correcting codes, basic bounds for codes [notes]
• Reed-Solomon codes, Berlekamp-Welch algorithm for decoding [notes]
• Polynomial identity testing, Schwarz-Zippel Lemma, finding perfect matchings in graphs [notes]
• Solving satisfiability via random walks [notes]
• Pairwise independent hash functions and applications [notes]
• Karger's min-cut algorithm [notes]
• Randomized routing [notes]
• Expander graphs [notes]

Related material

• Randomized algorithms book, by Motwani and Raghavan