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

Algorithm Design by J. Kleinberg and E. Tardos, 2006 [main]
Introduction to Algorithms by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2001 [optional]

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

or email me for an appointment.

four 50-min in-class quizzes @ 15% each,
final exam @ 40%.

Note: I will post 4 homework assignments (one before each quiz), which will not be collected and graded. The solutions to homework problems will be posted before the quiz. The quizzes will be loosely based on the homework problems, so you will benefit by solving the homework problems by yourself!

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