Short Title:Computational Theory
Full Title:Computational Theory
Language of Instruction:English
Module Code:COTH H4001
 
Credits: 5
Field of Study:Computer Science
Module Delivered in 4 programme(s)
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 End-of-Semester Final Examination 1,2,3,4,5 60.00 End-of-Semester

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 Resources

Required 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, South-Western 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, Springer-Verlag 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

Programme Code Programme Semester Delivery
TA_KCOMP_B (1 year add on) Bachelor of Science (Honours) in Computing 8 Mandatory
TA_KACOI_B Bachelor of Science (Honours) in Computing with Language (French/ German/ Spanish) 8 Mandatory
TA_KACOS_B Bachelor of Science (Honours) in Computing with Software Development 8 Mandatory
TA_KCOSD_B Bachelor of Science (Honours) in Computing with Software Development - Year 4 ( Add on) 2 Mandatory