CMPUT204, Fall 2005

Main page

This is the main course web page for CMPUT204, Fall 2005 (both sections). 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 the menu.


Contact Information

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 you send me an e-mail on Friday or Saturday, don't expect to get a quick response.

Course Information Sheet and References

Here is the course information sheet in Postscript format and in PDF format.
(Download a free Postscript viewer.)

Text Book
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.

Additional References

Grading Scheme

Important dates

Date Event
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

Course outline

Topics to be covered and relevant readings from the text:

Basics (3-30)
- 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 provided)
- Mergesort and Insertion sort (recall)
- Quicksort
- Bucketsort and Radixsort
- Lower bound on sorting

Heaps (Chapter 6 of CLRS will be provided, 94-95, 99-111)
- Heaps
- Heapsort
- Priority Queues

Design Techniques (Chapter 5)
- Greedy method
- Divide-and-Conquer
- Dynamic Programming

Graphs (289-293, 296-320, 325-328, 225-234)
- Basics
- Traversals (DFS/BFS)
- Applications
- Set ADT

Graph Algorithms (340-355, 360-369)
- Shortest paths
- Minimum Spanning tree

Additional Topics (time permitting)

Course newsgroup

General Policies