On successful completion of this unit, a student will be able to:
The learning outcomes will assessed by coursework and exam.
Detailed notes will be distributed, but the following texts may also be useful. All can be found in the University library.
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.
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.
Exercise sheets (both formative and summative) for Part I can be found on Blackboard. Solutions will also be published there after the examples classes.
We are all fallible. A list of any errors and corrections to the distributed notes will be available here.
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 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.
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.
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.
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.
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:
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
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.
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 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.
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:
This course unit was previously taught by Andrea Schalk and relies heavily on materials produced by Andrea.