# Lectures, Course Outline, and Learning Objectives

### Key to ASCII notation

• '{}' = ∅ = "empty set"
• '(-' = ∈ = "element of"
• '(_' = ⊆ = "subset of" (not strict)
• 'u' = ∪ = "union"
• 'n' = ∩ = "intersection"
• '~L' = L = "complement of L"
• '-]' = ∃ = "there exists"
• '\-/' = ∀ = "for all"
• '/\' = ∧ = "and"
• '\/' = ∨ = "or"
• '->' = → = "implies"
• '<->' = ↔ = "if and only if (iff)"
• '!' = ¬ = "not", e.g., 'a != b' = a ≠ b = "a is not equal to b", 'w !(- L' = w ∉ L = "w is not an element of L", etc.
• '\sum' = ∑ = summation sign
• '\prod' = ∏ = product sign
• '\Sigma' = Σ = capital greek letter Sigma, '\delta' = δ = lowercase greek letter delta, etc.
• '|_x_|' = ⌊x⌋ = floor(x)
• '|^x^|' = ⌈x⌉ = ceiling(x)
• '_' indicates a subscript, e.g., 'q_1' = q1
• '^' indicates a superscript, e.g., 'n^2' = n2
• curly braces '{}' surround longer subscripts/superscripts, e.g., '\sum_{0 <= i <= n} 2^{i/2}' = ∑0 ≤ i ≤ n 2i/2

## Tutorial notes and Lecture summaries

Every week, specific sections of the textbook will be posted as readings. You will be expected to read these sections to prepare for the following week's lectures.

At the end of each week, a short summary of the material covered during tutorials and lectures will be posted, along with some tutorial exercises to test your understanding of that week's material. These exercises will be discussed during the following week's tutorial.

When these files are in plain text (ASCII), they will use the notation listed above for mathematical symbols.

1. Week 1 tutorial exercises / Week 1 tutorial solutions (with important notes for students and TA's)
Week 1 lecture notes
Readings: review chapters 0, 1, 2; section 3.1.
2. Week 2 tutorial exercises / Week 2 tutorial solutions
Week 2 lecture notes / Formal details of the equivalence between regular TMs and 2-way infinite TMs.
3. Week 3 tutorial exercises / Week 3 tutorial solutions
Week 3 lecture notes
4. Week 4 tutorial exercises / Week 4 tutorial solutions
Week 4 lecture notes
5. Week 5: no tutorial because of Thanksgiving
Week 5 lecture notes
6. Week 6 tutorial exercises / Week 6 tutorial solutions
Week 6 lecture notes
7. Week 7 tutorial exercises / Week 7 tutorial solutions
Week 7 lecture notes
8. Week 8 tutorial exercises / Week 8 tutorial solutions
Week 8 lecture notes
9. Week 9: no tutorial because of Fall Break
Special Guest Lecture by Prof. Stephen Cook, on Friday!
10. Week 10 tutorial exercises / Week 10 tutorial solutions
Week 10 lecture notes
11. Week 11 tutorial exercises / Week 11 tutorial solutions
Week 11 lecture notes
Readings: sections 8.1, 8.2 (and start of Chapter 8).
12. Week 12 tutorial exercises / Week 12 tutorial solutions
Week 12 lecture notes
Readings: sections 8.3 (for the examples), 9.1.
13. Week "13": no tutorial—lecture instead at the usual time and place (Mon 6 Dec, 2-3pm, BA 1220)
Week 13 lecture notes
See the Tests/Exam page for advice about studying for and writing the final exam.

## Course outline

### Lecture topics

The following topics will be covered in this course, in the order listed. For each topic, we have indicated the approximate number of weeks required to cover that topic as well as a list of the relevant sections in the textbook.

• Computability Theory [5 weeks]
(Chapters 3, 4, 5 in the textbook)
• Turing machines: definitions and examples (section 3.1)
• Other models of computation, the Church-Turing thesis (sections 3.2, 3.3)
• Diagonalization, the Halting problem (sections 4.1, 4.2)
• Decidability and recognizability, examples (sections 4.2, 5.1)
• Reducibility, examples (sections 5.1, 5.2)
• Mapping reducibility, examples (section 5.3)
• Complexity Theory [7 weeks]
(Chapters 7, 8, and parts of 9, 10 in the textbook)
• Models of efficient computation (sections 7.1, 7.2)
• P, NP, coNP, examples (section 7.2, 7.3)
• Polytime reducibility, NP-completeness (section 7.4)
• Cook's theorem, more NP-completeness (section 7.5)
• Self-reducibility (not in textbook)
• Space complexity and other complexity classes (sections 8.1, 8.2, 8.3, 9.1, 10.1)

### Learning objectives

By the end of this course, students should

• be familiar with fundamental restrictions on computability:

• be familiar with Turing machines;
• understand the notions of decidability and semi-decidability;
• know that the Halting problem is undecidable;
• understand and be able to apply techniques for showing undecidability (diagonalization, reductions);
• understand the importance of computational complexity:

• be familiar with the definitions of P and NP;
• be able to demonstrate membership in P or NP;
• be familiar with the definition of NP-completeness;
• be able to apply techniques for showing NP-completeness;
• know other standard complexity classes (L, PSPACE, EXP), and be able to demonstrate membership in those classes.