Modern Algorithms, Fall 2019
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.
Instructors: Sina Dehghani, Omid Etesami
Lectures: Wednesdays 9:00-10:30, 11:00-12:13
- 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:
- 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
- Week 4:
- Week 5:
- Week 6:
- Gradient Descent, Mirror Descent, and Accelerated Gradient Descent [lecture notes]
- Week 7:
- Week 8:
- Week 9:
- Week 10:
- Week 11:
- Week 12:
- Week 13:
- Week 14:
- Assignment 1
- Assignment 2
- Assignment 3
- Assignments (40%)
- Midterm exam (25%)
- Final Exam (35%)