ALGORITHM DESIGN

Schedule.

Most of the material we cover in also in the course textbook.
Pointers are given below for topics not in the text.

Week 1.
  • Tuesday January 8th. Introduction: Cryptograpy.
              Related Reading.
              Slides on the RSA encryption by D. Moshkovitz.
  • Thursday January 10th. Network Flows: maxflow-mincut theorem.

    Week 2.
  • Tuesday January 15th. Network Flows: open-pit mining; bipartite matching and vertex cover.
  • Thursday January 17th. Network Flows: flow decomposition theorem; maximum capacity augmenting path algorithm.

    Week 3.
  • Tuesday January 22nd. Network Flows: shortest augmenting path algorithm. [Assignment 1 assigned.]
              Related Reading.
              Slides on the MFMC theorem and the shortest augmenting path algorithm by S. Sarkar.
  • Thursday January 24th. Linear Programming: Standard form; Weak duality.

    Week 4.
  • Tuesday January 29th. Linear Programming: Applications of linear programming and duality. [Assignment 1 due.]
              Related Reading.
              Our presentation of linear programming and the simplex algorithm is based upon the book Linear Programming by V. Chvatal (see Chapters 1-5).
              An introduction to linear programming, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, can also be found here.
  • Thursday January 31st. Linear Programming: The Simplex Algorithm; Geometry of LPs.
              Related Reading.
              Slides of the Lecture.

    Week 5.
  • Tuesday February 5th. Linear Programming: Bland's Rule; the Two-Phase Simplex Method; the Ellipsoid Method. [Assignment 2 assigned.]
              Related Reading.
              Slides of the Lecture.
  • Thursday February 7th. Linear Programming: Strong duality; Complementary slackness.
              Related Reading.
              Slides of the Lecture.

    Week 6.
  • Tuesday February 12th. NP: Reductions. [Assignment 2 due.]
  • Thursday February 14th. NP: NP-completeness.

    Week 7.
  • Tuesday February 19th. NP: co-NP; good characterizations. [Assignment 3 assigned.]
  • Thursday February 21st. NP: Non-deterministic algorithms; proof of Cook's Theorem.

    Week 8.
  • Tuesday February 26th. Midterm Exam. [Assignment 3 due.]
  • Thursday February 28th. Backtracking: Hamiltonian Cycle; Satisfiability.           Related Reading.
              An introduction to backtracking, by S. Dasgupta, C. Papadimitriou and U. Vazirani (Section 9.1.1).

    Week 9. Spring Break - No Lectures.

    Week 10.
  • Tuesday March 12th. Branch and Bound: Knapsack; TSP. [Assignment 4 assigned.]           Related Reading.
              An introduction to branch and bound, by S. Dasgupta, C. Papadimitriou and U. Vazirani (Section 9.1.2).
  • Thursday March 14nd. Local Search; Simulated Annealing.
              Related Reading.
              An introduction to local search, by S. Dasgupta, C. Papadimitriou and U. Vazirani (Section 9.3).

    Week 11.
  • Tuesday March 19th. Approximation Algorithms: Vertex Cover; the Travelling Salesman Problem.
  • Thursday March 21st. Approximation Algorithms: Centre Selection. [Assignment 4 due.]

    Week 12.
  • Tuesday March 26th. Approximation Algorithms: Set Cover; the Knapsack Problem. [Assignment 5 assigned.]
  • Thursday March 28th. Approximation Algorithms: Multiway-Cut; Disjoint Paths Problem.

    Week 13.
  • Tuesday April 2nd. Randomised Algorithms: [Assignment 5 due.]
  • Thursday April 4th. Randomised Algorithms: [Assignment 6 assigned.]

    Week 14.
  • Tuesday April 9th. Simulated Annealing:
  • Thursday April 11th. PSPACE: [Assignment 6 due.]

    Week 17.
  • Tuesday April 30th. Final Exam (Tentative)