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 September 2nd. Introduction: Cryptograpy.
              Related Reading.
              Slides on the RSA encryption by D. Moshkovitz.
  • Thursday September 4th. Network Flows: maxflow-mincut theorem.

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

    Week 3.
  • Tuesday September 16th. 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 September 18th. Linear Programming: Standard form; Weak duality.
              Related Reading.
              For notes on linear programming see Chapter 26 of Jeff Erickson's book.

    Week 4.
  • Tuesday September 23rd. 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).
  • Thursday September 25th. Linear Programming: The Simplex Algorithm; Geometry of LPs.
              Related Reading.
              Slides of the Lecture.

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

    Week 6.
  • Tuesday October 7th. NP: Reductions. [Assignment 2 due.]
  • Thursday October 9th. NP: NP-completeness.

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

    Week 8.
  • Tuesday October 21st. Midterm Exam.
  • Thursday October 23rd. Backtracking: Hamiltonian Cycle; Satisfiability. [Assignment 3 due.]
              Related Reading.
              An introduction to to backtracking can be found in Section 9.1.1 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani.
              See also Section 12.1 of the book Introduction to the Design and Analysis of Algorithms by A. Levitin.
              More notes on backtracking can be found in Chapter 3 of Jeff Erickson's book.

    Week 9.
  • Tuesday October 28th. Branch and Bound: Knapsack; TSP. [Assignment 4 assigned.]
              Related Reading.
              An introduction to to branch and bound can be found in Section 9.1.2 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani.
              See also Section 12.2 of the book Introduction to the Design and Analysis of Algorithms by A. Levitin.
  • Thursday October 30th. Local Search; Simulated Annealing.
              Related Reading.
              Local Search is covered in Chapter 12 of the course text.
              An introduction to to local search can also be found in Section 9.3 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani.

    Week 10.
  • Tuesday November 4th. Approximation Algorithms: Vertex Cover; the Travelling Salesman Problem.
              Related Reading.
              See Sections 11.1 and 11.6 of the course text.
  • Thursday November 6th. Approximation Algorithms: Set Cover; Multiway-Cut. [Assignment 4 due.]
              Related Reading.
              See Sections 11.3 of the course text.

    Week 11.
  • Tuesday November 11th. Approximation Algorithms: Centre Selection; the Knapsack Problem. [Assignment 5 assigned.]
              Related Reading.
              See Sections 11.2 and 11.8 of the course text.
  • Thursday November 13th. Approximation Algorithms: the Steiner Tree Problem; the Disjoint Paths Problem.
              Related Reading.
              See Sections 11.5 of the course text.

    Week 12.
  • Tuesday November 18th. Parameterized Complexity: Vertex Cover; Longest Path.
              Related Reading.
              See Sections 10.1-10.2 of the course text.
  • Thursday November 20th. Randomised Algorithms: Minimum Cut. [Assignment 5 due.] [Assignment 6 assigned.]
              Related Reading.
              See Section 13.2 of the course text.


    Week 13.
  • Tuesday November 25th.Complexity: PSPACE; EXP.
              Related Reading.
              See Chapter 9 of the course text.
  • Thursday November 27th. Application: Bandwidth Auctions.

    Week 14.
  • Tuesday December 2nd. Last Lecture. [Assignment 6 due.]

    Week 16.
  • Wednesday December 17th. Final Exam. (6pm)