CSC 363: Computational Complexity and Computability (Jan-Apr 2010)

You can come by my office in PT 290E on Friday, May 7, from 1:00 to 1:30 to pick up any assignments or tests that you haven't picked up yet.

Instructor:

Radford Neal, Office: PT290E / SS6026A, Phone: (416) 946-8482 / (416) 978-4970, Email: radford@cs.utoronto.ca

Office hours:

Mondays from 4:30 to 5:30 and Thursdays from 12:10 to 1:00.
Office hours will be held in PT 290E. Office hours continue until the exam.

Lectures:

Wednesdays, 7:10pm to 9:00pm, from January 6 to March 31, except February 17 (Reading Week). Held in BA 1210.

Tutorials:

Wednesdays, 6:10pm to 7:00pm, from January 13 to March 31, except February 17 (Reading Week).

NOTE: Tests will be held during the tutorial time, so you must not have a time conflict with the tutorial.

There are two tutorial sections. Please go to the section in the room as indicated below:

BA 1210: For students with last names starting from A to L
BA 3012: For students with last names starting from M to Z
The tutorial section you are in will not affect who marks your tests or assignments.

Textbook:

Michael Sipser, Introduction to the Theory of Computation, second edition.

A list of errata for this edition is available at http://www-math.mit.edu/~sipser/itoc-errs2.1.html

Evaluation:

All assignments (short and long) are to be done by each student individually.

Requests for assignments or tests to be remarked must be made in writing to the instructor (not the tutors) within one month of the work being returned.

Accomodating illness and other special circumstances:

If due to illness or other serious personal difficulties, you are unable to complete an assignment on time, or unable to write one of the tests, you should contact the instructor as soon as possible. For tests and short assignments, accomodation will be by taking that portion of the mark from other work. For long assignments, you may be allowed to hand in the assignment up to one week late; if that is not possible, that portion of the mark will be taken from other work.

Note that for the final exam, accomodation for illness or other difficulties is handled officially through your college/faculty, not by the instructor.

Assignments:

Short Assignment #1: handout, answer.
Short Assignment #2: handout, answer.

Long Assignment #1: handout, answers.

Short Assignment #3: handout, answer.
Short Assignment #4: handout, answer.

Long Assignment #2: handout, answers.

Tests:

Test #1: test paper, answers. Test #1 was marked out of a total of 100 possible marks, but will be considered as if it were out of 90 in computing course marks.

Test #2: test paper, answers. Test #2 was marked out of a total of 100 possible marks, but will be considered as if it were out of 80 in computing course marks.

Topics covered in lectures and tutorials:

Tutorial   Lecture
Jan 06 DFA, NFA & RE, and their equivalence (Chapter 1)
Jan 13 Non-determinism in FA Brief look at PDAs (Chapter 2)
Turing Machines (Chapter 3 through page 149)
Jan 20 Robustness of TM model Nondeterministic TM, Enumerators, Church-Turing Thesis (Chapter 3)
Acceptance problems (Chapter 4 to page 167)
Jan 27 Recognizing vs. deciding Acceptance, emptyness, and equality problems (Section 4.1)
The Halting Problem (Section 4.2)
Feb 03 TEST #1 Answers to test questions
Reductions, emtpyness problem for TM (Section 5.1)
Feb 10 Examples relating to
long assignment #1
Linear bounded automata, computation histories
computable functions, mapping reductions (Section 5.1 and 5.3)
Feb 17
Feb 24 Post Correspondence Problem
(Section 5.2)
Time complexity, classes P and NP
polynomial time reductions (Sections 7.1 to 7.3)
Mar 03 Solutions to long assignment #1 Verifiers, NP completeness
Intro to Cook-Levin Thm (Sections 7.3 and 7.4)
Mar 10 Solution to short assignment #3
Examples of showing NP-completeness
Proof of the Cook-Levin Thm (Section 7.4)
Showing 3-SAT and VERTEX-COVER are NP-complete
Mar 17 TEST #2 The class coNP, Space complexity (Start of Ch. 8)
Mar 24 Facts about coNP Savitch's Theorem, PSPACE=NPSPACE
PSPACE-completeness, log space (Sections 8.1-8.4)
Mar 31 Languages in L NL completeness (Section 8.5), Brief looks at
Circuit Complexity (Section 9.3 and 10.5) and
Oracles (Section 9.2)

Web pages for a past version of this course:

CSC 363, Fall 2009, F. Pitt.