COMP11212: Fundamentals of Computation

Semester 2, 2020/2021

Sean Bechhofer (Part 1) & Gareth Henshall (Part 2)

Learning Outcomes

On successful completion of this unit, a student will be able to:

  1. Describe formal languages using a variety of mechanisms;
  2. Define classes of languages and demonstrate translations between those classes;
  3. State key properties of classes of languages and determine when those properties hold;
  4. Define models of computation and use those models to demonstrate what can and cannot be computed;
  5. Produce program specifications and proofs of program correctness;
  6. Describe computational complexity and identify the complexity of programs.

The learning outcomes will assessed by coursework and exam.

Reading List

Detailed notes will be distributed, but the following texts may also be useful. All can be found in the University library.

  • Introduction to the Theory of Computation (3rd Edition), Michael Sipser. CENGAGE Learning. ISBN 1-13318781-1.
    An electronic version of this textbook should be available via the Blackboard site.
  • Introduction to Automata Theory, Languages, and Computation. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman
  • Logic in Computer Science: modelling and reasoning about systems. Michael Huth and Mark Ryan.


There is an area on the University's Blackboard Site for the course with links to video content, notes, weekly schedules, online exercises and associated resources. This has a discussion list that can be used to raise any questions you might have about the material. Please avoid discussing the specifics of assessed work (at least not until after solutions are published)

Please do not redistribute the notes. More importantly, please do not redistribute the solutions published on Blackboard.


See Blackboard for a detailed week by week schedule.

Asynchronous content is available via the University's Video system.

Part 1

Part 1 covers Weeks 1—5 and is taught by Sean Bechhofer.


Almost every time we use a computer the computer must make sense of what we type into it. How does it do that? How does a computer take a computer program and break it down so that it can be turned into instructions the computer can actually carry out? How can we search documents or webpages for fairly complicated pieces of text, such as all occurrences of a double typed word ("the the", for example), even across line breaks, arbitrary amounts of space, and with the first letter possibly capitalized? How can we make use of tools such as grep?

In this part of the course we study techniques that help us deal with such issues. We look at different ways of describing collections of strings, and how to transform one description into another. We also look at what these descriptions can and can't do.

Exercise Sheets for Part I

Exercise sheets (both formative and summative) for Part I can be found on Blackboard. Solutions will also be published there after the examples classes.

Corrections and Clarifications

We are all fallible. A list of any errors and corrections to the distributed notes will be available here.

Course notes

The notes (available from Blackboard), including the exercises, cover all the examinable material for this part of the course. I appreciate any feedback on the course in general as well as on the material handed out. For this purpose please email me at sean.bechhofer at

The notes are written in a fair amount of detail because you are expected to spend some time each week in self-study. I will not explain every detail that appears in the notes in the lectures. The lectures are there for me to introduce the big ideas, and to go through examples with you.

The notes also contain organizational information at the beginning, including a description of the format of the exam.

Solutions to marked examples will be published on Blackboard.

The material for this part of the course is mathematical in nature. There is an Appendix in the notes that with a more rigorous treatment of the material. This material is examinable, but at most 10% of the final mark depends on it. Most students choose not spend time on this part, and that is fine, but if you are interested in theoretical computer science then you should work through it.

Part 2

Part 2 of the unit runs from weeks 6—10 and is taught by Gareth Henshall.


The second half of the course (10 lectures) provides an introduction to the topics of computability, complexity, and correctness.

The notes provide a detailed introduction to the topics being covered and recommended reading.

Course notes

The notes for this part contain all the examinable material for this part of the course. If you spot a mistake please email me at I will update the notes with corrections as they are found.

The style of this part is the same as Part I i.e. you are expected to spend time reading the notes and I will not cover every detail that appears in the notes in the lectures.

Exercise Sheets for Part II

Exercises for the examples classes will be posted here (they are not in the notes) and solutions will be posted on Blackboard.

External resources. In the past some students have shared some websites that they have found useful/interesting. Please send anything you find useful to me to put here:


Some previous students have built some tools to help understand the material:

  • This tool is a Java tool for exploring operational semantics, correctness proofs, and Godel encodings of while programs. If you want to help improve the tool then let me know. It's quite big as it contains a theorem prover for checking constraints in correctness proofs. (Requires Java 8)
  • This tool is an interpreter for the while language written in C.
You are not required to use any of these tools but they may help. If you develop anything you want to share then please let me know and I'll add it here.

General Organisation


There are a number pieces of assessed work for this course. Much of it is formative: you will get some feedback and possibly a mark, but this mark will not contribute towards the final grade for the unit. But the formative assessments will enable you to track your understanding of the materials and topics. You are strongly encouraged to do these assessments. It is through practice that we can acquire skills.

In addition to the formative assessments, there will be some summative assessments. For these, you will be given marks (and feedback) and the mark will contribute towards your grade for the unit. The coursework forms 20% of the assessment, with the remaining 80% being the exam.

Coursework will consist of both online Blackboard quizzes and pencil and paper exercises. Formative exercises will be marked in the examples classes -- where you can also get assistance from GTAs.

The notes also contain a number of exercises that serve as preparation for the marked work. You could also choose to leave some of these exercises for revision.

The point of the examples classes is to

  • provide you with feedback for the work that you have done;
  • help you with the exercises you couldn't do.

Examples Classes

You're expected to complete any summative work individually. Please do not be tempted to plagiarise or submit work which is not your own. Offences of plagiarism (or any other academic malpractice) are taken very seriously by the University and if found guilty the penalties can be severe. Passing others' work off as your own also has little benefit in terms of your understanding of the materials.

Attendance at Examples Classes

Past experience proves the case for attendance at examples classes convincingly: Students who do the set work in each week will pass the exam. On the other hand 90% of students who failed the exam in previous years either failed the coursework or failed to even attend more than 50% of examples classes.


Exam Format

  • The exam will be a "hybrid" exam with a mixture of online and paper questions. It will cover both parts of the course, with online and paper questions for both Part I and Part II .
  • You must answer all parts of all questions.
  • The exam makes up 80% of the final mark, the coursework 20%.

The department keeps a wealth of information on exams, when they are, how to prepare for them, where to find old exam papers (where they exist), etc, here.

Past Papers

The department keeps an online repository of exam papers. You can also read comments on how students performed on part 1 of each paper and where they lost marks. You can find feedback from other members of staff teaching on the unit by looking at the general feedback page.

Previous exam papers.

As discussed above, the exam format has changed. Past papers will still provide an indication of the kinds of question you will be asked in the exam. The weekly online questions will also prepare you for the online portion of the exam.

Note also that up until 2011/12 the course unit consisted of three Parts. Part B is no longer taught, and not relevant for your exam preparation. Part C developed into the current second part, but the past exam questions are probably not relevant any longer. Also note that the questions were shorter then. However, certainly for Part 1 the type of task that appears in the paper is still typical of what you might be asked to do.

The contents of Part II has shifted slightly over the last few years. The following questions are still relevant to the current content:

  • Questions 7 in 2009-2011 apart from the parts asking you to sketch graphs
  • Question 8 in 2009
  • Question 8b in 2010
  • Questions 7 and 8 in 2012
  • Questions 3d,3e,3f and 4 excluding 4e in 2013
  • Questions 3d, 3e and 4 in 2014
  • Questions 3 and 4 in 2015


This course unit was previously taught by Andrea Schalk and relies heavily on materials produced by Andrea.

Built with Bootstrap and Font-awesome