There are two lectures per week, Monday at 11:00 and Friday at 10:00. Each student also has one examples class in that period. See the organizational part of the notes and the timetable for more detail.
Lectures are recorded using the University's Lecture Capture Podcast system. Please do not use the podcasts as a substitute for lecture attendance.
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.
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
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.
For the first part of the course, the following texts may be useful. All can be found in the University library.
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 manchester.ac.uk.
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
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.
We are all fallible. A list of any errors and corrections to the distributed notes is available here.
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.
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 firstname.lastname@example.org. 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:
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
Solutions to the exercises in the notes will be made available via Blackboard when the last examples class for a sheet has occurred.
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.
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.
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.
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:
This course unit was previously taught by Andrea Schalk and relies heavily on materials produced by Andrea.