| Volker Sorge | 10 credits in Semester 2 |
We have published the solution to exercise in gzipped PostScript or pdf to help you with homework exercise 27.
I have issued an addendum for handout 5, with the Turing machine that accepts words of the form a2n, ≱0. Please pick it up here in gzipped PostScript or pdf.
There have been some mistake in the solutions to exercise 2, that were handed out in class today. Please either see the Errata or download the updated version here
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 | Zaid Al-Zobaidi / Aybek Mukhamedov |
| Group 2 | UG04, Learning Centre | Olaf Klinke |
| Group 3 | UG05, Learning Centre | Olufunmilola Onolaja |
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 Exercise 3 |
gzipped PostScript,
pdf gzipped PostScript, pdf |
gzipped PostScript,
pdf gzipped PostScript, pdf |
| 3 | Context Free Grammars and Pushdown Automata | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 4 | Turing Machines | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 5 | Church's Thesis Addendum |
gzipped PostScript,
pdf gzipped PostScript, pdf |
Solution 26ps.gz,
pdf gzipped PostScript, pdf |
| 6 | The Halting Problem | gzipped PostScript, pdf | gzipped PostScript, pdf |
| 7 | Undecidability | 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 | Review Suggestions | gzipped PostScript, pdf |
Errata can be found here.
Maintained by:
Volker Sorge,
School of Computer Science,
The University of Birmingham
Last modified: Wed Apr 15 17:24:12 BST 2009