CMPUT 204: Algorithms I
Fall 2004 Course Page

A1 (V 128): Bowling
A1 (V 128): Bowling
A1 (V 128): Bowling
F03: Mikhaeil
A2 (V 103): Salavatipour
A2 (V 103): Salavatipour
A2 (V 103): Salavatipour
F02: Chen
F01: Liu
Instructors: Michael Bowling (Course Coordinator)
Office Hours: M 3-4pm, W 11am-Noon
ATH 339
Mohammad Salavatipour
Office Hourse: M 2-3pm, F 2-3pm
ATH 303
TAs: Rimon Mikhaeil rimon-AT-cs-DOT-ualberta-DOT-ca
Guohua Liu guohua-AT-cs-DOT-ualberta-DOT-ca
Xian Chen xianchen-AT-cs-DOT-ualberta-DOT-ca

   :  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!):
  1. 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.
  2. 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.
  3. Nov 19, 2004: Here are the solutions to the 3rd term test.
  4. Oct 29, 2004: Here are the solutions to the 2nd Midterm.
  5. Oct 11, 2004: For those in lecture A1: The office hour on October 11 (Thanksgiving Monday) has been moved to October 12, 1:30-2:30pm.
  6. Oct 7, 2004: For those in session A2: The office hour on this Friday (2-3) is canceled. If you need help you can come to my office tomorrow between 11-12 or on Tuesday (Oct 12), between 2-3.
  7. Oct 4, 2004: Here are the solutions to the first Midterm.
  8. 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.
  9. 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.
  10. Sep 27, 2004: Assignment 2, Question 1: You do not need to write out the induction proof if you use iterated substitution.
  11. Sep 22, 2004: Assignment 2 and solutions to Assignment 1 are posted.
  12. 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.
  13. Sep 15, 2004: Ignore question 4(b) of Assignment 1. The marks for that question will be shifted to parts (a) and (c).
  14. Sep 8, 2004: Seminar F04/EF04 is cancelled. If you were in this seminar, you must register for one of the other three seminars.
  15. Aug 4, 2004: Course page started.
  16. Newsgroup:

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 1-2, Appendix A-C) 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
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 1-4, Appendix A-C)  
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 7-8.1)
Assignment #2 Due
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, Matrix-chain multiplication (Chap 15.1-2) Lecture17.pdf
Oct 22 Matrix-chain multiplication, DP characteristics and LCS problem (Chap 15.1-4) Lecture18.pdf
8 Oct 25 LCS and Edit distance Lecture19.pdf
Oct 27 More Dynamic Programming Lecture20.pdf
Oct 29 Midterm #2 (Chapters 6-8, 15.1-3)  
9 Nov 1 Graph notions (Chap 22.1) Lecture21.pdf
Nov 3 Disjoint sets: array of representatives (Chap 21.1-2)
Assignment #3 Due
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 Breadth-First-Search (Chap 22.1-2) Lecture25.pdf
Nov 12 Fall Break: No Lecture  
11 Nov 15 Depth-First-Search and bicomponents (Chap 22.3, Prob 22-2) Lecture26.pdf
Nov 17 Bicomponents, Greedy algorithms, MST problem (Chap 23.0-2) Lecture27.pdf
Nov 19 Midterm #3 (Chapters 21-22.2)  
12 Nov 22 Greedy, MST problem, Prim's algorithm (Chap 23.0-2) Lecture28.pdf
Nov 24 Prim's and Kruskal's MST algorithms (Chap 23.2)
Assignment #4 Due
Nov 26 SSSP problem and Dijkstra's algorithm (Chap 24.0, 24.3) Lecture30.pdf
13 Nov 29 Bellman-Ford's and Floyd-Warshalls' 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 NP-completeness (Chap 34) Lecture33.pdf
14 Dec 6 Cook's Theorem and NP-completeness proofs (Chap 34) Lecture34.pdf
Dec 8 Example NP-completeness proofs (Chap 34)
Assignment #5 Due

Grading Scheme (Fall 2004) :

  1. 5 Assignments: 35% (6% + 8% + 8% + 8% + 5%)
  2. 3 Midterms (in class, 50 minutes each): 30% (10% + 10% + 10%)
  3. Final Exam (3 hours): 35%
  • 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:
    • A     90
    • B     78
    • C     65
    • D     50
  • 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, NP-Completeness

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.