CMPT 705 - Design and Analysis of Algorithms - Fall'16

Note that the due date of Homework 8 is Thursday Dec 1, rather than usual Tuesday
In preparation for the final exam, note that the exam is cumulative, that is,
I may ask questions from all sections of the course, and give problems related to any topic .
In order to get a high grade, A- and above, you will need to be able to prove theorems.
Office Hours:
Monday, Dec 5th, 10:00am-12:00pm, will stay longer if necessary
Tuesday, Dec 6th, 10:00am-2:00pm
I will be away next week. Anahita will run the midterm, and the class on Thursday is cancelled.
Midterm
When: Tuesday, November 8, regular time, 13:30 - 14:20
Where: regular place, BLU 9660
Duration: 50 minutes, regular class
What's included: `theory' questions (definitions, theorems, etc.) on Greedy Algorithms, Divide and Conquer, Dynamic Programming, Network Flows, and Linear Programming.
Problems to solve on the same topics (problems from HW1 -- HW4).
More you can learn from a sample midterm posted on the course webpage.
What do you need to have with you?: Only a pen or pencil.

Course Texts:

"Algorithm Design" by Jon Kleinberg and Eva Tardos, Addison Wesley, 2005

"Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill, MIT Press

References:

"Computational Complexity" by Christos H. Papadmitriou, Addison Wesley, 1995
"Approximation Algorithms" by Vijay V. Vazirani, Springer, 2nd ed. 2004
"Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005
"The Art of Computer Programming. Vol. 1,2,3,4" by D. E. Knuth, Addison Wesley
"Concrete Mathematics" by R. L. Graham; D. E. Knuth; and O. Patashnik, Addison-Wesley, 1994

Instructor: Andrei Bulatov (abulatov@sfu.ca), Office: TASC 8013

TA:

Lectures:
- Tu 13:30-14:20, in BLU 9660
- Th 12:30-14:20, in K 9500
Office Hours by Instructor: Mo 10:00-12:00 (starting from Sep. 19th),
and We 10:00-12:00 (starting from Sep. 28th) in TASC 8013 (or by appointment).
Office Hours by TAs: No

Assignments due:
- Assignment 1 is due Tuesday, September 27
- Assignment 2 is due Tuesday, October 4.
- Assignment 3 is due Tuesday, October 11.
- Assignment 4 is due Tuesday, October 18.
- Assignment 5 is due Tuesday, November 1.
- Assignment 6 is due Tuesday, November 15.
- Assignment 7 is due Tuesday, November 22.
- Assignment 8 is due Thursday, December 1.
Midterm:
- Tuesday, November 8, regular time 13:30 - 14:20, regular room, BLU 9660
Final exam:
- Wednesday, December 7, 8:30 - 11:30, room AQ 3150

I will post slides I use in class.