
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, 300).
The second course of a twocourse sequence on algorithm design.
Emphasis on principles of algorithm design.
Categories of algorithms such as divideandconquer, greedy algorithms, dynamic programming; analysis of algorithms;
limits of algorithm design; NPcompleteness; 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
Time 
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
9:30 





11:0012:20 
Office hour (ATH 353) 
A1/EA1 (SAB 326) 

A1/EA1 (SAB 326) 

12:30 





14:00 





15:3016:50 





 Office
 Phone
 Email

Guohui Lin (instructor)
 ATH 353
 4923737
 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:
 M. R. Garey and D. S. Johnson (1979). "Computers and Intractability: A Guide to the Theory of NPcompleteness". 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):
Week 
Date 
Lecture Topics 
1
 Sep 1
 Course overview
Ch 15, 32: sequences and strings

Sep 3
 Course prerequisite (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: Allpairs shortest paths

6
 Oct 6
 Ch 25: Allpairs shortest paths
Ch 26: Maximum flow: EdmondsKarp algorithm

Oct 8
 Ch 26: Maximum flow: pushrelabel 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 coNP

9
 Oct 27
 Ch 34: NPcompleteness and reducibility (HC ≤_{p} TSP)

Oct 29
 Ref[1]: Cook's Theorem (CNFSAT ≤_{p} SAT)

10
 Nov 3
 Ch 34: NPcompleteness proofs (SAT ≤_{p} 3CNFSAT)
Assignment #4 (6%) due at the beginning of class

Nov 5
 Ch 34: NPcompleteness proofs (CNFSAT ≤_{p} 3CNFSAT ≤_{p} 3Coloring ≤_{p} 4Coloring)

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: 9amnoon, 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:
http://www.registrarsoffice.ualberta.ca/en/Examinations/Fall2015Winter2016ExamPlanner.aspx

 Jan 7
 Deferred final exam:

Grading Scheme:
 Mark distribution:
 6% Prerequisite 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)
 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 coversheet 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 lettersize 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.
 