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.
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
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.
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.
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 will be 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 information such as recommended reading.
These notes contain a lot of new material and it is likely that they will also contain some mistakes. If you spot a mistake please email me at email@example.com. I will update the notes with corrections as they are found. A list of the corrected mistakes can be found
The notes contain the exercises for the examples classes and solutions will be posted on Blackboard.
The coursework for this unit contributes 25% of the overall mark. Each week there will be a number of exercises to be completed online via Blackboard. These must be completed by 17:00 on Friday afternoon.
In addition to the online exercises, there will be two or three exercises to be completed on paper and marked during the examples classes.
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
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.
You are expected to complete this work individually. The online exercises are marked automatically. For the examples classes, you will get a mark for the relevant exercises during the examples class. The TA 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. 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 weeks. 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.
Note that the exam format has changed for academic year 17-18, with the introduction of an online component.
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.