| |
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
| Time |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| 9:30 |
|
|
|
|
|
11:00-12:20
|
Office hour (ATH 353) |
A1/EA1 (SAB 326) |
|
A1/EA1 (SAB 326) |
|
| 12:30 |
|
|
|
|
|
| 14:00 |
|
|
|
|
|
15:30-16:50
|
|
|
|
|
|
|
| Office
| Phone
| Email
|
| Guohui Lin (instructor)
| ATH 353
| 492-3737
| 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 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):
| 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:
http://www.registrarsoffice.ualberta.ca/en/Examinations/Fall-2015-Winter-2016-Exam-Planner.aspx
|
|
| Jan 7
| Deferred final exam:
|
Grading Scheme:
- 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)
- 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).
- 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.
| |