COMP 360: Algorithm Design

Course Information

• Instructor: Yang Cai
Office Hours: Wednesday 3:00 pm - 4:30 pm, MC 324.

• TA: Xiangyu Ren and Liana Yepremyan
Office Hours: (This Week) Tuesday 4:00 pm - 5:30 pm by Xiangyu Ren, MC 229;
Friday 11:00 am - 12:30 am by Liana Yepremyan, MC 303.

• Lecture: Mondays and Wednesdays 1:05 pm-2:25 pm, Macdonald Engineering Building 280.

• Course Description: Advanced algorithmic techniques and applications. The outline of the course can be found here.

• Textbook: Algorithm Design, by Jon Kleinberg and Eva Tardos.

• Prerequisites: Comp 251 and one of Math 240/Math 235/Math 363.

• Assessment: The grade comprises the following components:
• 25% from homework problems: there will be 5 problem sets. See Lecture 1's slides for the collaboration policy.
• 25% from the midterm exam (Feb. 25th in class).
• 50% from the final exam.

Lectures

Week 1

• Lecture 1 (Jan 5th): Course Administrivia. Introduction: Cryptography. Slides Dana Moshkovitz's slides on the RSA encryption.
• Lecture 2 (Jan 7th): Network Flows. Ford-Fulkerson Algorithm. Residual Graph. Augmenting Path. Cuts. | Related Reading: Textbook Chapter 7.1.
• Week 2

• Lecture 3 (Jan 12th): Max Flow Min Cut Theorem. Application: Open Pit Mining. | Related Reading: Textbook Chapter 7.2, 7.11.
• Lecture 4 (Jan 14th): Bipartite Matching. Pseudopolynomial Time. Flow Decomposition Theorem. Max Capacity Augmenting Path Algorithm. | Related Reading: Textbook Chapter 7.5, 7.3, Chapter 23.6.1 in Erikson's Notes.
• Week 3

• Lecture 5 (Jan 19th): Max Capacity Augmenting Path Algorithm (cont'd). | Related Reading: Chapter 23.6.1 in Erikson's Notes.
• Lecture 6 (Jan 21st): Shortest Augmenting Path Algorithm. | Related Reading: Chapter 23.6.2 in Erikson's Notes.
• Week 4

• Lecture 7 (Jan 26th): Linear Programming: Applications and Duality (Weak). | Related Reading: Our presentation of LP is based upon the book Linear Programming by V. Chvatal (see Chapters 1-5).
• Lecture 8 (Jan 28th): The Simplex Algortihm. | Related Reading: Slides of this Lecture.
• Week 5

• Lecture 9 (Feb 2nd): The Simplex Algorithm: Termination and Initialization , The Ellipsoid Method. | Related Reading: Slides of this Lecture; Michel Goemans's Notes on the Ellipsoid Method
• Lecture 10 (Feb 4th): Applications of LP. Minmax Theorem for 2-player Zero-sum Games | Related Reading: Chapter 26.2, 26.3
• Week 6

• Lecture 11 (Feb 9th): Minmax Theorem (cont'd). Strong Duality. Complementary Slackness | Related Reading: Slides of this Lecture
• Lecture 12 (Feb 11th): Polynomial-Time Reduction. Examples of Reductions | Related Reading: Textbook Chapter 8.1, 8.2.
• Week 7

• Lecture 13 (Feb 16th): NP, NP-Completeness | Related Reading: Textbook Chapter 8.3, 8.4.
• Lecture 14 (Feb 19th): co-NP; good characterizations. | Related Reading: Textbook Chapter 8.9, 8.10.
• Week 8

• Lecture 15 (Feb 23th): Backtracking: Hamiltonian Cycle; Satisfiability | Related Reading: Section 9.1.1 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani; Chapter 3 of Jeff Erickson's book.
• Midterm (Feb 25th).

Week 10

• Lecture 16 (Mar 9nd): Branch and Bound: Knapsack; TSP | Related Reading: Section 9.1.2 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani; Section 12.2 of the book Introduction to the Design and Analysis of Algorithms by A. Levitin.
• Lecture 17 (Mar 11th): Local Search. Simulated Annealing | Related Reading: Chapter 12 of the course text; Section 9.3 of the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani.
• Week 11

• Lecture 18 (Mar 16th): Approximation Algorithms: Vertex Cover; the Travelling Salesman Problem | Related Reading: See Sections 11.1 and 11.6 of the course text.
• Lecture 19 (Mar 18th): Approximation Algorithms: Set Cover; Multiway-Cut | Related Reading: See Sections 11.3 of the course text.
• Week 12

• Lecture 20 (Mar 23th): Approximation Algorithms: Multiway-Cut (cont'd), Centre Selection| Related Reading: See Sections 11.2 of the course text.
• Lecture 21 (Mar 25th): Approximation Algorithms: the Knapsack Problem, (F)PTAS, the Steiner Tree Problem | Related Reading: See Sections 11.8 of the course text.
• Week 13

• Lecture 22 (Mar 30th): Online Algorithms: Competitive Ratio, Ski-rental, Online Caching/Paging | Related Reading: Debmalya Panigrahi's Notes, Shuchi Chawla's Notes.
• Lecture 23 (Apr 1st): Randomized Algorithms: Minimum Cut | Related Reading: See Sections 13.2 of the course text.

Online Resources

Previous incarnation of this class:
Other reference: