Advanced Algorithms (Fall 2016)

Shay Mozes

Lectures (including video)

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.

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.