COMP11212: Fundamentals of Computation

Semester 2, 2017/2018

Sean Bechhofer (Part 1) & Giles Reger (Part 2)


There are two lectures per week, Monday at 11:00 and Tuesday at 11:00. Each student also has one examples class in that period. See the organizational part of the notes and the timetable for more detail.

Reading List

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


Course notes will be available via these pages. There is also an area on the University's Blackboard Site for the course where solutions will be released. 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.


Lectures are recorded using the University's Lecture Capture Podcast system. Please do not use the podcasts as a substitute for lecture attendance.

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.

Course notes

The notes, 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.

Copies of the notes are handed out in the first week of term. Left-over copies are deposited near the Student Support Centre as usual. If you lose your notes and no copies are left you can print them again from here.

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.

Corrections and Clarifications

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

Part 2

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


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

Please see the first half of the notes for a thorough introduction to the topics being covered and additional informaion such as recommended reading.

Course notes

The notes have been split into bits as follows:

These notes contain a lof of new material and it is likely that they will also contain some mistakes. If you spot a mistake please email me at I will update the notes with corrections as they are found. A list of the corrected mistakes can be found here

The notes contain the exercises for the examples classes and solutions will be posted on Blackboard.

Slides from the lectures will appear here after the lecture:

General Organisation

Examples classes

For each of the five examples classes associated with the first part there is an exercise sheet at the end of the notes. It details a number of exercises. Some of these are marked in the examples classes every week for the coursework component of your mark. There are also preparatory exercises that make the key exercises easier to do, and additional exercises that you could do, or that you could leave for revision. There are also exercises for those working through the appendix of the notes. Please read page 4 of the notes for a description of how the coursework is marked, and what you have to do in order to get marks for your work.

The point of the examples classes is to

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

Solutions to the exercises in the notes will be made available via Blackboard when the last examples class for a sheet has occurred.

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.


The coursework for this unit consists of preparing the named exercises on each sheet, for 25% of the overall mark. You will get a mark for these during the examples class. The marker may ask you to show all your work and to explain how you solved the exercise. If you cannot do this you will be considered to have plagiarized the piece of work in question and be given a mark of 0 for the week. A note will be made on your file, and for additional, or more serious, offences you will have to answer to higher authorities. Ultimately you may be expelled from the university for such offences.

Best Eight

Coursework solutions are released shortly after the examples classes. This means that there is no opportunity for extensions to the deadline.

Your final coursework mark will be calculated by taking the best eight marks from the ten sessions. This means that you can do badly in one or two sessions without impacting your final mark. If you miss more than two sessions due to ill-health or circumstances outside your control, you must submit mitigating circumstances

The examples classes are for you to get feedback on your work. They are not for you to do the work. If you attend an examples class and tell a marker that you're "not ready to be marked yet", you will get a mark of 0 for that exercise.


Exam Format

  • The exam has two questions which correspond to the two different parts of the taught material.
  • You must answer all parts of both questions.
  • Each question is worth 30 marks, the whole exam is marked out of 60.
  • The exam makes up 75% of the final mark, the coursework 25%.

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.

Note that previous exam papers had a different structure. Between 2012 and 2016, the paper asked for answers to three questions out of four. This has changed for 2016-17 and all questions should now be answered.

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