Theory of Computation module (CS32004)

This module will help you develop an understanding of fundamental concepts for computation that help us understand the capabilities and limits of computing systems.

By studying general models of computers, we can gain an understanding of which types of problems can be solved by a computer and which cannot be solved. You will also learn about the complexity of algorithms, which describes how fast and with how much memory an algorithm solves a problem.

Equipped with this knowledge, you will be able to discuss some of the biggest, unanswered questions in computer science, such as the "P versus NP" problem.

Additionally, a strong understanding of computational theory is helpful in many branches of computer science, such as algorithm design and compiler construction. It also has practical applications in fields such as cryptography, artificial intelligence, and programming languages.

What you will learn

In this module, you will:

• study finite state automata, regular languages, and regular expressions
• learn about Turing machines as a model for computers
• explore the decidability of Turing machines and the halting problem
• look at time-bounded deterministic and non-deterministic Turing machines
• study the complexity classes P and NP

By the end of this module, you will be able to:

• describe common models of computation and their powers
• demonstrate an understanding of the theoretical limits of computing power and their underlying proofs
• explain the connection between formal languages and machines
• relate the theoretical ideas of complexity and decidability to real-world situations in computer science, such as algorithm design

Assignments / assessment

• class test 1 (10%)
• class test 2 (10%)
• written exam (80%)

Teaching methods / timetable

You will learn by taking a hands-on approach. This will involve taking part in tutorials.

Learning material is provided through videos, review notes, examples, and tutorial questions.