Short Title:  Computational Theory 

Full Title:  Computational Theory 

Language of Instruction:  English 

Field of Study:  Computer Science 

Reviewed By:  FINBARR FEENEY 

Module Author:  MARGARET FINNEGAN 

Module Description:  To instill an appreciation of the importance of program complexity, and develop an ability to differentiate between alternative solutions to a given problem, to to reconise computationally intractable problems; to make the student cognisant of the parallels between finite automata and programs, and the ability to identify undecidable problems; to provide a grounding in formal specification languages, and an appreciation of their importance in software development. 

Learning Outcomes 
On successful completion of this module the learner will be able to: 
LO1 
Determine the time and space complexities of alternative algorithmic solutions, evaluate and compare proposed solutions, and identify programming limitations for different problems. 
LO2 
Describe the significance of Finite State Machines and Turing Machines within the context of Computer Science. 
LO3 
Use mathematical techniques, e.g. sets, relations, functions, in the specification of Formal Models of computation. 
LO4 
Apply Mathematical techniques to determine the time complexities of algorithms 
LO5 
Prove closure properties of formal languages. 
Module Content & Assessment
Course Work 
Assessment Type 
Assessment Description 
Outcome addressed 
% of total 
Assessment Date 
Continuous Assessment 
In class practical and theory exam. Typical practical tasks for example would be to: design a Turing machine to implement mathematical functions such as multiplication, design a Finite State Machine and describe and formally define the regular expression that describes the language accepted by it, demonstrate knowledge of various graph algorithms, and used mathematical techniques that can show to which class (P or NP) that the algorithm belongs. 
1,2,3,4,5 
20.00 
n/a 
Assignment 
5 lab sheets over the course of the semester: Examines all aspects of the course on an ongoing basis. Theory and practical questions. 
1,2,3,4,5 
20.00 
n/a 
End of Module Formal Examination 
Assessment Type 
Assessment Description 
Outcome addressed 
% of total 
Assessment Date 
Formal Exam 
EndofSemester Final Examination 
1,2,3,4,5 
60.00 
EndofSemester 
TU Dublin – Tallaght Campus reserves the right to alter the nature and timings of assessment
Module Workload
Workload: Full Time 
Workload Type 
Workload Description 
Hours 
Frequency 
Average Weekly Learner Workload 
Lecture 
Lecture 
2.00 
Every Week 
2.00 
Tutorial 
Tutorial 
1.00 
Every Week 
1.00 
Total Weekly Learner Workload 
3.00 
Total Weekly Contact Hours 
3.00 
Workload: Part Time 
Workload Type 
Workload Description 
Hours 
Frequency 
Average Weekly Learner Workload 
Lecture 
Lecture 
2.00 
Every Week 
2.00 
Tutorial 
Tutorial 
1.00 
Every Week 
1.00 
Total Weekly Learner Workload 
3.00 
Total Weekly Contact Hours 
3.00 
Module ResourcesRequired Book Resources 

 Judith L. Gersting 2014, Mathematical structures for computer science, W.H. Freeman New York [ISBN: 0716743582]
 Recommended Book Resources 

 Michael Sipser 2012, Introduction to the Theory of Computation, SouthWestern College Publishing; 3rd International edition edition (23 Nov. 2012) [ISBN: 1133187811]
 Cristopher Moore,Stephan Mertens 2011, The Nature of Computation, Oxford University Press [ISBN: 9780199233212]
 Steven S. Skiena 2008, The Algorithm Design Manual, SpringerVerlag New York Incorporated [ISBN: 978184800069]
 Thomas H. Cormen 2009, Introduction to Algorithms, MIT Press [ISBN: 9780262533058]
 This module does not have any article/paper resources 

This module does not have any other resources 

Module Delivered in
