CMPUT 304: Algorithms II (Fall 2015, A1/EA1)

CMPUT 304 Algorithms II: (University Calendar Description, see also Department Course Description)
*3 (fi 6) (either term, 3-0-0). The second course of a two-course sequence on algorithm design. Emphasis on principles of algorithm design. Categories of algorithms such as divide-and-conquer, greedy algorithms, dynamic programming; analysis of algorithms; limits of algorithm design; NP-completeness; heuristic algorithms. Prerequisites: CMPUT 204; one of STAT 151, 221, 235 or 265; one of MATH 225, 228, 229, 328 or consent of Instructor.

Course Objectives:
Get familiar with some fundamental computational problems and the algorithms for solving them; learn the design techniques for these algorithms, and the associated theoretical analyses; learn the limits of algorithm design and the intractability of problems; learn how to prove the intractability and how to tackle intractable problems.

Student Responsibilities:
Preview the lecture content before coming to the class; review the lecture slides after class to identify unclear points; do assignments; review solutions to the assignments; forward constructive feedbacks to the instructor and/or TAs.

Code of Student Behavior

Department Course Policies

Office hour (ATH 353)
A1/EA1 (SAB 326)
A1/EA1 (SAB 326)

Guohui Lin (instructor)
ATH 353
guohui TA ualberta TOD ca
Christopher Martin (TA)
  csmartin AT ualberta DOT ca
Yao Xu (TA)
  xu2 AT ualberta DOT ca

Recording of teaching is permitted only with the prior written consent of the instructor or if recording is part of an approved accommodation plan.

Course discussion and announcements from the instructor done through eClass/ualberta webpage!

Required textbook: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. "Introduction to Algorithms (Third Edition)". The MIT Press (September 30, 2009).

Recommended readings:

  1. M. R. Garey and D. S. Johnson (1979). "Computers and Intractability: A Guide to the Theory of NP-completeness". W. H. Freeman & Company.
  2. D. Gusfield (1997). "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology". Cambridge Univ. Press.

Lecture Schedule (sign in eClass/ualberta to see assignments, sample solutions, and sample exams):

Week Date Lecture Topics
1 Sep 1 Course overview
Ch 15, 32: sequences and strings
Sep 3 Course pre-requisite (CMPUT 204) evaluation - exam (6%)
2 Sep 8 Ch 15: Longest common subsequence (dynamic programming)
Sep 10 Ch 15: Edit distance
3 Sep 15 Ch 32: String matching
Ref[2]: The fundamental preprocessing
Assignment #1 (6%) due at the beginning of class
Sep 17 Ch 32: The KMP algorithm
4 Sep 22 Research travel, TAs to discuss Assignment #1 questions in class
Sep 24 Appendix B and Ch 22: Graphs
Ch 23: Minimum spanning trees
5 Sep 29 Ch 24: Single source shortest paths
Assignment #2 (6%) due at the beginning of class
Oct 1 Ch 25: All-pairs shortest paths
6 Oct 6 Ch 25: All-pairs shortest paths
Ch 26: Maximum flow: Edmonds-Karp algorithm
Oct 8 Ch 26: Maximum flow: push-relabel algorithms
Midterm classroom feedback collecting
7 Oct 13 Midterm review
Assignment #3 (6%) due at the beginning of class
Oct 15 Midterm in class (80 minutes, closed book, on Assignments 1 & 2 | Ch 15, 32, 22, 23)
8 Oct 20 Ref[1]: Turing machines
Oct 22 Ch 34: Classes P, NP, and co-NP
9 Oct 27 Ch 34: NP-completeness and reducibility (HC ≤p TSP)
Oct 29 Ref[1]: Cook's Theorem (CNF-SAT ≤p SAT)
10 Nov 3 Ch 34: NP-completeness proofs (SAT ≤p 3-CNF-SAT)
Assignment #4 (6%) due at the beginning of class
Nov 5 Ch 34: NP-completeness proofs (CNF-SAT ≤p 3-CNF-SAT ≤p 3-Coloring ≤p 4-Coloring)
11 Nov 10, 12 Reading week
12 Nov 17 Ch 35: Approximation algorithms
Assignment #5 (6%) due at the beginning of class
Nov 19 Ch 35: Approximation algorithms
13 Nov 24 Ch 35: Approximation algorithms / inapproximability
Nov 26 Ch 35: Approximation algorithms
Nov 30 is the last day for withdrawal
14 Dec 1 UTS Teaching evaluation open
Ch 35: Approximation algorithms
Dec 3 Final review
Assignment #6 (6%) due at the beginning of class
  Dec 10 10am - 2pm: Office hours in ATH 332
Dec 11 10am - 2pm: Office hours in ATH 332/328
  Dec 14*** Final exam: 9am-noon, room SAB 326 (3 hours, closed book, on all materials)

***WARNING: Students must verify this date on BearTracks when the Final Exam Schedule is posted. The final exam planner is found on the Registrar's website:

  Jan 7 Deferred final exam:

Grading Scheme:

  1. Mark distribution:
    • 6%     Pre-requisite content evaluation (in class, closed book)
    • 36%     6 Assignments (6% each)
    • 16%     Midterm (in class, 80 minutes, closed book)
    • 42%     Final (3 hours, closed book)
  2. Notes:
    • No late assignments will be accepted.
    • On collaboration, you are encouraged to discuss the assignments with each other, but you must write your solutions alone and independently. You must use the mandatory assignment cover-sheet to submit your work.
    • Any questions concerning the marking of a term exam (by instructor) or an assignment (by TA) should be brought to the attention of the marker within 7 days of the date on which the test has been returned to the class in question; after that time, marks cannot be changed.
    • One letter-size paper with your notes allowed in the exams.
    • Exam absence may result in a mark of 0, unless an acceptable excuse exists. In this case:
      • for a missed term exam, 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 on January 7, 2016 (time and place TBD).
  3. Final grades will be approximately curved, with reasonable cutoffs. Historical cutoffs have been:
    • A+:    90+
    • A, A-:    80+
    • B+, B, B-, C+, C, C-:    60+
    • D+, D:    50+


Disclaimer: Any typographical errors in this Course Outline are subject to change and will be announced in class.


  Last modified: April 28 2016 16:16:30  © Guohui Lin