Tuesday/Thursday, Seigle 301 10-11:30 am Instructor: Brendan Juba Teaching assistants: Kris Nilsson, Charles Troutman, Yimu Liu, Haixin Zhou 3 credits
This course provides an overview of techniques for the design and analysis of algorithms for the kinds of problems that you are likely to encounter at the graduate level. The contrast with undergraduate algorithms is as follows: whereas at the undergraduate level we focused on the standard paradigms for obtaining optimal worst-case solutions to problems, such solutions are intractable for nearly all of the problems we will consider. We will draw on techniques from continuous optimization, linear algebra, and probability to develop a collection of approaches that yield fast algorithms for approximate solutions for a wide variety of problems. We will also consider a variety of problem settings, including on-line and streaming settings. As in undergraduate algorithms, our goal is still to understand why the methods work and how to quantify their efficiency.
Because algorithms and their analysis can be subtle, trying to understand their behavior based solely on informal arguments (sometimes called "hand-waving") is fraught with peril. The safest way to avoid being wrong is to pursue rigorous correctness and efficiency arguments (i.e. proofs). We will strive for mathematically rigorous argument, both in class and on your assignments. An important part of learning about algorithms is learning how to argue rigorously about their behavior; this will enable you to understand precisely why they work, and therefore in what ways the algorithms can or cannot be extended or modified to solve variations of the original task or meet other criteria. After successfully completing this class, you should be able to understand and rigorously analyze a wide variety of algorithms encountered in graduate study.
Formally, this class requires CSE 3407, Analysis of Algorithms as well as basic linear algebra. We will briefly review the main paradigms of worst-case optimal polynomial-time algorithms, greedy and dynamic programming, as well as the theory of intractability from CSE 3407, but we expect some prior familiarity with these topics. We will recall the main results of linear algebra (e.g., eigenvectors/eigenvalues) and tools from probability (tail inequalities) but we will utilize these extensively. We also expect that you can make arguments in support of algorithmic correctness and complexity.
Informally, CSE 5401 demands "mathematical maturity" -- the ability to read, understand, and produce rigorous mathematical arguments (i.e. proofs). We will use basic logical techniques such as induction, proof by contradiction, and proof by cases extensively, as well as tools from probability, linear algebra, optimization, and combinatorics. You will practice communicating your ideas in the form of proofs through your classroom interactions and homework assignments.
There is no required textbook for the course, but the following references may be helpful.
The breakdown of your final grade will be as follows:
Any curving of exams to adjust for observed difficulty is at the sole discretion of the instructors. We do not anticipate curving homework grades, and we will not drop exam scores.
| Lecture no. | Topic | Dates | Homework |
| Lec. 1 | Greedy Algorithms (review) Minimum Spanning Tree | 8/26 | |
| Lec. 2 | Dynamic Programming and PTAS Knapsack Williamson and Shmoys, Section 3.1 notes | 8/28 | Assigned: Homework 1 |
| Lec. 3 | Intractability (NP completeness review) notes | 9/2 | |
| Lec. 4 |
Hashing and the power of two choices
Mitzenmacher & Upfal second edition Chapter 15, sections 15.1-15.3 (pairwise independence) Section 17.1 (power of two choices) notes |
9/4 |
Due:
Homework 1 Assigned: Homework 2 |
| Lec. 5 |
Multiplicative weights
Blum, Hopcroft, and Kannan, Section 5.10.6 (The problem is called "experts learning" there.) notes |
9/9 | |
| Lec. 6 |
Markov chains Mitzenmacher & Upfal, Chapter 7 notes |
9/11 |
Due:
Homework 2 Assigned: Homework 3 |
| Lec. 7 |
Games
Blum, Hopcroft, and Kannan, Section 5.11 (Near the end of "Boosting".) notes |
9/16 | |
| Lec. 8 |
Sparse cuts and conductance An alternative to Cheeger's inequality: Blum, Hopcroft, and Kannan directly bound the mixing time in terms of the conductance in Section 4.4 notes |
9/18 |
Due:
Homework 3 Assigned: Homework 4 |
| Lec. 9 |
Gradient descent
Blum, Hopcroft, Kannan, Section 10.5 (only covers the first part of lecture) notes |
9/23 | |
| Lec. 10 |
Streaming algorithms Blum, Hopcroft, Kannan Sections 6.2.1 and 6.2.3 notes |
9/18 |
Due:
Homework 4 |
| Lec. 11 |
Equivalence of counting and sampling
Mitzenmacher and Upfal Section 11.3
(presented in terms of counting independent sets) notes |
9/30 | |
| Exam 1 | Midterm Exam 1(in class) | 10/2 | |
| Lec. 12 |
Solving convex programs with separation oracles using Ellipsoid Blum, Hopcroft, Kannan, Section 10.6.1 The separation oracle framework is also discussed in Williamson and Shmoys, Section 4.3 notes |
10/9 |
Assigned:
Homework 5 |
| Lec. 13 |
Coupling for sampling colorings Mitzenmacher and Upfal, Section 12.2 (Example: section 12.2.2) and 12.5 (Theorem 12.7) notes |
10/14 | |
| Lec. 14 |
Linear Program Duality Williamson and Shmoys, Appendix A notes |
10/16 |
Due:
Homework 5 Assigned: Homework 6 |
| Lec. 15 |
Dimensionality reduction
Blum, Hopcroft, and Kannan, Section 2.7 (Gaussian version) notes |
10/21 | |
| Lec. 16 |
Semidefinite programming Williamson and Shmoys, Section 6.1 (also see Chapter 6 Chapter Notes for discussion of the algorithms for solving semidefinite programs) Blum, Hopcroft, and Kannan, Section 10.8 notes |
10/23 |
Due:
Homework 6 Assigned: Homework 7 |
| Lec. 17 |
Primal-dual algorithms
Williamson and Shmoys Sections 7.1-7.2 notes |
10/28 | |
| Lec. 18 |
Path coupling for counting independent sets Mitzenmacher and Upfal, Section 12.6 notes |
10/30 |
Due:
Homework 7 Assigned: Homework 8 |
| Lec. 19 | On-line algorithms via primal-dual notes | 11/4 | |
| Lec. 20 |
Randomized rounding of semidefinite programs Williamson and Shmoys, Sections 6.2 and 6.3 (also briefly described in Blum, Hopcroft, and Kannan, Section 10.8) notes |
11/6 |
Due:
Homework 8 Assigned: Homework 9 |
| Lec. 21 |
Smoothed analysis of k-means
The k-means objective and Lloyd's algorithm are discussed in Blum, Hopcroft, and Kannan Section 7.2 (but not the smoothed analysis) notes |
11/11 | |
| Lec. 22 |
Primal-dual algorithm for Steiner Forest Williamson and Shmoys, Section 7.4 notes |
11/13 |
Due:
Homework 9 |
| Lec. 23 |
Randomized rounding for coloring
Williamson and Shmoys Section 6.5 notes |
11/18 | |
| Exam 2 | Midterm Exam 2(in class) | 11/20 |
Assigned:
Homework 10 |
| Lec. 24 |
Locality-sensitive hashing notes |
12/2 | |
| Lec. 25 |
Course summary notes |
12/4 |
Due:
Homework 10 |