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' = q_{1}
 '^' indicates a superscript, e.g.,
'n^2' = n^{2}
 curly braces '{}' surround longer subscripts/superscripts,
e.g.,
'\sum_{0 <= i <= n} 2^{i/2}' =
∑_{0 ≤ i ≤ n}
2^{i/2}
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.
When these files are in plain text (ASCII),
they will use the notation listed above
for mathematical symbols.
 Week 1 lecture notes
Readings: section 3.1
(and review chapters 0, 1, 2 as needed).
 Week 2 lecture notes
Readings: sections 3.2, 3.3.
Formal details of the equivalence
between regular TMs and 2way infinite TMs.
 Week 3 lecture notes
readings: sections 3.3, 4.2.
 Week 4 lecture notes
readings: sections 4.2.
 Week 5 lecture notes
readings: section 5.1.
 Week 6 lecture notes
readings: section 5.3, problem 5.28.
 Week 7 lecture notes
readings: sections 7.1, 7.2.
 Week 8 lecture notes
readings: sections 7.2, 7.3, 7.4.
 Week 9 lecture notes
readings: sections 7.4, 7.5.
 Week 10 lecture notes
readings: section 7.5.
 Week 11 lecture notes
readings: sections 8.1, 8.2, 8.4.
 Week 12 lecture notes
readings: sections 8.3, 8.5, 9.1.
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 ChurchTuring 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, NPcompleteness
(section 7.4)
 Cook's theorem, more NPcompleteness
(section 7.5)
 Selfreducibility
(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
