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

Grading: Homework and take-home exam

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


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.


Related material