In the undergrad algorithm courses we are usually faced with classical problems such as max flow or maximum matching. The algorithms for these types of problems are mostly efficient, exact, and based on some cute combinatorial observation or proof.

However, more recent algorithms deal with a wider variety of problems. In these problems, it is tried that the models be more realistic and based on real world applications, though with the cost of sometimes having more complex algorithms. The algorithms also use a larger set of tools and techniques, such as continuous mathematics, linear algebra, and probabilistic methods. This course introduces beautiful and powerful techniques of theoretical computer science for the design of algorithms in recent years.

This course is highly inspired by the course CS270 in Berkeley.

- Assignment 3 is up and its due date is Jan 25.

- Assignment 2 is up and its due date is Jan 1.

- Assignment 1 is up and its due date is Oct 28.

- Classes are held in Lecture Hall 1.

- Week 1:
- Introduction, review of basic Primal Dual and Gradient Descent methods in Path Routing and Tolling problems [lecture notes]

- Week 2:
- Introduction to game theory [lecture notes]
- Maximum weighted matching [lecture notes]

- Week 3:
- Multiplicative weight update and strong duality [lecture notes]
- Adaboost, Path Routing and Tolling reconsidered [you may see the previous lecture notes and a nice survey here]

- Week 4:
- Linear Programming and Complementary Slackness [lecture notes]
- Facility Location [lecture notes]

- Week 5:
- Semidefinite Programming and Max cut [lecture notes]
- Strong duality

- Week 6:
- Gradient Descent, Mirror Descent, and Accelerated Gradient Descent [lecture notes]

- Week 7:
- Perceptron and SVM [lecture notes]
- Online algorithms [lecture notes]

- Week 8:
- Online algorithms (continued) [lecture notes]
- Computational concentration of measure [slides]

- Week 9:
- Probabilistic embedding of metrics to spaces and hierarchial seperated tree (HST) [lecture notes]
- Linear Time Linear Solvers [Satish Rao's slides]

- Week 10:
- Streaming algorithms

- Week 11:
- Power of two choices and Cuckoo hashing [Satish Rao's slides]
- Johnson-Lindenstrauss lemma [Satish Rao's slides]

- Week 12:
- Cheeger's inequality [Satish Rao's slides part 1 , part 2]

- Week 13:
- Sampling [Satish Rao's notes]
- Principal component analysis (PCA) [Satish Rao's slides]

- Week 14:
- Fixed points and Nash's theorem [lecture notes]

- Assignments (40%)
- Midterm exam (25%)
- Final Exam (35%)