Theory of Computation

This unit provides an introduction to classical models of computation, the equivalence of different computational models, and limits on what can be computed in terms of uncomputability and intractability. Consult the handbook entry for further details.

Timetabled Lectures and Labs

The first half of the lecture course will be delivered by Dr Bogdan Warinschi, the second half by Dr Oliver Ray. 'Labs' will occur during the timetabled slots, but will not take place in the computer labs. As this is a theoretical course we will be organising problems classes with postgraduate Teaching Assistants. You will be assigned to a problem class with 10 or 11 others to take place during one timetabled hour per week. The first problem classes will take place in week 14. For each problem class there will be an associated, unassessed, problem sheet that you should attempt beforehand and bring your answers along with you.

Office Hours

Lecture Notes

Students are expected to take notes during lectures. Any supplementary notes will be posted here as the course progresses.

The course closely follows the core text, Introduction to the Theory of Computation of which there are several copies in the library. Reading the appropriate chapters as we progress through the course is recommended.

To succeed on this course we recommend you attend lectures, take detailed notes, do the weekly problem sheets, and read the course text. Please share copies of the course text among yourselves by establishing study groups, etc.

Lecture summaries and associated reading

Lecture 1 Brief introduction to the course. I introduced Deterministic Finite Automata (DFAs) as a simple computational "device". I explained informally and formalized what does it mean for a DFA to accept a language L, and concluded by saying we call a language regular if it is accepted by some DFA. (Reading : Chapter 0 pages: 13-14, Chapter 1 pages 31-43 )

Lecture 2 We defined the class of regular languages, as the class of languages that are accepted by accepted by DFAs. We also looked at a couple of examples of DFAs. I have covered the design (and the design idea) of a DFA that accepts the set of bitstrings that represent integers divisible by 3. Finally, I introduced the set of regular operations (concatenation, union, and star) and looked at a couple of examples. (Reading : Chapter 1 pages 44-45)

Lecture 3 I first showed that the union of two regular languages is regular and looked at a construction on a particular example. Then, I talked about nondeterminims and nondeterministic finite automata (NFA). We saw a few examples of NFAs and that sometimes we may design NFAs more easily than DFAs (for the same language). We ended with the formal definition of an NFA and the formal definition of what does it mean for an NFA to accept a word. (Reading : Chapter 1.2 pages 45-54)

Study Guide

The study guides give you an overview of the course topics, and excercises to work through on your own and for the problems classes:

Assessment

Assessment is by coursework (30%) and exam (70%)

The first coursework is available: Coursework 1 . You will need the file data.txt for problem 5. This coursework is worth 15% and is due on March 16th. Late deadline is March 18th. The coursework should be handed in class at the beginning of the lecture, or submitted as a PDF file via the submission system. (Please read the instructions in the coursework on how to name the file you submit.)

The second coursework is available: Coursework 2 . The coursework is worth 15% and is due on Wednesday May 11th. The coursework should be submitted via the electronic submission system. Late deadline is Friday May 13th. The coursework should be handed in class at the beginning of the lecture, or submitted as a PDF file via the submission system. (Please read the instructions in the coursework on how to name the file you submit.)