CS 466/666, Fall 2011

Course Outline

Course Number and Title: CS466, Algorithm Design and Analysis

Term and Year of Offering: Fall 2011

Time and location of offering: 01:00-02:20TTH, DWE3516

Instructor: Therese Biedl, DC2341, biedl -at- uwaterloo.ca, Office hours 10-11W

TAs: Shahin Kamali (DC2305, skamali -at- uwaterloo.ca, Office hours 9:30-10:30M), Jakub Truszkowski (DC2501, jmtruszk -at- uwaterloo.ca, Office hours 11-12F).

Course Description: Algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and applications.

Course Objectives: To enhance the student's understanding of algorithm design and analysis techniques.

Required text: No required textbook.

Course Overview:
Algorithm techniques (sample): Amortized analysis, Randomized algorithms, Adaptive analysis, Lower bounds, NP-hardness, Exact algorithms, Approximation algorithms, PTAS and FPTAS, Hardness of approximation, Fixed-parameter tractability, Incremental and online algorithms.
Problems considered (sample): Priority Queues, Convex Hull, Selection, Minimum Enclosing Disk, Linear programming, Union/Find data structures, Minimum Spanning Tree, Travelling Salesman, Vertex Cover, Satisfiability, Maximum Cut, The lost cow problem, Set Cover.

Evaluation: For CS466 students: Assignments: 20%, Midterm: 30%, Final: 50%
For CS666 students: Assignments: 20%, Midterm: 25%, Project: 15%, Final: 40%
All students must pass the final to pass the course.

There will be 5 assignments, due at 5:00pm on Wednesday, Oct. 5, 19, Nov. 2, 16, 30.

Assignments involve only written work (no programming). Your solutions will be judged not only for correctness but also for the quality of your presentation and explanations. Use lots of pictures and examples to illustrate concepts, but do not give proof by example. Justification is always required unless said otherwise.

Assignments typically involve creating new algorithms/lower bounds. Creativity is not something that can be forced in a few hours. You must look at the assignment very early (preferably the day it becomes available) to give yourself time to "mull over" the question.

The midterm is on Thursday, Oct. 27, in class.

The final is scheduled by the UW registrar, sometime in December.

The CS666 project report is due Wednesday, December 7, 5:00pm, and to be submitted by email in PS or PDF. Students will also meet with the instructor to answer questions about the project (in a meeting scheduled individually in December); the grade for the project depends in part on ths ability to answer such questions.

Group Work: No group work is allowed. Exceptions may be possible for the CS666 project after consultation with the instructor.

Late policy: No late assignments will be accepted.
Any credit not obtained on assignments (by either not doing a question at all, or by not doing it good enough to receive full credit) will automatically transfer to the midterm (Ass. 1-2) or final (Ass. 3-5.)

Handing in and returning assignments: Assignments are to be placed in the CS466 assignment box located on the 3rd floor of MC next to the elevators by the bridge to DC. Please write legibly and staple the pages of your solutions securely. Put your full name and ID number on the first page on the top right corner.
Assignments and exams will be returned in class. Any assignments/exams not picked up after two classes will be kept for two weeks in a box outside DC2341, publicly accessible to everyone. If you would not like your grade to be publicly accessible, please pick up your assignment/exams before that.

Mark Appeals: All mark appeals (for assignments and midterm) must be made within two weeks of the date of return. If you pick up your assignment/exam late, your appeal period does not lengthen.
For assignments, you should first consult the TA who marked the question. Only if the problem is still unresolved should you then bring the case to the instructor's attention. For the midterm, your appeal should be submitted to the instructor in writing. Note that as a result of closer scrutiny of your work, marks may go up or down.

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.