CMPT 405 - Design and Analysis of Algorithms - Spring'17

Instructor | Times & dates | Homeworks & midterm | Lectures

Announcements

The final exam is marked and the grades are out.
Those who didn't submit the project have received the same mark for the project
I also made available the total weighted grade for the course. However, projects are still being marked, and so the total grade of some may change.
To determine the letter grade I used the following cutoffs:
A+: >94
A: 93.99-89.00
A-: 88.99-84
B+: 93.99-79
B: 78.99-74
B-: 73.99-69
C+: 68.99-64
C: 63.99-59
C-: 58.99-54
D: 53.99-50
F: <50

Outline solution to the final exam's problems can be found on the course webpage
You can come to review your work or discuss your grade today, Thursday, April 20, between 12 and 2pm. I will finish marking projects by that time.
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:
Tuesday, Apr 18th, 10:00am-2:00pm
Midterm
When: Thursday, March 2, regular time, 11:30 - 12:20
Where: regular place, BLU 10021
Duration: 50 minutes, regular class
What's included: `theory' questions (definitions, theorems, etc.) on Greedy Algorithms, Divide and Conquer, Dynamic Programming,
Network Flows, and Approximation. This includes lectures 2-14
Problems to solve on the same topics excluding approximation (problems from HW1 -- HW3).
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.
There is a typo in Problem #1 of assignment 2. More precisely, the algorithm given in the problem does not make much sense.
For a correct statement please refer to the online version here
Here I explain how you should solve and submit the first homework.
- Solving.
  Solutions to the homeworks must be your own. It does not mean that you cannot solve them with your friends, this means that
  you have to write solutions on your own, avoiding copying and consulting. This is what the university policy requires.
  
  There are no specific requirements for formatting solutions, title pages and so on. Use your common sense to make sure your
  writing and your solutions are clear and understandable. Don't forget to indicate your name, student ID, and assignment number
  on the first page.
  Whenever you are asked to design an algorithm, you should include an analysis of that algorithm, that is, to prove soundness
  and give an estimation of running time
- Handing in. There are 3 ways to hand in your work.
  
  1. You can bring it to the class on the due day, and put it on my desk BEFORE THE CLASS. 70% of people usually do that.
  
  2. You can put it into the assignment box located in ASB 9838.
  BE CAREFUL!! PUT YOUR WORK INTO THE RIGHT BOX!! If you put it into a wrong box, in some cases it will be viewed
  as late submission and you will lose points; in some case it will be viewed as very late submission and you will get 0.
  
  3. You can slide your work under my office door.
- Deadline: The moment I step into my office after the class on the due day. All works handed in after this moment will be
  considered as late submission. There is absolutely no submission after I post solutions. This will normally happens a day or two
  after the due day.
Course information handout:
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:
- Amineh Dadsetan (adadseta@sfu.ca)
Where and When
- Lectures:
  - Tu 11:30-13:20, in BLU 10011
    Th 11:30-12:20, in BLU 10021
- Office Hours by Instructor: Mo 10:00-12:00 (starting from January 16th), in TASC 8013 (or by appointment).
- Office Hours by TAs: No
Important dates
- Assignments due:
  - Assignment 1 is due Thursday, January 26.
  - Assignment 2 is due Thursday, February 9.
  - Assignment 3 is due Thursday, February 23.
  - Assignment 4 is due Thursday, March 9.
  - Assignment 5 is due Thursday, March 23.
  - Assignment 6 is due Thursday, April 6.
- Midterm:
  - Thursday, March 2, regular time 11:30 - 12:20, regular room, BLU 10021
- Final exam:
  - Wednesday, April 19, 8:30 - 11:30, room SWH 10041
Homeworks and Midterms
Lectures
I will post slides I use in class.
Relevant Links
- Reinhard Diestel Graph Theory
- The Ethernet protocol. Find our algorithm in this description.
- Impagliazzo's talk on the power of randomness

CMPT 405 - Design and Analysis of Algorithms - Spring'17

Announcements

Where and When

Important dates

Homeworks and Midterms

Lectures

Relevant Links