| L01 | Oct. 26 | [+] 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. 2 | [+] 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. 9 | [+] NP Completeness and Approximation algorithms |
[Slides] | [Video] |
| In this lecture we review NP-completness and start discussing approximation algorithms. | ||||
| L04 | Nov. 16 | [+] Approximation Algorithms |
[Slides] | [Video] |
| In this lecture we continue our discussion of approximation algorithms. We present algorithms for Euclidean TSP and Bin-Packing, and a polynomial-time approximation scheme (PTAS) for Knapsack. We also briefly discuss the PCP theorem and hardness of approximations. | ||||
| L05 | Nov. 23 | [+] Solving hard problems on structured instances |
[Slides] | [Video] |
| We 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 | Nov. 30 | [+] Solving hard problems - Treewidth and Parametrized complexity |
[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 interval graphs, mention other graph families, and move on to define treewidth. Finally we introduc the concepts of parameterized complexity and fixed parameter tractability (FPT). We discuss kernelization and branching - two approached for designing FPT algorithms. | ||||
| L07 | Dec. 7 | [+] Parametrized complexity wrap-up and Linear programming |
[Slides] | [Video] |
| We finish the discussion of parameterized complexity by considering alternative parameters. Then we start discussing linear programming. | ||||
| L08 | Dec. 14 | [+] Linear programming |
[Slides] | [Video] |
| We first discuss poblem set 2. Then we return to linear programming and present the simplex algorithm. After a couple of examples we introduce the integer linear programs (ILP), which are NP-hard problems. We discuss solving ILPs using the branch and bound heuristic, and introduce the concept of an LP relaxation of an ILP. | ||||
| L09 | Dec. 28 | [+] 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, show that the max-flow min-cut theorem can be obtained using LP duality, and show an approximation algorithm based on the concept of complementary slackness. In the last few minutes we start discussing randomized algorithms. | ||||
| L10 | Jan. 4 | [+] Randomized algorithms |
[Slides] | [Video] |
| In this lecture we discuss randomized algorithms. We give a brief review of basic probabiliy theory, inculding the Markov and Chernoff bounds. 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. 11 | [+] Primality testing and online algorithms |
[Slides] | [Video] |
| We finish the discussion of randomizes algorithm by considering the primality testing problem. Then we begin dicussing online algorithms and competitive analysis. | ||||
| L12 | Jan. 18 | [+] Online algorithms and course wrap-up |
[Slides] | [Video] |
| We conclude the discussion of online algorithms - paging, bin backing and investing in the stock market. We then reflect on what we've learned during this semester and discuss the exam. | ||||