Office hours: (starting Week 1 for Vassos and Week 2 for the TAs, on Zoom links provided by email to students)
Course forum page: https://www.piazza.com/utoronto.ca/winter2022/cscc63
Tutorial times and locations: TBA
Back to the index
Prerequisites: CSCB63 (and, transitively, CSCB36) and one of: enrolment in a computer science program, or a program for which this specific course is a program requirement, or CGPA of at least 3.5.
Textbooks: Sipser. Introduction to the theory of computation (3rd edition). Cengage Learning 2013.
Tentative weekly schedule (check regularly as it may change):
|Paradoxes; cardinality of infinite sets; informal introduction to computability.||
1 video (Quercus).
Sipser, the Diagonalization Method (pp. 202-207).
Notes on countable sets.
|No tutorial this week||Wed: A1 posted|
|Turing Machines; recognizable (recursively enumerable) and decidable (recusive) languages; Turing Machine variants (multitape TMs).||Lecture
2 video (Quercus).
Sipser Ch 3 (excluding Nondeterministic TMs, pp. 178-180).
|No tutorial this week||Wed: A1 due, A2 posted|
|Nondeterministic TMs; Church's thesis, universal TM; undecidability of the universal language, unrecognizability of its complement.||
3 video (Quercus).
Sipser pp. 178-180, §4.2.
|No tutorial this week||Wed:
A2 due, A3 posted
|The halting problem; mapping reductions and Turing reductions; using reductions to prove undecidability or unrecognizability of languages.||
Lecture 4 video (Quercus).
Sipser §5.1, 5.3, 6.3.
Notes on reductions.
|Practice with Turing machines and reductions --- Slides|
examples of using reductions to prove undecidability or
unrecognizability; Post's Correspondence Problem.
||Sipser §5.2.||No tutorial this week||Wed: A3 due, A4 posted
|Rice's theorem; more reductions. The recursion theorem and some applications.||Sipser §6.1.||Practice with reductions --- Slides||Fri: A4 due
|Feb 20||Reading Week (no lectures or office hours but midterm test on Saturday!)||Sat: Midterm test|
|Introduction to computational complexity; running time of Turing machines; the "polynomial time thesis", the complexity classes P and NP.||Sipser §7.1-7.2 (Theorem 7.16 optional)||No tutorial this week|
|Alternative characterization of NP; polynomial time (Turing and mapping) reductions; the satisfiability problem; NP completeness; decision, search, and optimization problems, self-reducibility.||Sipser
§7.3-7.4 (up to page 304).
||No tutorial this week||Wed: A5 posted|
|Cook-Levin theorem: NP completeness of SAT and 3-SAT; NP completeness of the independent set, clique, and vertex cover problems.||Sipser §7.4-7.5 (pp. 304-313).||No tutorial this week|| Wed: A5 due, A6 posted
|More NP-complete problems: Hamiltonian cycle in directed and undirected graphs, traveling salesman problem, 3-dimensional (tripartite) matching, exact cover by 3-sets, exact cover, subset sum, partitioning, zero-one linear programming, integer linear programming.||Sipser §7.5 (pp. 313-322).||No tutorial this week||Wed:
Fri: A7 posted
|Coping with NP-completeness. The time complexity class coNP. The polynomial time hierarchy.||No tutorial this week|
|Space complexity. Savitch's theorem. Relationships between time and space complexity classes. PSPACE completeness.||Sipser §8.1-8.3.
||No tutorial this week||Fri:
Back to the index
Academic integrity: Academic integrity is essential to the University of Toronto and so the University treats cases of cheating and plagiarism very seriously. Academic offences relevant to this course include using someone else's ideas or words without appropriate attribution; obtaining or providing unauthorized assistance on any assignment, test, or exam; misrepresenting your identity; and falsifying or altering documentation.
Accessiblity: If you have a disability or health condition that may require accommodation, please consult with AccessAbility Services (AA142, 416-287-7560, email@example.com) as soon as possible. Enquiries to AccessAbility Services are confidential. Its staff will help assess needs and, if appropriate, will provide referrals and arrange accommodations.
will be up to eight homework assignments (not necessarily of equal weight)
worth in total 40% of the course grade, a midterm test worth 20% of the
course grade, and a final exam worth 40% of the course grade. A
grade of at least 40% on the final
exam is required to pass the course.
Homework grading: For each homework assignment, we may grade only a selected (but not preannounced) subset of the questions. In that event, the homework assignment will be graded out of the total weight of the selected questions.
Late homework policy: No late homeworks will be accepted. If you miss a homework deadline because of a medical or personal exigency, you must fill out and send to the course instructor the Special Consideration Form as soon as possible. If the reason for missing the deadline is acceptable, the weight of the missed homework will be shifted to other components of your grade.
Homework collaboration policy: In each homework assignment you may collaborate with at most one other student who is currently taking CSCC63. If you collaborate with another student on an assignment, you and your partner must submit only one copy of your solution, with both of your names. The solution will be graded in the usual way and both partners will receive the same grade. Collaboration involving more than two students is not allowed. For help with your homework you may consult only the instructor, TAs, your homework assignment partner (if you have one), your textbook, and your class notes. You may not consult any other source.
submit a regrading request for an assignment or the midterm test you must
fill out, in plain text, this form
and email it to the course instructor no later than one week from the date
the graded assignment or test was made available to the class. (This
period may be shorter for the last assignment, to ensure timely delivery
of course grades.) Regrading requests made after the deadline will
not be accepted. As a result of a regrading request your grade in
the assignment may increase, remain unchanged, or decrease.
Regrading requests consume a large amount of the instructor's and TAs'
time, both of which are in short supply. Before making a
regrading request, you must read and understand the provided solutions and
think carefully about your own solution. To discourage frivolous
regrading requests we will apply the following rule: A regrading
request that does not result in increasing the grade of the
submitted assignment causes a ``demerit'' to each of the student(s) who
submitted the assignment in question.
We will not consider regrading requests for an assignment submitted by a
student who has accumulated two such demerits.
Missed midterm test policy: If you miss the midterm test due to a medical or personal exigency, get in touch with your instructor immediately, and fill out the Special Consideration Form. There will be no make-up test, but if the reason for missing the test is acceptable, the weight of the missed midterm test will be shifted to the final examination.
Back to the index
Back to the index