: What's new
:: Textbook
:: Lecture Slides & Calendar
:: Grading Scheme
:: Assignment Lists
:: Tutorials
:: Smart Studying Scheme
:::Department Catalogue Description
:::Code of Student Behavior


What's New (204 students check this page often!):
 Dec 7, 2004: A practice final is available (PS or PDF). This final
is from last year and is strictly for
practice. The term tests are more indicative
of the kinds of questions you will be asked on
the final. In particular, question 7 on the
practice final is not something that will likely
appear on this year's final.
 Nov 26, 2004: The due date for the final assignment (5) is
Wednesday, December 8, the last day of
classes. This has been corrected on the
assignment download.
 Nov 19, 2004: Here are the solutions to the 3rd term test.
 Oct 29, 2004: Here are the solutions to the 2nd Midterm.
 Oct 11, 2004: For those in lecture A1: The office hour on
October 11 (Thanksgiving Monday) has been moved to October 12,
1:302:30pm.
 Oct 7, 2004: For those in session A2:
The office hour on this Friday (23) is canceled. If
you need help you can come to my office tomorrow between 1112 or on
Tuesday (Oct 12), between 23.
 Oct 4, 2004: Here are the solutions to the first Midterm.
 Sep 29, 2004: In previous years, 204 has had quizzes in place of
multiple midterms. Therefore, there is no example from a previous
year for what to expect on the midterm, but the closest example is the
first quiz from last year (PS or PDF). The length will be roughly the same,
but the midterm will cover recurrences in addition to the quiz
material.
 Sep 28, 2004: There were two errors in the (explanations of)
solutions to questions 5(d) and 5(e) in assignment 1. The corrected
version is now posted.
 Sep 27, 2004: Assignment 2, Question 1:
You do not need to write out the induction proof if you use iterated substitution.
 Sep 22, 2004: Assignment 2 and solutions to Assignment 1 are posted.
 Sep 21, 2004: After getting requests from students to have the
lecture notes online "before" each lecture, we decided to do it. So from
now on, you can download the lecture note for each lecture one day before
the lecture. This applies to the lecture on Sep 22, too.
 Sep 15, 2004: Ignore question 4(b) of Assignment 1. The marks
for that question will be shifted to parts (a) and (c).
 Sep 8, 2004: Seminar F04/EF04 is cancelled. If you were in this seminar, you must register for one of the other three seminars.
 Aug 4, 2004: Course page started.
 Newsgroup: ualberta.courses.cmput.204
Textbook
:
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Introduction to Algorithms (Second Edition). McGraw Hill. 2001.
Lecture Topics & Calendar:
Week 
Date 
Lecture Topics 
Slides 
1 
Sep 8 
Course overview, basic concepts (Chap 1) 
Lecture01.pdf 
Sep 10 
Getting started with insertion sort (Chap 12, Appendix AC) 
Lecture02.pdf 
2 
Sep 13 
Insertion sort: analysis (Chap 2) 
Lecture03.pdf 
Sep 15 
Merge sort: analysis (Chap 2); big O (Chap 3) 
Lecture04.pdf 
Sep 17 
Growth of functions (Chap 3) 
Lecture05.pdf 
3 
Sep 20 
Recurrence and iterated substitution (Chap 4) 
Lecture06.pdf 
Sep 22 
More iterated substitution, recursion
tree method (Chap 4)
Assignment #1 Due 
Lecture07.pdf 
Sep 24 
Iterated substitution leading to Master Theorem (Chap 4) 
Lecture08.pdf 
4 
Sep 27 
Full version of Master Theorem, and its limit (Chap 4) 
Lecture09.pdf 
Sep 29 
Heap, its properties and construction (Chap 6) 
Lecture10.pdf 
Oct 1 
Midterm #1 (Chapters 14, Appendix AC) 

5 
Oct 4 
Heapsort: algorithm and its analysis (Chap 6) 
Lecture11.pdf 
Oct 6 
Heapsort analysis and more discussion (Chap 6) 
Lecture12.pdf 
Oct 8 
Quicksort algorithm, its BC & WC
running time (Chap 7) 
Lecture13.pdf 
6 
Oct 11 
Thanksgiving: No Lecture 

Oct 13 
Quicksort AC running time and two kinds of trees (Chap 78.1)
Assignment #2 Due 
Lecture14.pdf 
Oct 15 
Decision tree lower bound (Chap 8.1) 
Lecture15.pdf 
7 
Oct 18 
DP concepts, knapscak (Chap 8.1,
15.1) 
Lecture16.pdf 
Oct 20 
knapsack, Matrixchain multiplication
(Chap 15.12) 
Lecture17.pdf 
Oct 22 
Matrixchain multiplication, DP characteristics and LCS problem (Chap 15.14) 
Lecture18.pdf 
8 
Oct 25 
LCS and Edit distance 
Lecture19.pdf 
Oct 27 
More Dynamic Programming 
Lecture20.pdf 
Oct 29 
Midterm #2 (Chapters
68, 15.13) 

9 
Nov 1 
Graph notions (Chap 22.1) 
Lecture21.pdf 
Nov 3 
Disjoint sets: array of
representatives (Chap 21.12)
Assignment #3 Due 
Lecture22.pdf 
Nov 5 
Disjoint sets: forest of rooted trees (Chap 21.3) 
Lecture23.pdf 
10 
Nov 8 
Union by rank and compressed find (Chap 21.4) 
Lecture24.pdf 
Nov 10 
Graph notions and BreadthFirstSearch (Chap 22.12) 
Lecture25.pdf 
Nov 12 
Fall Break: No Lecture 

11 
Nov 15 
DepthFirstSearch and bicomponents (Chap 22.3, Prob 222) 
Lecture26.pdf 
Nov 17 
Bicomponents, Greedy algorithms, MST problem (Chap 23.02) 
Lecture27.pdf 
Nov 19 
Midterm #3 (Chapters
2122.2) 

12 
Nov 22 
Greedy, MST problem, Prim's algorithm (Chap 23.02) 
Lecture28.pdf 
Nov 24 
Prim's and Kruskal's MST algorithms
(Chap 23.2)
Assignment #4 Due 
Lecture29.pdf 
Nov 26 
SSSP problem and Dijkstra's algorithm (Chap 24.0, 24.3) 
Lecture30.pdf 
13 
Nov 29 
BellmanFord's and
FloydWarshalls' algorithm (Chap 24.1 and 25.2) 
Lecture31.pdf 
Dec 1 
Main ideas and basic concepts (Chap 34) 
Lecture32.pdf 
Dec 3 
Polynomial time reduction and NPcompleteness (Chap 34) 
Lecture33.pdf 
14 
Dec 6 
Cook's Theorem and NPcompleteness proofs (Chap 34) 
Lecture34.pdf 
Dec 8 
Example NPcompleteness proofs (Chap
34)
Assignment #5 Due 
Lecture35.pdf 
Grading Scheme (Fall 2004)
:
 5 Assignments: 35% (6% + 8% + 8% + 8% + 5%)
 3 Midterms (in class, 50 minutes each): 30% (10% + 10% + 10%)
 Final Exam (3 hours): 35%
Note:
 Any questions concerning the marking of an assignment or a midterm
should be brought to the attention of the marker (this will be either the instructor or a TA)
within 7 days of the date on which the assignment or the test has been returned to
the class (lecture or tutorial) in question;
After that time, marks cannot be changed.
 No late policy for assignments. Assignments are due at the beginning of lecture on their due date.
 Midterms and Final Exam absence may result in a mark of 0, unless an acceptable
excuse exists and is supported by documentation, in which case
 for a missed Midterm, the marks will be added to the final exam;
 for a missed Final Exam, the student must apply to the Faculty of Science (not the instructor)
for permission to write the deferred exam.
 The University's exam policy.
 Following recent departmental practice, all cases of
plagiarism will
be forwarded by the instructor to the dean.
See The Code of Student Behavior.
 Grade cutoffs will be assigned within a few points of each of the following, taking into consideration
the final distribution of marks:
 This course has multiple sections.
You must write all exams in the lectur in which you are registered, because
lectures and exams vary slightly between sections. So should you attend the lectures in which
you are registered.
 Final grade cutoffs for each section will be set individually, in consultation with the instructors of
the other sections.
Assignment List:
:
Assignment 
Topics covered 
Assignment 1 in PDF or PS
Solutions to Assignment 1 in PDF or PS

Growth of functions, induction, analysis of
algorithm 
Assignment 2 in PDF or PS
Solutions to Assignment 2 in PDF or PS

Recurrences, sorting, heaps 
Assignment 3 in PDF or PS
Solutions to Assignment 3 in PDF or PS

More sorting, dynamic programming 
Assignment 4 in PDF or PS
Solutions to Assignment 4 in PDF or PS

Disjoint sets, graph algorithms 
Assignment 5 in PDF or PS
Solutions to Assignment 5 in PDF or PS

More graph algorithms, NPCompleteness 
Tutorials
:
Tutorials are for the purpose of additional review and discussion of
the lecture topics. It will also be used to discuss go over the
solutions to homework assignments and midterms. New material may also
be presented, for which students will be responsible
Smart Studying Scheme
:
It is strongly recommended that you understand the topics in the lecturing days.
Leaving them behind causes serious trouble according to former CMPUT 204 students.
Some key points of success are listed in the following.
(Nonetheless, following them all does not necessarily guarantee high marks.)
 Lecturing contents:
 Before the lectures, print out the agenda and have (at least) 30 minutes
going through the related textbook chapters (appendix);
 After the lecture, have (at least) 30 minutes going through the slides and
the related textbook chapters (appendix) again.
 Turn to either instructors (after
lecture or office hours) or TAs (tutorials, emails, newgroups)
for the parts you don't understand well.
 Assignments:
 After reviewing the lecture contents, solve the related questions in the assignments.
Students are encouraged to discuss and study in small groups. Nonetheless, software
will be applied to scan for plagiarism/cheating.
 Turn to instructors or TAs for help, ONLY after you have seriously thought
about the questions for some time.
 Midterms:
 Check with TAs and/or instructors to make sure you can solve every question on the
Midterms.
 Don't miss any one of the questions!
Similar questions might occur again in the Final.
 Using office hours:
 Take advantage of the office hours! If you do have time conflicts, send emails
to request for an appointment.
 The expected hours per week: at least 10.
