| L01 | Nov. 6 | [+] Introduction and stable matching |
[Slides] | [Video] |
|---|---|---|---|---|
| Overview of the class. A quick review of material students should be very comfortable with. The second half of the lecture is devoted to the stable matching problem, as an example for the way we theoretically tackle a real life problem from various aspects. | ||||
| L02 | Nov. 13 | [+] Divide and Conquer |
[Slides] | [Video] |
| In this lecture we study various examples for divide and conquer algorithms. We recall the master theorem for bounding recurrence relations. | ||||
| L03 | Nov. 20 | [+] NP Completeness and Approximation algorithms |
[Slides] | [Video] |
| In this lecture we review NP-completness and start discussing approximation algorithms. | ||||
| L04 | Nov. 27 | [+] Approximation Algorithms |
[Slides] | [Video] |
| In this lecture we continue our discussion of approximation algorithms. We present approximation algorithms for Euclidean TSP and Bin-Packing, and start working towards a polynomial-time approximation scheme (PTAS) for Knapsack. | ||||
| L05 | Dec. 4 | [+] Polynomial time approximation shchemes, and Solving hard problems on structured instances |
[Slides] | [Video] |
| We discuss a polynomial time approximation scheme (PTAS) for the knapsack problem. We then discuss problems that are NP-Hard, but can be solved efficiently if we assume the input is restricted in some way. Examples include minimum independent set on trees using greedy and dynamic programming algorithms, the partition problem on powers of two, facility location problems on trees, and maximum independent set on interval graphs. | ||||
| L06 | Dec. 11 | [+] Solving hard problems - structured inputs and Treewidth |
[Slides] | [Video] |
| We continue the discussion of NP-Hard problems that can be solved efficiently if we assume the input is restricted in some way. We discuss facility location on trees, partition on powers of two, interval graphs, mention other graph families, and move on to define treewidth. | ||||
| L07 | Dec. 18 | [+] Parametrized complexity |
[Slides] | [Video] |
| We introduce the concepts of parameterized complexity and fixed parameter tractability (FPT). We discuss kernelization and branching - two approached for designing FPT algorithms. We finish the discussion of parameterized complexity by considering alternative parameters. | ||||
| L08 | Jan. 1 | [+] Linear programming |
[Slides] | [Video] |
| We discuss linear programming, convex polyhedra and the simplex method. We then start discussing integer linear programming. | ||||
| L09 | Jan. 8 | [+] Integer Linear programming, LP duality and a bit of Randomized algorithms |
[Slides] | [Video] |
| We discuss approximation algorithms for linear integer programs that use optimal solutions to the relaxation LP problem. We then introduce LP duality, and show an approximation algorithm based on the concept of complementary slackness. In the seconf half of the lecture we start discussing randomized algorithms. | ||||
| L10 | Jan. 15 | [+] Randomized algorithms |
[Slides] | [Video] |
| In this lecture we discuss randomized algorithms. We discuss a few examples for the use of randomization in sampling (calculating the value of pi), the selection probelm, skip lists, random walks, and finding the minimum cut in a graph. | ||||
| L11 | Jan. 22 | [+] Online algorithms |
[Slides] | [Video] |
| We dicuss online algorithms and competitive analysis. Examples covered include the ski rental problem, scheduling, paging, and bin packing. | ||||
| L12 | Jan. 29 | [+] Sublinear algorithms and course wrap-up |
[Slides] | [Video] |
| We discuss algorithm for situations where the available memory or time are sublinear in the input length. We discuss the streaming model, property testing and sublinear time algorithms. We then reflect on what we've learned during this semester and discuss the exam. | ||||