Lectures, Course Outline, and Learning Objectives

Key to ASCII notation

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.
    Readings: section 3.2.
  3. Week 3 tutorial exercises / Week 3 tutorial solutions
    Week 3 lecture notes
    Readings: sections 3.3, 4.2.
  4. Week 4 tutorial exercises / Week 4 tutorial solutions Week 4 lecture notes
    Readings: sections 4.2, 5.1.
  5. Week 5: no tutorial because of Term Test 1
    Week 5 lecture notes
    Readings: sections 5.1, 5.3.
  6. Week 6 tutorial exercises / Week 6 tutorial solutions
    Week 6 lecture notes
    Readings: problem 5.28, section 7.1.
  7. Week 7 tutorial exercises / Week 7 tutorial solutions
    Week 7 lecture notes
    Readings: sections 7.1, 7.2, 7.3.
  8. Week 8 tutorial exercises / Week 8 tutorial solutions
    Week 8 lecture notes
    Readings: section 7.4.
  9. Week 9: no tutorial because of Term Test 2
    Week 9 lecture notes
    Readings: section 7.5.
  10. Week 10 tutorial exercises / Week 10 tutorial solutions
    Week 10 lecture notes
    Readings: section 7.5.
  11. Week 11 tutorial exercises / Week 11 tutorial solutions
    Week 11 lecture notes
    Readings: sections 8.1, 8.2, 8.4 (and start of Chapter 8).
  12. Week 12 tutorial exercises / Week 12 tutorial solutions
    Week 12 lecture notes
    Readings: section 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.

Learning objectives

By the end of this course, students should