| Volker Sorge | 10 credits in Semester 2 |
The room for exercise group 2 is actually UG04 in the Learning Centre.
Rooms and groups for the exercise classes will be announced Monday afternoon! Please have a look at the webpage before going to class on Tuesday.
Exercise classes are Tuesdays, 2:00-2:50pm. Exercises will be conducted in groups and you are expected to go to the group you are assigned to every week and hand in your homework with the respective tutor. Please check the links below to find your group. Note, that tutors have the right to reject work if you are in the wrong class!
Should your ID number not be on any of the lists, please email me. For the first exercise, please go to either of the groups and tell the tutor.
| Group 1 | UG40, Computer Science | Aybek Mukhamedov |
| Group 2 | UG04, Learning Centre | Kidane Weldemariam |
| Group 3 | G35, Chemical Engineering | Theodoros Tsokos |
Information about the tutorials
20% continuous assessment: Every
handout will contain Quickies, Classroom Exercises and Homework
Exercises. The classroom exercises are to be done during the exercise
classes and your work will be collected by the tutor for marking at the end of
the class. Quickies are small exercises best done shortly after the lecture to
experiment with the new concepts. They will not all be assessed. Those that are
assessed should be handed in to your tutor at the exercise class. Homework must
be handed in through one of the departmental pigeon holes on the Ground Floor
(next to the General Office). They are due Mondays, 9am. This is one week
after they have been issued in the lecture. Late submissions will not be
accepted because we will provide model answers to all exercises. If you have a
serious reason for not being able to complete a particular assignment, then see
someone from the Welfare Team. (The precise procedure is explained in the Student
Handbook .) If your explanation for absence is accepted then we will ignore
the relevant pieces of assignment in the calculation of your mark.
Clearly write your registration numbers on each sheet of your submission. No registration numbers -- no points. Do not write your names on your submission. Submissions with names will be marked but not returned. When handing in you homework exercises on Monday morning please refrain from attaching cover sheets. Just drop it in the right pigeon hole. Please observe that there is a separate pigeon hole for the stretcher exercises!
Marks will be assigned on the basis of your performance in both classroom and homework exercises. Marks will be made available on this webpage and through the School Information System.
If you have any questions, problems, or comments, please email me or come and see me during my office hours Monday 11-12am after the lecture. To see me outside these office hours, please email me and suggest some times, which are compatible with my timetable.
When emailing, please observe that you can expect the fastest response, when your email is short and in plain ASCII. If you have to send attachments, please make sure they are in some open standard format. In particular, do NOT send MS word files. Why? See here.
| Title | Author(s) | Publisher | Comments |
| Introduction to the Theory of Computation, 2nd Edition | Sipser | PWS Publishing, 2005 | Further Reading |
| Computers Ltd: What they really can't do | Harel | Oxford University Press, 2003 | Further Reading |
| Introduction to Languages and the Theory of Computation | Martin | McGraw-Hill | Further Reading |
| Computability and Complexity: From a Programming Perspective | Jones | MIT Press | Further Reading |
| An Introduction to Functional Programming through Lambda Calculus | Michaelson | Addison-Wesley | Further Reading |
| Week | Topic | Handout | Solutions |
| 0 | General Information | gzipped PostScript, pdf | |
| 1 | Regular Expressions and Finite Automata | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 2 | Regular Languages | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 3 | Context Free Grammars and Pushdown Automata | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 4 | The Halting Problem | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 5 | Undecidability | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 6 | Turing Machines | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 7 | Church's Thesis | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 8 | Complexity | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 9 | NP Completeness | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 10 | Lambda Calculus | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 11 | More on the Lambda Calculus | gzipped PostScript, pdf | |
| 12 | Review Suggestions | gzipped PostScript, pdf |
Errata can be found here.
Maintained by:
Volker Sorge,
School of Computer Science,
The University of Birmingham
Last modified: Fri Mar 14 11:02:58 GMT 2008