Office hours: Held at the times and locations indicated in the table below. Vassos's office hours start on Week 1; TAs' office hours start on Week 2.
| Day | Time | Place | Person |
| Mon |
2:30-3:30 | IC486 | Vassos |
| 4:00-5:00 | IC402 - Table 1 | Sasha | |
| Tue |
11:00-12:00 | IC402 - Table 1 | Ananya |
| 12:00-1:00 | IC402 - Table 1 | Malhar |
|
| Wed |
2:30-3:30 | IC486 |
Vassos |
| 5:00-6:00 | IC402 - Table 1 | Ian |
Course web page: http://www.cs.toronto.edu/~vassos/teaching/c63/
Course forum page: https://piazza.com/utoronto.ca/winter2024/cscc63h3slec01/home
Tutorial times and locations: TUT01: Thu 3-4pm (SW 319), TUT02: Thu 5-6pm (HW 215)
Prerequisites: CSCB63 (and, transitively but importantly, 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.
Textbook: Sipser. Introduction to the theory of computation (3rd edition). Cengage Learning 2013.
Tentative weekly schedule (check regularly as it may change):
| Week
|
Lecture
topics |
Study materials | Tutorials
|
Assignments
& tests |
| Week 1 Jan 7 |
Paradoxes; cardinality of infinite sets; informal introduction to computability. | Sipser, the Diagonalization Method (pp. 202-207). Slides used in Mon lecture (paradoxes). Notes on countable sets. |
No tutorial this week | Wed: A1 posted |
| Week 2 Jan 14 |
Turing machines; recognizable (recursively enumerable) and decidable (recursive) languages; Turing machine variants (multitape TMs). | Sipser Ch 3 (excluding Nondeterministic TMs, pp. 178-180). Slides used in Mon lecture (TM for even-length palindromes). Notes on the yields relation and on TMs as function computers. |
Practice with Turing machines, recognizable and decidable languages — Slides | Wed: A1 due, A2 posted |
| Week 3 Jan 21 |
Nondeterministic TMs; Church's thesis, universal TM; undecidability of the universal language, unrecognizability of its complement. | Sipser pp. 178-180, §4.2. Slides used in Mon lecture (NTM example and simulation by DTM) and notes on the running time of the simulation. Notes on Church's thesis and the Universal Turing machine. Slides used in Wed lecture (Universal TM). |
More practice with Turing machines, recognizable and decidable languages — Slides | Wed: A2 due, A3 posted |
| Week 4 Jan 28 |
The halting problem; mapping reductions and Turing reductions; using reductions to prove undecidability or unrecognizability of languages. | Sipser §5.1 (pp. 221-226 optional), 5.3, 6.3 Notes on reductions. |
No tutorial this week | Wed: A4 posted, A3 due |
| Week 5 Feb 4 |
Rice's theorem; more examples of using reductions to prove undecidability or unrecognizability. The recursion theorem and some applications. |
Notes on Rice's theorem. Sipser §6.1. |
Practice with reductions — Slides | |
| Week 6 Feb 11 |
The arithmetic hierarchy: the world beyond recognizable and co-recognizable languages. | Notes on the arithmetic hierarchy. | No tutorial this week | Wed:
A4 due |
| Feb 19 |
Reading
Week (no lectures or office hours) |
|||
| Week 7 Feb 25 |
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). Notes on a decidable language that is not in P. |
Q & A on computability (for upcoming midterm). | Fri: Midterm test |
| Week 8 Mar 3 |
Alternative characterization of NP; polynomial time (Turing and mapping) reductions; the satisfiability problem; NP completeness; Cook-Levin theorem: NP completeness of SAT and CNF-SAT. | Sipser §7.3-7.4. Slides used in Mon lecture. Notes on the Cook-Levin theorem. |
Review of midterm test answers. |
Wed: A5 posted |
| Week 9 Mar 10 |
NP completeness of the 3-SAT, independent set, clique, and vertex cover problems. More NP-complete problems: 3D matching, exact cover, subset sum, partitioning. | Sipser §7.5. Notes on 3D matching. Slides used in Wed lecture. Notes on proving NP-completeness. |
Practice with satisfiability — Slides | Wed: A5 due, A6 posted |
| Week 10 Mar 17 |
Even more NP-complete problems: colourability, interger linear programming, Hamiltonian cycle in directed and undirected graphs, traveling salesman problem. Decision, search, and optimization problems; self-reducibility. | Sipser §7.5. Notes on colourability. Notes on Hamiltonian cycle. Notes on self-reducibility. Slides used in Wed lecture. |
No tutorial this week | Wed: A6 due, A7 posted |
| Week 11 Mar 24 |
The time complexity class coNP. The polynomial time hierarchy. Space complexity. Savitch's theorem. |
Notes on coNP and the polytime hierarchy. Sipser §8.1. |
Practice with NP-completeness — Slides | |
| Week 12 Mar 31 |
Relationships between time and space complexity classes. PSPACE completeness. | Sipser §8.2-8.3. Slides used in Wed lecture (exampe of reduction of Geography to TQBF). |
No tutorial this week | Wed: A7 due |
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, ability@utsc.utoronto.ca) 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.
Evaluation: There 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 pre-announced) subset of the questions or parts thereof. In that event, the homework assignment will be graded out of the total weight of the graded part of the assignment.
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. 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.
Regrading policy: To 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.