COMP 360: Algorithm Design
Winter 2015
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 9: Reading Week
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: