- Instructor
- Timothy Ng (ng@cs.queensu.ca), Goodwin Hall 235
*Office hours*: Monday 3:30-4:30, Thursday 4:30-5:30- Teaching assistant
- Daniel Gotsch (goc@cs.queensu.ca)
*Office hours*: Wednesday 11:00-12:00, Goodwin Hall 235- Lectures
- Botterell Hall B148, Slot 21 (Monday 2:30-3:30, Tuesday 4:30-5:30, Thursday 3:30-4:30)
- Textbook
- Michael Sipser. Introduction to the Theory of Computation, 3rd ed.

The textbook is available in the bookstore. Older editions are fine. - Grading
- 10% × 5 assignments + 20% midterm + 30% final
- Course webpage
- http://cs.queensu.ca/~ng/cisc462/

Turing machines and other models of computability such as M-5-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.

- Prerequisite
- CISC 223

The course will cover topics from Parts 2 and 3 of the textbook. This outline is subject to change.

References to the textbook are given simply as section numbers. References to secondary sources are given as section numbers preceded by:

**[AB]**Sanjeev Arora and Boaz Barak. Computational Complexity.*This book is available as a draft on the authors' website and an electronic version is available online through the Queen's Library.***[Aar]**Scott Aaronson. Quantum Computing Since Democritus.*These are archived and freely available course notes.*

- Jan 9
- Introduction. What is computability? What is complexity?
- Jan 10
- Turing machines, decision problems (3.1, 3.2)
- Jan 12
- Variants of Turing machines, the Church-Turing thesis (3.2, 3.3)
- Jan 16
- Decidability, properties of regular languages (4.1)
- Jan 17
- Properties of context-free languages (4.1)
- Jan 19
- Undecidability, the Universal Turing machine, diagonalization (4.2)
- Jan 23
- More diagonalization, unrecognizability (4.2)
- Jan 24
- Undecidable problems (5.1)
*Assignment 1 due.*- Jan 26
- Rice's theorem, Mapping reducibility (5.3)
- Jan 30
- More reducibility (5.3), linear bounded automata (5.1)
- Jan 31
- Computation histories (5.1)
- Feb 2
- Post Correspondence Problem (5.2)
- Feb 6
- Introduction to complexity, time complexity. (7.1, Aar4)
- Feb 7
- P. (7.2)
*Assignment 2 due.*- Feb 9
- NP. (7.3)
- Feb 13
- NP-completeness. (7.4)
- Feb 14
- Midterm review.
- Feb 16
- Midterm.
- Feb 20: Reading Week
- No classes.
- Feb 27
- NP-complete problems and reductions. (7.5)
- Feb 28
- More NP-complete problems and reductions. (7.5, AB2.2)
- Mar 2
- The Cook-Levin theorem. (7.4)
- Mar 6
- coNP, space complexity (8.1, AB2.6)
- Mar 7
- PSPACE and Savitch's Theorem. (8.2)
*Assignment 3 due.*- Mar 9
- PSPACE-completeness, logarithmic space (8.3, 8.4)
- Mar 13
- NL-completeness. (8.5)
- Mar 14
- NL = coNL. (8.6, AB4.3)
- Mar 16
- NL-complete problems and reductions.
- Mar 20
- The space hierarchy. (9.1)
- Mar 21
- The time hierarchy. (9.1)
*Assignment 4 due.*- Mar 23
- Relativization. (9.2)
- Mar 27
- The Polynomial Hierarchy. (AB5.1, 5.2, 5.5)
- Mar 28
- Circuits. (9.3, AB6.1, 6.3, 6.4)
- Mar 30
- Probabilistic computation. (10.2, AB7.2-7.4)
- Apr 3
- Derandomization. (AB7.5, Aar7)
- Apr 4
- Final review.
*Assignment 5 due.*- Apr 6
- No class. (Creative Computing Showcase)

There will be 5 assignments. Assignments are to be done individually. Assignments are to be handed in at the beginning of class in class on the due date. Late assignments will not be accepted. If you are unable to finish the assignment, please discuss the matter with me before the assignment is due, as soon as possible. If approved, the weight of the assignment will be transferred to the following exam (midterm or final).

- Assignment 1
- Due Jan 24
- Solutions
- Assignment 2
- Due Feb 7
- Solutions
- Assignment 3
- Due Mar 7
- Solutions
- Assignment 4
- Due Mar 21
- Solutions
- Assignment 5
- Due Apr 4
- Solutions

The midterm will be held on **Thursday February 16**, in class. It will cover everything on **computability theory** (Chapters 3 to 5).

This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.

The final will be held on **Monday April 17** at **9:00 am** in **Goodwin 247**. You will have **3 hours** to complete the final. It will cover topics in **complexity theory** (Chapters 7 to 10).

This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.

Academic Integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1), on the Arts and Science website, and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.

Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at: http://www.queensu.ca/studentwellness/accessibility-services/.