Registry

Module Specifications

Current Academic Year 2012 - 2013
Please note that this information is subject to change.

Module Title	Computability and Complexity
Module Code	CA320
School	School of Computing
Online Module Resources
Module Co-ordinator	Semester 1: David Sinclair Semester 2: David Sinclair Autumn: David Sinclair
NFQ level	8	Credit Rating	5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

Description

The goal of this module is to provide an insight into the fundamental capabilities and limitations of computers. This module will expose students to three central areas of the theory of computation: automata, computability and complexity. With respect to automata, a number of languages of increasing descriptive power will be studied as well as corresponding automata which can be used to recognise these languages. With respect to computability, it will be shown which problems can or cannot be solved by computer. A number of different models of computation will be studied, and it will be shown that these are all of equivalent computational power. With respect to complexity, it will be shown for those problems which can be solved by computer whether they can be solved within a reasonable amount of time and space.

Learning Outcomes

1. Determine which languages are descriptive enough to describe particular problems.
2. Determine which automata are powerful enough to solve particular problems.
3. Design languages to describe particular problems.
4. Design automata to solve particular problems.
5. Solve problems using a number of different models of computation.
6. Determine whether a given problem can be solved by computer.
7. Determine whether a given problem can be solved within a reasonable amount of time.
8. Determine whether a given problem can be solved within a reasonable amount of space.

Workload	Full-time hours per semester
*Type*	*Hours*	*Description*
Lecture	24	No Description
Laboratory	24	No Description
Independent learning	77	No Description
Total Workload: 125

All module information is indicative and subject to change. For further information,students are advised to refer to the University's Marks and Standards and Programme Specific Regulations at: http://www.dcu.ie/registry/examinations/index.shtml

Indicative Content and Learning Activities

Introduction.
Sets, Functions, Languages and Algorithms.

Regular languages and finite automata.
Regular grammars, Regular expressions and Finite state automata.

Context-free languages and pushdown automata.
Context-free grammars, Derivations and ambiguity and Pushdown automata.

Context-sensitive grammars and linear bounded automata.
Context-sensitive grammars, Context-sensitive languages and Linear bounded automata.

Models of computation.
Turing machines, Unrestricted grammars, Partial recursive functions, Lambda calculus, Haskell, Cellular automata and Church-Turing thesis..

Computability.
Halting problem , Reducibility and Other uncomputable problems.

Complexity.
Asymptotic notation, The class P, The class NP, NP-completeness, Space complexity, The class PSPACE, PSPACE-completeness and The class EXP.

Assessment Breakdown
Continuous Assessment	25%	Examination Weight	75%

Course Work Breakdown
Type	Description	% of total	Assessment Date
Assignment	Describe a specified problem using a formal langauge	10%	Week 7
Assignment	Design an automaton to solve a specified problem	15%	Week 12

Reassessment Requirement
Resit arrangements are explained by the following categories; 1 = A resit is available for all components of the module 2 = No resit is available for 100% continuous assessment module 3 = No resit is available for the continuous assessment component
This module is category 1

Indicative Reading List

M. Sipser: 1996, Introduction to the Theory of Computation, PWS Publishing Company, 0-53-494728-X
Simon Thompson: 0, Haskell: The Craft of Functional Programming, Addison Wesley, 0-201-34275-8
Harry R. Lewis, Christos H. Papadimitriou: 1998, Elements of the theory of computation, Prentice Hall, Upper Saddle River, NJ, 0-13-272741-2
J.C. Martin: 1997, Introduction to Languages and the Theory of Computation, McGraw-Hill, 0-07-115468-X
Graham Hutton: 0, Programming in Haskell, Cambridge University Press, 9780521692694

Other Resources

None

Array

Programme or List of Programmes

BSSAO

Study Abroad (DCU Business School)

CASE

BSc in Computer Applications (Sft.Eng.)

ECSA

Study Abroad (Engineering & Computing)

ECSAO

Study Abroad (Engineering & Computing)