Theory of Computation module (AC32008)

On this page
Credits

20

Module code

AC32008

Semester: 2

Organisation

About the Module

This module aims to introduce general models of computation such as finite state automata and Turing machines and their relationship to classes of languages, and use these models to explore the limits of the power of computers.

Credit Rating

There are 20 SCQF points available on this module.

Module Timetable

WeekTopics Covered
1Introduction to languages, finite automata
2Deterministic and nondeterministic finite automata; equivalence of DFA and NFA
3Regular expressions, equivalence with finite automata, Pumping Lemma
4Turing machines, (partially) decidable languages, computable functions
5Church-Turing thesis, TMs as generators, Universal Turing Machines
6Undecidability, the Halting Problem, examples of undecidable problems
7Time complexity, decision problems, polynomial time, the class P
8Non-deterministic TMs, polynomial transformations, the class NP
9NP-completeness, Cook's theorem, examples of NP-complete problems
10Revision
11Revision
12Revision

Assessment and Coursework

Coursework counts for 20% of the final module mark.
The final degree exam counts for 80% of the final module mark.

 Assignments

TitleWeek GivenWeek DueEffort Expected (hours)Value (%)
Class Test 1551010
Class Test 2991010

Resources

All course material is available on My Dundee. This includes copies of lecture materials, practical exercises and assignments. The reading list for this module can be accessed from My Dundee, and provides recommended materials for completing the module.