Shortcuts: Course notes · Coursework · Solutions · Exams · Official Syllabus · Lecture Capture Podcasts
The material on this page has not yet been updated for 2014/15. This page is here to allow students to see what to expect from the first part of this course unit.
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.
There are two lectures per week, and each student has one examples class in that period. See the organizational part of the notes for more detail.
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 A.Schalk at cs.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 do 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.
The material for this part of the course is mathematical in nature. There is an Appendix in the notes that shows how the statements in the notes can be made completely rigorous. 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.
Despite my best efforts, the notes may still contain some errors. I keep an up-to-date list of them available here.
Corrigenda. Last updated 23 April 2014.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 are made available here when the last examples class for a sheet has occurred.
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.
In order for your exercise marks to count at all you must have done work in at least 7 out of the 10 weeks when examples classes run. If your mark has been zeroed due to plagiarism this will not count as a week with work done for these purposes.
Exam Format:
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.
Previous exam papers. Note 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 I might ask you to do.
The department keeps an online repository of exam papers. You can find the 2009, the 2010, the 2011, the 2012, the 2013, and the 2014 papers there.
You can also read my comments on how students performed on my part of each paper and where they lost marks for the 2009, 2010, 2011, 2012, 2013 and 2014 papers. You can find feedback from other members of staff teaching on the unit by looking at the general feedback page.