This module introduces the theoretical foundations for computing systems: finite state machines, pushdown automata, and Turing machines, along with the formal languages that can be recognised by these machine models.

It also deals with the question 'What is computable?' and 'What is efficiently computable?' by showing when problems are computationally hard, and how to find algorithmic solutions to computationally hard problems.

Autumn

Spring

• Blackboard
• Unconfirmed practical marks when available
• Exam Papers, past 2 years (where applicable)

This unit aims to:

1. Introduce machine models (i.e. models of computation) and the corresponding notions of formal languages;
2. Introduce complexity theory and algorithmic solutions to computationally hard problems;
3. Enhance analytical and logical skills in reasoning abstractly (about computation and complexity);
4. Teach the foundations of theoretical computer science, providing a thorough grounding for theoretical courses at more advanced levels.

By the end of the unit, a candidate will be able to:

1. Use different machine models and the formal languages they are able to recognise.      
2. Show that a problem is computationally easy or hard.                     
3. Identify algorithmic solutions for computationally hard problems.

Models of Computation (Semester 1)

• finite automata and regular languages
• pushdown automata and context free languages
• Turing machines and decidability

Computation and Complexity (Semester 2)

Time Complexity

• P vs. NP, NP-completeness, Cook-Levin theorem
• Techniques for proving NP-hardness

Algorithm Design Techniques:

• Dynamic Programming
• Network flows
  
• Linear Programming 

Coping with Intractability:

• Approximation algorithms
• Heuristics 
• Randomisation

The theoretical background and techniques will be presented in a series of formal lectures, 2 lectures per week. Students will reinforce the material through self-study, and through weekly problems classes where students will apply analytical skills obtained in class. Both lectures and problem classes are designed to achieve objectives 1-4.