Registry

Module Specifications

Archived Version 2012 - 2013

Module Title	Computability and Complexity
Module Code	CA320
School	School of Computing
Online Module Resources
Module Co-ordinator	Dr David Sinclair	Office Number	L2.53
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.

*Type*	*Hours*	*Description*
Workload	Full-time hours per semester
Lecture	24	No Description
Laboratory	24	No Description
Independent Study	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%

Type	Description	% of total	Assessment Date
Course Work Breakdown

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
Unavailable

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

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)
HMSA	Study Abroad (Humanities & Soc Science)
HMSAO	Study Abroad (Humanities & Soc Science)
SHSAO	Study Abroad (Science & Health)

Archives: