CMPT 405/705

Design & Analysis of Algorithms - Spring 2019

Announcements

Apr 12: The solutions to quiz 4 are now posted.
Apr 9: I will have office hours between now and the final exam (Apr 18) on Wed and Fri, at 12:30-1:30 pm both days.

older announcements...

Mar 31: The solutions to HW 4 are now posted. Quiz 4 will cover the remaining part of the course, starting from Lecture 22 (Randomized algorithms) to the end of the course.
Mar 28: The solutions to quiz 3 are now posted.
Mar 26: HW 4 is now available (see below).
Mar 14: No lectures on Wed, Mar 20, and Fri, Mar 22 (as I'm away at a conference).
Mar 10: The solutions to HW 3 are now posted.
Mar 3: The solutions to Quiz 2 are now posted.
Mar 2: HW 3 is now posted. Quiz 3 will cover the topics from Lecture 12 to Lecture 20: LP and Coping with NP-hard problems (Chapters 10, 11, and 12 of KT, mainly). You also need to know the definitions of NP and NP-completeness (see Chapter 8), though you will not be asked to prove any problems to be NP-complete.
Feb 24: The solutions to HW 2 are now posted.
Feb 21: Quiz 2 will cover Dynamic Programming and Network Flow topics: Lectures 6 (the DP part) - 11, inclusive. Linear Programming will not be on Quiz 2.
Feb 3: HW 2 is now available.
Jan 26: Quiz 1 will cover the topics from Lectures 1 to 6: BFS/DFS to FFT, inclusive.
Jan 26: The solutions to HW 1 are now posted.
Jan 13: HW 1 is now posted (see below).
Jan 1: The first lecture is on January 4.

Course description

The course continues with the study of concepts and problem-solving techniques useful for the design and analysis of efficient algorithms. The students are assumed to have taken cmpt 307 or its equivalent. After a review of the basic algorithm-design topics (BFS, DFS, greedy, dynamic programming, divide-and-conquer, network flow, NP-completeness), we will study more advanced topics (see below).

Topics
Texts
Lectures
Office hours
Marking scheme

Review of basic algorithmic techniques
Linear programming
Coping with NP-hard problems
Randomized algorithms
Approximation algorithms
Streaming algorithms
Other topics

day	time	room
Mon	14:30-15:20	AQ 3150
Wed	14:30-15:20	AQ 3150
Fri	14:30-15:20	AQ 3150

day	time	room
Wed	12:30-13:20	TASC1 8011
Fri	15:30-16:20	TASC1 8011

Teaching staff

Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011

TA: Alex (alex_sweeten@sfu.ca)

If you have grading-related questions, please email the TA and ask for an appointment. If you still have questions after meeting with the TA, then come and see me.

Important dates

The 50-minute quizzes will be given during our regular lectures on the following dates.

Quiz 1	Quiz 2	Quiz 3	Quiz 4
Feb 1	Mar 1	Mar 18	Apr 8

Final exam: April 18, 12-3 pm, SWH 10041.

Assignments

I'll post homework assignments & solutions.

Lecture notes

I'll post some lecture notes on what I have done in class, and the reading assignment.

01/4: Lecture 1: BFS and DFS for digraphs; Topological sorting of DAGs; Strongly connected components in digraphs. Read: Chap. 22 of CLRS. (Chap. 3 of KT for background)
01/7: Lecture 2: Strongly connected components in digraphs (cont'd); k-Clustering via Kruskal. Read: Chap. 22 of CLRS, and Sec. 4.7 of KT. See also my lecture notes on the correctness analysis of the SCC algorithm. (Read ahead: Sec. 4.8 of KT.)

Slides for lectures 1-2 (SCC Algo and k-Clustering Algo) in the OneNote format and in PDF

01/9: Lecture 3: Huffman coding (algorithm, correctness & runtime analysis); Merge Sort. Read: KT, Secs. 4.8, 5.1, 5.2. (Read ahead: CLRS, Sec. 28.2 and Chap. 30; KT, Secs. 5.5, 5.6.)

Slides for lecture 3 (Huffman coding and Merge Sort) in the OneNote format and in PDF

01/11: Lecture 4: Strassen's matrix multiplication algorithm; FFT algorithm. Read: CLRS, Sec. 28.2, Chap. 30. (Read ahead: CLRS, Chap. 30; KT, Sec. 6.6.)

Slides for lecture 4 in the OneNote format and in PDF

01/14: Lecture 5: FFT algorithm (cont'd).
01/16: Lecture 6: multiplication of two polynomials using FFT. Dynamic Programming: Sequence alignment. Read: CLRS, Chap. 30. KT, Secs. 6.6, 6.7. (Read ahead: KT, Sec. 7.1; CLRS, pages 660-663.)

Slides for lecture 6 (Sequence alignment) in the OneNote format and in PDF

01/18: Lecture 7: Network flows: Ford-Fulkerson algorithm. Read: KT, Secs. 7.1, 7.2; CLRS, pages 660-663. (Read ahead: KT, Secs. 7.5, 7.7-7.11.)

Slides for lecture 7 (Max Flow) in the OneNote format and in PDF

01/21: Lecture 8: Network flows: Max-flow = Min-cut, Correctness of the algorithm Read: KT, Secs. 7.1, 7.2; CLRS, pages 660-663. (Read ahead: KT, Secs. 7.5, 7.7-7.11.)
01/23: Lecture 9: Network flows: Runtime analysis of the Edmonds-Karp implementation (using shortest augmenting paths); Applications of MaxFlow to combinatorial problems (max matchings etc.) Read: KT, Secs. 7.1, 7.2, 7.3, 7.5, 7.6; CLRS, pages 660-663. (Read ahead: KT, Secs. 7.5, 7.7-7.11.)

Slides for lecture 9 (Appllications of the Max Flow algorithm) in the OneNote format and in PDF

01/25: Lecture 10: Applications of MaxFlow to combinatorial problems: Survey design, Airline scheduling. Read: KT, Secs. 7.7-7.11. (Read ahead: CLRS, Chap 29; KT, Chap 8.)
01/28: Lecture 11: Applications of MaxFlow to combinatorial problems: Image segmentation, Project selection. Read: KT, Secs. 7.7-7.11. (Read ahead: CLRS, Chap 29; KT, Chap 8.)
01/30: Lecture 12: Linear programming. Read: CLRS, Chap 29.

Slides for lecture 12 (Linear Porgramming) in the OneNote format and in PDF

02/4: Lecture 13: Linear programming: Simplex algorithm. Read: CLRS, Sec. 29.4 on LP Duality (Chap. 29 on LP). (Read ahead: CLRS, Sec. 29.2; KT, Chap. 8.)
02/6: Lecture 14: LP Duality. Read: CLRS, Sec. 29.4 on LP Duality (Chap. 29 on LP). (Read ahead: CLRS, Sec. 29.2; KT, Chap. 8.)

Slides for lectures 14 (LP Duality) in the OneNote format and in PDF

02/8: Lecture 15: P vs NP. Read: KT, Secs. 8.1-8.4. (Read ahead: KT, Chap. 10.1, 11.6, 11.3, 11.8.)

Slides for lectures 14 (P vs NP) in the OneNote format and in PDF

02/11: Lecture 16: Coping with NP-complete problems. Read: KT, Secs. 10.2, 11.8.

Slides for lectures 16-18 in the OneNote format and in PDF

02/13: Lecture 17: Coping with NP-complete problems (cont'd). Read: KT, Secs. 10.2, 11.8.
02/15: Lecture 18: Exact (exponential-time) algorithms for NP-hard problems. Read: KT, Secs. 10.2, 11.8.
02/25: Lecture 19: Vertex Cover algorithms; Local Search. Read: KT, Chap. 12.

Slides for lectures 19-21 in the OneNote format and in PDF

02/27: Lecture 20: Max-Cut algorithm.
03/4: Lecture 21: Nash Equilibrium for multicasting.
03/6: Lecture 22: Randomized Algorithms: Conflict resolution and Min-Cut.

Slides for lectures 22-25 in the OneNote format and in PDF

03/8: Lecture 23: Randomized Algorithms: Max 3-SAT.
03/11: Lecture 24: Randomized Algorithms: Hash functions.
03/13: Lecture 25: Randomized Algorithms: Chernoff bounds, and load balancing.
03/15: Lecture 26: Randomized Algorithms: QuickSort, and the kth Smallest Element Selection in expected linear time.

Slides for lectures 26-28 in the OneNote format and in PDF

03/25: Lecture 27: Randomized Algorithms: The kth Smallest Element Selection in expected linear time, Polynomial Identity Testing.
03/27: Lecture 28: Randomized Algorithms: Schwartz-Zippel Lemma, Perfect matchings in bipartitite graphs. Derandomizing Randomized Algorithms via Pairwise Independence: Max-2SAT.

Slides for lectures 28-29 in the OneNote format and in PDF

03/29: Lecture 29: Streaming algorithms: Heavy Hitters.

Slides for lectures 29-30 in the OneNote format and in PDF

04/1: Lecture 30: Streaming algorithms: Distinct Elements.

Navigation