CSCC63 -- Computability and computational complexity

Winter 2022


Index of this document


Contact information and meeting times

Instructor:  Vassos Hadzilacos
Office hours:  Mon and Wed 2:30-3:30pm, or by appointment (on Zoom link provided in the initial email to students, or in person in my UTSC office when the campus is open)
Office:  IC 486 (Scarborough campus);  SF 2304B (St. George campus)
Telephone:  416-287-7256 (Scarborough campus);  416-978-6028 (St. George campus)
Email:  vassos@cs.toronto.edu
TAs:  Jackson Han, Richard Hong, Xing Hu, Joey Lakerdas-Gayle

Office hours: (starting Week 1 for Vassos and Week 2 for the TAs, on Zoom links provided by email to students)


Day Time Person
Mon 1-2 Jackson
2:30-3:30 Vassos
5-6 Richard
Tue 11-12 Xing
5-6 Joey
Wed 11-12 Xing
2:30-3:30
Vassos

Course web page:  http://www.cs.toronto.edu/~vassos/teaching/c63/

Course forum page:  https://www.piazza.com/utoronto.ca/winter2022/cscc63

Lecture times and locations:  LEC01: Mon 12-1pm (IC 220) and Wed 12-2pm (IC 220); LEC02: Mon 11am-12noon (IC 220) and Wed 9-11am (MW 140).  Weeks 1-4 will be on-line asynchronous.

Tutorial times and locations:  TBA 

Back to the index


Course content

Course goals:   To introduce the elements of the theory of computability and computational complexity.

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): 

Speak, then, and tell everything.  For, it comforts those in pain
To know before hand all the agony they still must bear.
--Aeschylus, Prometheus Bound




Week
Lecture topics
Study materials Tutorials
Assignments & tests
Week 1
Jan 9
Paradoxes; cardinality of infinite sets; informal introduction to computability. Lecture 1 video (Quercus).

Sipser, the Diagonalization Method (pp. 202-207).
Notes on countable sets.
No tutorial this week Wed: A1 posted
Week 2
Jan 16
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
Week 3
Jan 23
Nondeterministic TMs; Church's thesis, universal TM; undecidability of the universal language, unrecognizability of its complement. Lecture 3 video (Quercus).

Sipser pp. 178-180,  4.2.
No tutorial this week Wed: A2 due, A3 posted

Week 4
Jan 30
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
Week 5
Feb 6
More 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
Week 6
Feb 13
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
Week 7
Feb 27
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
Week 8
Mar 6
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
Week 9
Mar 13
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
Week 10
Mar 20
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: A6 due
Fri: A7 posted
Week 11
Mar 27
Coping with NP-completeness. The time complexity class coNP. The polynomial time hierarchy.
No tutorial this week
Week 12
Apr 3
Space complexity. Savitch's theorem. Relationships between time and space complexity classes. PSPACE completeness. Sipser 8.1-8.3.
No tutorial this week Fri: A7 due


Back to the index


Course policies

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

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.

Back to the index


Course documents

In this space we will make available course documents in PDF.

Back to the index


Course forum

We will use Piazza as the platform for class announcements and discussions.  This service is free to use, but requires registration.

To register, follow the link below and provide the access code provided in the initial email to students.  You must use your real name and your @mail.utoronto.ca or @utoronto.ca address as your email contact when you register in Piazza.  If you have privacy concerns about this, please contact the instructor to discuss alternatives.  The bottom line is that we must be able to identify any individual on the forum as a student registered in the course; individuals for whom this is not the case may be removed from the class forum without warning.

The URL of the CSCC63 Piazza page is:  https://www.piazza.com/utoronto.ca/winter2022/cscc63.

Guidelines for posting on Piazza:


Document maintained by Vassos Hadzilacos