CS466admin

CS 466/666 - Fall 2010
Design and Analysis of Algorithms
Administrative Issues

Home

Lectures

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.

Course Components

The primary components of the course are lectures, assignments, and exams, and the policies and procedures for each of these are outlined on their respective pages. Each CS666 (grad) student will do a course project involving writing a review of a research paper related to topics covered in the course. More details can be found here.

This website will be the primary means of communication and distribution of materials for the course. A broader forum for course-related communication will be the course newsgroup, as discussed on the resources page. Textbooks used in the course are also listed on that page, although the primary source for information will be the lectures.

Marks

For CS466:

Final	45%
Midterm	20%
Assignments	35%

For CS666:

Final	35%
Midterm	15%
Assignments	30%
Project	20%

Students must pass the weighted exam mark in order to pass the course.
The instructor reserves right to adjust marks.

Return Policy

Assignments 1-4 and the midterm exam will be returned initially in class as soon as they have been marked and the marks have been recorded.
After the initial handback in lecture, all assignments and exams will be available in the instructor's office hour.
All assignments and midterm exams will be held until the last day of exams. After this date, any unclaimed assignments and midterm exams will be destroyed.

Mark Appeals

All mark appeals (for assignments and midterm) must be made within 2 weeks of the date of the return or before the final exam, whichever is earlier (if you pick up your assignment/exam late, your appeal period does not lengthen). Note that as a result of closer scrutiny of your work, marks may go up or down.

For assignments:
1. Review all available material before appealing your mark. This includes model solutions, and the comments and marking schemes posted in the course newsgroup.
2. Appeal your mark to the TA who marked the question (see newsgroup postings for who).
3. Only if the appeal was not satisfactorily explained and resolved by the TA, bring your case to the instructor (this should happen rarely).
For midterm: The midterm mark appeals can be submitted in writing only to the instructor.

Academic Dishonesty

Cheating includes not only copying the work of another person (or letting another student copy your work), but also excessive collaboration.
You are allowed to talk with classmates about assignment questions only at an "abstract" level (i.e., general ideas). You must work out the details of your solutions on your own; in particular, your writeup must be expressed entirely in your own words. If you have discussions with others, I'd recommend that you (i) do not take any written notes during such discussions, (ii) wait several hours before writing your solutions (to let details fade), (iii) never show your writeup to other students, and (iv) acknowledge any person you have talked to (or any sources you have consulted). Note that TAs are trained in spotting suspicious similarities.

University Policies

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. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research.
The Office of Academic Integrity's website contains detailed information on UW policy for students and faculty.
This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in—and out—of the classroom.
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.
Discipline: A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 — Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 — Student Discipline.
Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy.
Appeals: A student may appeal the finding and/or penalty in a decision made under Policy 70 — Student Petitions and Grievances (other than regarding a petition) or Policy 71 — Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals.