Advanced Algorithms (Fall 2014)

Shay Mozes

Lectures (including video)

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.

Infrastructure for this site and for making the videos available was generously provided by Erik Demaine.
For more information about the process and setup see this guide by Erik Demaine and Martin Demaine.