University of Waterloo
Term and Year of Offering: Fall 2016
Course Number and Title: CS341, Algorithms
| Instructor's Name | Office Location |
Contact | Office Hours |
| Jeffrey Shallit | DC 3134 |
shallit@cs.uwaterloo.ca | Mon 11 AM-Noon; Wed Noon - 1 PM |
| Tim Smith | DC 3124 |
timsmith@uwaterloo.ca | Tuesdays 4:30 - 6:30 |
| TA's Name | Office Location | Contact | Office Hours |
| Daniel (Tiancong) Wang | DC 2582 | t258wang@uwaterloo.ca | Wednesdays, 2:30 - 3:30 PM |
| Vedat Levi Alev | DC 3115 | vlalev@uwaterloo.ca | Mondays, 3:30 - 4:30 PM |
Hong Zhou | DC 3115 | h76zhou@uwaterloo.ca | Tuesdays, 3:30 - 4:30 PM |
| Shayan Hassantabar | DC 3549 | ss3hassa@uwaterloo.ca | Wednesdays, 10 - 11 AM |
Course Description:
The study of efficient algorithms and effective algorithm design techniques. Program design with emphasis on pragmatic and mathematical aspects of program efficiency. Topics include divide and conquer algorithms, recurrences, greedy algorithms, dynamic programming, graph search and backtrack, problems without algorithms, NP-completeness and its implications.
Course Objectives:
To study efficient algorithms, effective algorithm design techniques and approaches to handling situations in which no feasible algorithms are known. The course is intended to give the student experience in program design and to emphasize both pragmatic and mathematical aspects of program efficiency.
Course Overview:
Introduction and Analysis of Algorithms (6 hours)
Review of previously encountered algorithm design approaches including divide and conquer. Solution of basic recurrence relations arising in such methods. The notions of average case and worst case behaviours.
Algorithm Design Techniques (15 hours)
A systematic study of design methods including greedy algorithms, dynamic programming, approaches to exploring graphs, backtracking, and branch and bound. Application of these techniques to a variety of problems commonly occurring in practice. Implementation of some examples and discussion of related issues.
Undecidability and Intractability (15 hours)
Algorithmically reducing one problem to another as a means of developing algorithms and proving lower bounds. The undecidability of the halting problem. Proving other problems undecidable via reductions. Reductions between decision and optimization problems. The idea of polynomial time and its independence of many machine models. The classes P and NP and their relationship. Polynomial reducibility and NP-Completeness. A selection of NP-hard problems and proofs of this status.
Required text:
Introduction to Algorithms, 3rd ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.
Evaluation:
Assignments 36%, Midterm 20%, Final Exam 44%.
Late policy:
Late assignments will not be accepted and will be given a mark of zero (except for extenuating circumstances such as illness).
Rules for Group Work:
Although you may discuss general aspects of assignments with classmates, you must work out the details of your solutions on your own; in particular, your writeup must be expressed entirely in your own words. Consultation with other sources must be clearly acknowledged.
Indication of how late submission of assignments and missed assignments will be treated
Late assignments will not be accepted and will be given a mark of zero (except for extenuating circumstances such as illness).
Indication of where students are to submit assignments and pick up marked assignments
Assignments are due at 5PM Thursdays and should be handed in via learn.
Academic Integrity: In order to maintain a culture of
academic integrity, members of the University of Waterloo community are
expected to promote honesty, trust, fairness, respect and responsibility.
[Check www.uwaterloo.ca/academicintegrity/
for more information.]
Grievance: A student who believes that a decision affecting
some aspect of his/her university life has been unfair or unreasonable may
have grounds for initiating a grievance. Read Policy 70, Student Petitions
and Grievances, Section 4, www.adm.uwaterloo.ca/infosec/Policies/policy70.htm.
When in doubt please be certain to contact the department's administrative
assistant who will provide further assistance.
Discipline: A student is expected to know what constitutes academic
integrity [check www.uwaterloo.ca/academicintegrity/]
to avoid committing an academic offence, and to take responsibility for
his/her actions. A student who is unsure whether an action constitutes an
offence, or who needs help in learning how to avoid offences (e.g.,
plagiarism, cheating) or about 'rules' for group work/collaboration should
seek guidance from the course instructor, academic advisor, or the
undergraduate Associate Dean. For information on categories of offences
and types of penalties, students should refer to Policy 71, Student
Discipline, www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.
For typical penalties check Guidelines for the Assessment of Penalties, www.adm.uwaterloo.ca/infosec/guidelines/penaltyguidelines.htm.
Appeals: A decision made or penalty imposed under Policy 70
(Student Petitions and Grievances) (other than a petition) or Policy 71
(Student Discipline) may be appealed if there is a ground. A student who
believes he/she has a ground for an appeal should refer to Policy 72
(Student Appeals) www.adm.uwaterloo.ca/infosec/Policies/policy72.htm.
Note for Students with Disabilities: The Office for persons with
Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with
all academic departments to arrange appropriate accommodations for
students with disabilities without compromising the academic integrity of
the curriculum. If you require academic accommodations to lessen the
impact of your disability, please register with the OPD at the beginning
of each academic term.