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

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.

  1. Week 1 tutorial notes / Week 1 lecture notes
    Readings: section 1.2 (and review chapters 0 as needed).
  2. Week 2 tutorial notes (now with sample solutions) / Week 2 lecture notes
    Readings: sections 1.3, 4.2.
  3. Week 3 tutorial notes (now with sample solutions) / Week 3 lecture notes
    readings: sections 4.1, 4.3, 1.1.
  4. Week 4 tutorial notes (now with sample solutions) / Week 4 lecture notes
    readings: sections 3.1, 3.2.
  5. Week 5: no tutorial because of Term Test 1
    Week 5 lecture notes
    Additional notes on induction
    readings: sections 3.2, 3.3.
  6. 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.
  7. 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.
  8. Week 8 tutorial notes (now with sample solutions) / Week 8 lecture notes
    readings: section 2.6.
  9. Week 9: no tutorial because of Term Test 2
    Week 9 lecture notes
    readings: sections 7.1, 7.2, 7.3.
  10. Week 10 tutorial notes (now with sample solutions) / Week 10 lecture notesupdated at 13:03 on Fri 27 Nov
    readings: section 7.2, 7.3, 7.4.
  11. Week 11 tutorial notes (now with sample solutions) / Week 11 lecture notes
    readings: section 7.5, 7.6, 7.7, 8.1.
  12. 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, well-ordering, structural). Chapters 1,4. [3 weeks]
  • Algorithm complexity and recurrence relations. Chapter 3. [2 weeks]
  • Algorithm correctness. Chapter 2. [2 weeks]
  • Regular languages, finite-state automata, and regular expressions. Chapter 7. [2 weeks]
  • Context-free languages, context-free 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 non-linear 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 finite-state automata (FSAs),
      • know the equivalence of regexps and FSAs,
      • be aware of the limitations of regular languages,
    • understand the concept of context-free languages:
      • know context-free grammars (CFGs),
      • know pushdown automata (PDAs),
      • know the equivalence of CFGs and PDAs,
      • be aware of the limitations of context-free languages.