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.
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.
Preview the lecture content before coming to the class;
review the lecture slides after class to identify unclear points;
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)
|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
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
"Introduction to Algorithms (Third Edition)". The MIT Press (September 30, 2009).
- M. R. Garey and D. S. Johnson (1979). "Computers and Intractability: A Guide to the Theory of NP-completeness". W. H. Freeman & Company.
- 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):
Ch 15, 32: sequences and strings
||Course pre-requisite (CMPUT 204) evaluation - exam (6%)
||Ch 15: Longest common subsequence (dynamic programming)
||Ch 15: Edit distance
||Ch 32: String matching|
Ref: The fundamental preprocessing
Assignment #1 (6%) due at the beginning of class
||Ch 32: The KMP algorithm
||Research travel, TAs to discuss Assignment #1 questions in class
||Appendix B and Ch 22: Graphs|
Ch 23: Minimum spanning trees
||Ch 24: Single source shortest paths|
Assignment #2 (6%) due at the beginning of class
||Ch 25: All-pairs shortest paths
||Ch 25: All-pairs shortest paths|
Ch 26: Maximum flow: Edmonds-Karp algorithm
||Ch 26: Maximum flow: push-relabel algorithms|
Midterm classroom feedback collecting
Assignment #3 (6%) due at the beginning of class
||Midterm in class (80 minutes, closed book, on Assignments 1 & 2 | Ch 15, 32, 22, 23)|
||Ref: Turing machines
||Ch 34: Classes P, NP, and co-NP
||Ch 34: NP-completeness and reducibility (HC ≤p TSP)
||Ref: Cook's Theorem (CNF-SAT ≤p SAT)
||Ch 34: NP-completeness proofs (SAT ≤p 3-CNF-SAT)|
Assignment #4 (6%) due at the beginning of class
||Ch 34: NP-completeness proofs (CNF-SAT ≤p 3-CNF-SAT ≤p 3-Coloring ≤p 4-Coloring)
||Nov 10, 12
||Ch 35: Approximation algorithms|
Assignment #5 (6%) due at the beginning of class
||Ch 35: Approximation algorithms
||Ch 35: Approximation algorithms / inapproximability
||Ch 35: Approximation algorithms|
Nov 30 is the last day for withdrawal
||UTS Teaching evaluation open|
Ch 35: Approximation algorithms
Assignment #6 (6%) due at the beginning of class
||10am - 2pm: Office hours in ATH 332
||10am - 2pm: Office hours in ATH 332/328
||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:
||Deferred final exam:
- 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)
- 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).
- 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.