Course Outline
CS 860: Advanced Topics in Algorithms and Complexity
Fall 2016

Course description and objectives

The topic for Fall 2016 is "The State of P vs. NP." We will read and discuss papers from the literature (both classic and recent) that explore ideas and progress on this central issue of theoretical computer science. By the end of the course, students should have the ability to

Instructor and contact information

Jonathan Buss, DC 3353, x34428, jfbuss@cs.uw… Office hours are set for TTh, 10:00–11:00am. To schedule an alternative time, contact the instructor; or simply drop by for a chat.

Course meetings: Wednesdays and Fridays, 10:30–11:50am, DC 2568.

References and syllabus

References will be listed from time to time.

Work for the course

Each student will present one or more papers to the class, selected by the instructor in consultation with the student. This will include reading and understanding the paper, organizing the material for presentation to fellow students (including determining what to include and what to exclude), and making the presentation.

The instructor will assist with this work. He has reserved Fridays at 2:00–3:30 for consultation and will arrange other times as required.

Required work

Grading: attendance/listening, 15%; presentation, 15%; term paper, 70%.

Auditors should listen and present the same as graded students, but need not submit a term paper.

Feedback and retention of student work

The instructor will provide written feedback on the student's oral work, as well as mark-up of any submitted work.

The instructor will retain hard copies of the submitted term papers for one year. Electronic copies will persist longer, unless specifically requested by the student.

Note for students with disabilities

AccessAbility Services (AAS), located in Needles Hall 1401, 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 AAS at the beginning of each academic term.

UW policies

This course adheres to the UW Senate's statement of academic integrity, to wit:

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.


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.


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

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 Guidelines.


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.