CMPUT204, Fall 2005
This is the main course web page for CMPUT204, Fall 2005 (both
Please use the links below and in the menu bar to the left to find the
information you need about this course.
If you do not see a Menu on the left, then your browser does not
support frames. In that case, click here for
- Instructor: Mohammad R. Salavatipour.
- e-mail address:
- Section A1: MWF, 10:00-10:50, V128.
- Section A2: MWF, 12:00-12:50, V103
- Tutorials (Seminars):
- Mon, 5:00-5:50, CAB357, by Xian Chen
- Tue, 12:30-1:20, CAB229, by Bruce Cameron
- Wed, 11:00-11:50 CAB377, by Guohua Liu
- Office hours: MF, 2-3.
- Office: Ath303.
Generally, the best way to contact me is by e-mail. I try to answer
e-mails within 1-2 working days. Often it is within the same day but if
send me an e-mail on Friday or Saturday, don't expect to get a quick
Course Information Sheet and References
Here is the course information sheet in
Postscript format and in PDF format.
(Download a free Postscript
The course text book is: ``Algorithm
Design'' by Michael Goodrich and Roberto Tamassia, John Wiley, 2002.
The link also has useful information about the course.
Here is the Errata.
- Five Assignments at 5% each: 35%
- Two term tests at 13% each: 26%
- Final Exam: 39%
|Wed, Sep 7
||First lecture (Assignment 1 is posted)
|Wed, Sep 28
||Assignment 1 due (Assignment 2 is posted)
|Mon, Oct 10
||Thanksgiving (no lecture)
|Wed, Oct 12
||Assignment 2 due
| Wed, Oct 19
||Term test 1 (Assignment 3 is posted)
|Wed, Nov 2
||Assignment 3 due (Assignment 4 posted)
|Fri, Nov 11
|| Remembrance day (no lecture
|Wed, Nov 16
|| Assignment 4 due
|Wed, Nov 23
||Term test 2 (Assignment 5 posted)
| Wed, Dec 7
|| Assignment 5 due, Last lecture
Topics to be covered and relevant readings from the text:
- Methodologies for Analyzing Algorithms
- Asymptotic notations
- Mathematical Reviews
Recurrences (219-224, 263-270)
- Mergesort as an example
- Recurrence relations
Sorting Algorithms (219-224, 239-243, Chapter 7 of CLRS will be
- Mergesort and Insertion sort (recall)
- Bucketsort and Radixsort
- Lower bound on sorting
Heaps (Chapter 6 of CLRS will be provided, 94-95, 99-111)
- Priority Queues
Design Techniques (Chapter 5)
- Greedy method
- Dynamic Programming
Graphs (289-293, 296-320, 325-328, 225-234)
- Traversals (DFS/BFS)
- Set ADT
Graph Algorithms (340-355, 360-369)
- Shortest paths
- Minimum Spanning tree
Additional Topics (time permitting)
- The course newsgroup is for discussions of topics related to the
course, including (but not limited to) questions and answers about the
course material and assignments.
- Important: NEVER
post to the course newsgroup your solution to an assignment, or even
your idea of the solution to an assignment, or even one small part of a
program or proof that is part of your solution to an assignment, etc.
In particular, questions similar to the ones in the following list
should be avoided completely:
"... Is this the right idea?" , "... Can anyone tell me what's wrong
with this?" , "For this question, are we supposed to do X or Y?"
- Post a message to
- Electronic Correspondence: Please do not send messages
that include HTML or MIME. I can only read plain ASCII text.
- Assignments and late policy: All assignments are due on
Wednesday by noon (at the beginning of the lecture for Section A2).
Late assignments (up to 24 hours) will
be deducted 50% of the full mark for that assignment. Assignments
submitted later than 24 hours after due time will get zero.
- Missed term test or exam:
Term tests and Final Exam absence may result in a mark of 0, unless an
acceptable excuse exists and is supported by documentation, in which
- for a missed term test, the weight of that test will be
carried over to the final exam;
- for a missed Final Exam, the student must apply to their
Faculty Office (not the instructor) for permission to write the
- Remarking Requests:
You may NOT submit a remarking request later than TWO WEEKS
from the date on which the assignment or
test was returned, with the exception of the last assignment, for which
you can submit a remarking request
no later than ONE week after it is returned.
We will NOT accept remarking requests after these
deadlines. It is your responsibility to pick
up your assignment or test as soon as possible. If you were not in
class or in tutorial when it was handed
back, pick it up from your instructor's office, immediately.
- Collaboration on Assignments and Plagiarism:
- What is plagiarism?: "Submitting the words, ideas,
images or data of another person's as ones own."
For more details, see
Code of Student Behaviour
- Are we allowed to collaborate on assignments?:
You are allowed to discuss the assignments with each other, but you
must write your solutions alone and independently. In particular, you
are not allowed to take any written (or recorded) notes
from your discussions.
You must list the name of students you have discussed the assignment
with, and any other sources that you have used on the front page of