Navigation

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.