Models of Computation
Lecturer: Steve Vickers
Tutors: Zaid Alzobaidi, Masoud Koleini, Chuangjie Xu, Maxim Strygin
Additional help from Asiri Rathnayake
- Timetable
- Tutor Groups
- Peerwise - register straight away. It won't take long.
- Handouts
- Continuous assessment, Policy on plagiarism, Anonymous marking, Exams
- Textbooks
- School module page
Handouts
Handouts containing lecture notes and exercises will be provided after each lecture. They can also be accessed here (in PDF format).
Spare copies are kept in the School Library.
PDF versions of some of the lecture slides can also be accessed here, but they are best viewed on-line in colour. Printed copies will not be made available.
Week by week: Handouts will normally be made available the Friday before the lecture,
and the slides after the lecture.
Handouts and slides for future weeks are from last year and are for reference only. There may be changes this year and in particular the exercises will be different.
Solutions to coursework will be made available after the handin date.
- Finite State Machines and Regular Expressions:
handout,
solutions,
slides,
applets to demonstrate
non-deterministic finite automata and
non-deterministic finite automata with epsilon-moves.
- Regular Languages:
handout,
solutions,
slides.
For more on loop invariants and Warshall's algorithm, see Reasoned Programming, chapters 10 (p.141) and 13 (p.176). - Context-free languages and pushdown automata: handout, solutions, slides
- The Halting Problem: handout, solutions, slides, Geoffrey Pullum's poem "Scooping the Loop Snooper"
- More on decidability: reducibility proofs: handout, solutions, slides.
- Turing machines:
handout,
solutions,
slides.
The homework in the printed handout is wrong. See the on-line handout for the correct version. - Church's Thesis: handout, solutions, slides.
- Complexity: handout, solutions, slides.
- NP-Completeness: handout, solutions, slides.
- The λ-Calculus: handout, solutions, slides.
- More on the λ-Calculus: handout, solutions, slides.
Timetable
Lecture
Mondays, 9:00--10:50am, Room E102 Biosciences (Building R27)
Exercise Classes
Tuesdays, 2:00--2:50pm
Tutor groups
There are four tutor groups.
For full lists, click the ID ranges.
If your id is not listed, go to the class with the right id range and mention to
your tutor that your id is missed out.
The four tutors are Zaid Alzobaidi, Masoud Koleini, Chuangjie Xu and Maxim Strygin, who will initially be allocated to groups as shown. (We may rotate them later.)
Make sure you know which group you are in (1, 2, 3 or 4)
and which room your exercise class is in.
Each group has a different pigeonhole for returning homework; there is a fifth
pigeonhole for all stretcher exercises.
Group 1
Students: -- 1066958
Tutor: Zaid Alzobaidi
Exercise Classes: LG33, Learning Centre (Building R28)
Group 2
Students: 1066959 -- 1089139
Tutor: Masoud Koleini
Exercise Classes: LG34, Learning Centre (Building R28)
Group 3
Students: 1089140 -- 1105303
Tutor: Chuangjie Xu
Exercise Classes: UG40, Computer Science
Group 4
Students: 1105304 --
Tutor: Maxim Strygin
Exercise Classes: LT2, Sport Ex (Building Y14)
Continuous assessment
This contributes 20% to the module mark and consists of the following. Every handout will contain "Quickies", "Classwork" and "Homework". Quickies are small exercises best done shortly after the lecture to experiment with the new concepts. They are generally unassessed. If any Quickies are assessed, they should be handed in to the tutor during the exercise class. The classwork 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. Homework must be handed in through one of the departmental pigeon holes on the Ground Floor (next to the General Office). Homework is due Mondays, 2pm. 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.
Marks will be assigned on the basis of your performance in both classroom and homework exercises. You will be able to check the marks which have been recorded against your name by visiting this web page. Marked work will normally be returned at the exercise classes two weeks after it was set.
Part of the continuous assessment mark will be given for participation in Peerwise.
Policy on plagiarism
You are encouraged to work in small teams during the exercise classes and to ask for help from the tutor. You will, however, have to submit your work individually. Homework exercises are of a style similar to those appearing in the May examination, and we recommend that you attempt them individually, but you may still find it helpful to discuss the assignments with others. In any case, work submitted must be formulated by yourself. If we find evidence of plagiarism then we will award zero marks, irrespective of whether you copied from others or whether your work was copied by others. More serious cases will be dealt with according to the School's policy on plagiarism.Anonymous marking
We are required to mark anonymously wherever possible. There is no reason why we should not follow this rule for the exercises in this course. Please note, however, that this means that you always have to write your registration number on your submitted work. Scripts which do not contain the registration number will have to be ignored by us.Final exam
The exam takes place in May and lasts 1.5-hour. It is marked on a scale from 0 to 100 but contributes only 80% to the module mark.
If you choose not to participate in the continuously assessed exercises, then you have to obtain 50% of the exam marks in order to pass the module!
Resit exam
There is one resit opportunity for this module in August. It contributes 100% to the module mark -- the exercise mark will not be carried forward.Peerwise
Please sign up for this module on Peerwise immediately; it only takes a few minutes.
Part of the continuous assessment mark will be given for participation in Peerwise. See the instructions for students on that page.
To gain points, you must write at least one multiple-choice question on a topic covered in the module, and answer at least three other questions.
A further part of the mark may be given as discretionary bonus points. The bonus marks may be awarded for active participation (e.g. leaderboard status), but in particular for writing insightful questions.
The more questions you create, answer, comment on, etc, the more you will learn and the more you will help other students on the module. If a fair number of students contribute good questions, there will be plenty of revision material for everyone before the exams. You may also enjoy winning badges and trying to get on the leaderboard.
You need to register on the Peerwise server.
- The course ID for this module is 5945.
- Your "identifier" on Peerwise is the same as your Bham student ID number.
- You can choose any username and password when registering.
- Please tag your questions with appropriate topics, so that others can find them more easily.
Textbooks
It is not necessary for you to buy a textbook for this course as the handouts are sufficiently detailed for revision and self-study. Some students, however, do like to see the material explained by another author and this can help to understand the more difficult parts. In this case we recommend that you examine the textbooks in the School Library first before you commit any money.
Sipser: Introduction to the Theory of Computation. PWS Publishing, 1997.
The first part on finite automata is excellent and gives many examples and detailed explanations. The later chapters get rather mathematical, but on the whole this book is good cover for the module.
Harel: Computers Ltd: What they really can't do. Oxford University Press, 2003.
A well-written and non-technical introduction to the fields of uncomputable problems (e.g., "Halting Problem") and NP-completeness.
Martin: Introduction to Languages and the Theory of Computation. McGraw-Hill.
The strength of this book is the many worked examples. What I don't like so much is its reliance on mathematical formalism (and the fact that it starts with two chapters on mathematical background). Like the books before, it does not cover everything we do in the course.
Jones: Computability and Complexity: From a Programming Perspective. MIT Press.
This is one of the very few books which subscribe to the view that undecidability can be explained without Turing machines (the course notes being another such text). However, the underlying formalism is that of functional programming which not all of you will be familiar with.
Michaelson: An Introduction to Functional Programming through Lambda Calculus. Addison-Wesley.
This is a nice gentle introduction to the λ-calculus, leading towards functional programming. The early chapters are very accessible.