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

• Knowledge quizzes 
• Formal exam

Spring

• Knowledge quizzes 
• Formal exam

• 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.

Automata Theory (Semester 1)

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

Computation and Complexity (Semester 2)

Computational Complexity: P and NP

• Reductions and Rice's Theorem
• P vs. NP, NP-completeness, Cook's theorem
• Techniques for proving NP-hardness

Algorithm Design Techniques:

• Branch-and-bound
• Dynamic Programming
• Network flows
  

Approximation Algorithms:

• Examples for approximation algorithms
• Polynomial-time approximation schemes
• Hardness results for approximation
  

Randomization:

• Examples for randomized algorithms
• Probabilistic complexity classes

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.