Computation Theory

Supervision Work

• Supervision 1 (pdf, code)
  Exercises: 7, 9, 10, 13, 14, 15, 18, 19, 21, 22, 23, 24, 25, 27, 28, 32, 34, 36
  Optional: 8
• Supervision 2 (pdf)
  Exercises: 1, 5, 6, 7, 8, 9, 17, 18
  Optional: 11, 19, 20
• Supervision 3 (pdf)
  Exercises: 3, 5(c), 8, 9, 10, 13, 17, 19, 21, 23, 24, 27, 28, 31
  Optional: 11, 20

Past papers

• Past papers categorised by topic (pdf)

Projects

Under construction (these are currently only ideas, but feel free to try one of these)

If you are interested in going in more depth in some aspects of the course, then you might want to look at these projects. If you email me, I can give you hints and further references. Do let me know if you attempt one of this, even if you have a partial solution.

• Choose any topic that you find interesting from these lecture notes.
• Choose any topic that you find interesting from Computability: An introduction to recursive function theory or Lambda-calculus and combinators
• (Draft) Projects (html)

Solution Notes

Do not look at the solution notes before giving serious thought to the exercises.

• Supervision 1 (pdf)
• Supervision 2 (pdf)
• Supervision 3 (pdf)

Dima Szamozvancev has also written solution notes for many of the core exercises.

Further resources

• Foundations of functional programming (lecture notes)
• “Computability: An introduction to recursive function theory” by N. Cutland
• “Lambda-calculus and combinators an introduction” (2nd ed.) by R. Hindley and J. Seldin
• “Problems in Set Theory, Mathematical Logic and the Theory of Algorithms” (Chapter 3) by Igor Lavrov and Larisa Maksimova