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
Week
Topics Covered
1
Introduction to languages, finite automata
2
Deterministic and nondeterministic finite automata; equivalence of DFA and NFA
3
Regular expressions, equivalence with finite automata, Pumping Lemma
Church-Turing thesis, TMs as generators, Universal Turing Machines
6
Undecidability, the Halting Problem, examples of undecidable problems
7
Time complexity, decision problems, polynomial time, the class P
8
Non-deterministic TMs, polynomial transformations, the class NP
9
NP-completeness, Cook's theorem, examples of NP-complete problems
10
Revision
11
Revision
12
Revision
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
Title
Week Given
Week Due
Effort Expected (hours)
Value (%)
Class Test 1
5
5
10
10
Class Test 2
9
9
10
10
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.