**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 youmust nothave 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 LThe tutorial section you are in will not affect who marks your tests or assignments.

BA 3012: For students with last names starting from M to Z

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

- Four short assignments worth 4% each (16% total)
Due (without exception) atstartof tutorial on Jan 20, Jan 27, Mar 10 (changed from Mar 3), and Mar 17 (changed from Mar 10). Answers will be immediately be reviewed in tutorial or lecture.- Two long assignments worth 12% each (24% total)
Due at start of tutorial Feb 24 and ar 31 (changed from Mar 24). Handed out three weeks before due. Answers reviewed posted one week after due. You may hand in up tooneof the assignments up tooneday late (ie, 6pm Thursday) without explanation. Other late assignments will be accepted only with a valid excuse (see below).- Two tests worth 10% each (20% total)
Held in tutorial times Feb 3 and Mar 17. Answers will immediately be reviewed in the lecture that follows.- Final exam worth 40%
This has now been scheduled by the Faculty of Arts and Science, the exam rules and schedule are here. The final exam will cover material from the whole course.You must receive at least 40% on the final exam to pass the course.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 instructoras 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 #1Linear 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-completenessProof of the Cook-Levin Thm (Section 7.4)

Showing 3-SAT and VERTEX-COVER are NP-completeMar 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.