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 should read these sections
to prepare for the following week's lectures and tutorials.
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 tutorial notes
/ Week 1 lecture notes
Readings: section 1.2 (and review chapters 0 as needed).
 Week 2 tutorial notes
(now with sample solutions) /
Week 2 lecture notes
Readings: sections 1.3, 4.2.
 Week 3 tutorial notes
(now with sample solutions) /
Week 3 lecture notes
readings: sections 4.1, 4.3, 1.1.
 Week 4 tutorial notes
(now with sample solutions) /
Week 4 lecture notes
readings: sections 3.1, 3.2.
 Week 5: no tutorial because of Term Test 1
Week 5 lecture notes
Additional notes on induction
readings: sections 3.2, 3.3.
 Week 6 tutorial notes
(now with sample solutions) /
Week 6 lecture notes
updated at 09:56 on Tue 20 Oct
readings: sections 2.1, 2.2, 2.7, 2.8.
 Week 7 tutorial notes
(now with sample solutions) /
Week 7 lecture notes
Additional example of
iterative correctness.
readings: sections 2.3, 2.4, 2.5.
 Week 8 tutorial notes
(now with sample solutions) /
Week 8 lecture notes
readings: section 2.6.
 Week 9: no tutorial because of Term Test 2
Week 9 lecture notes
readings: sections 7.1, 7.2, 7.3.
 Week 10 tutorial notes
(now with sample solutions) /
Week 10 lecture notes—updated
at 13:03 on Fri 27 Nov
readings: section 7.2, 7.3, 7.4.
 Week 11 tutorial notes
(now with sample solutions) /
Week 11 lecture notes
readings: section 7.5, 7.6, 7.7, 8.1.
 Week 12 tutorial notes
(now with sample solutions) /
Week 12 lecture notes
readings: section 8.2, 8.3, 8.5.
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.
 Induction (simple, complete, wellordering, structural).
Chapters 1,4. [3 weeks]
 Algorithm complexity and recurrence relations.
Chapter 3. [2 weeks]
 Algorithm correctness.
Chapter 2. [2 weeks]
 Regular languages, finitestate automata, and regular expressions.
Chapter 7. [2 weeks]
 Contextfree languages, contextfree grammars, and pushwon automata.
Chapter 8. [2 weeks]
Learning objectives
By the end of this course, students should...
 understand induction and be able to use its various forms
(simple, complete, structural);
 understand how to state and prove the correctness of algorithms,
including basic complexity analysis:
 be able to write preconditions and postconditions,
 be able to write and prove loop invariants,
 be able to prove properties of recursive algorithms,
 understand clearly the difference between upper and lower bounds
on algorithm complexity,
 be able to setup recurrence relations for
the running time of recursive algorithms,
 be able to solve general recurrence relations,
including simple nonlinear examples;
 understand basic properties of languages:
 know the formal definition of a language and related concepts
(strings, alphabets, etc.),
 understand the concept of regular languages:
 know regular expressions (regexps),
 know finitestate automata (FSAs),
 know the equivalence of regexps and FSAs,
 be aware of the limitations of regular languages,
 understand the concept of contextfree languages:
 know contextfree grammars (CFGs),
 know pushdown automata (PDAs),
 know the equivalence of CFGs and PDAs,
 be aware of the limitations of contextfree languages.
