Registry

Module Specifications

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

Module Title	Algorithms & Complexity
Module Code	CA313
School	School of Computing
Online Module Resources
Module Teacher	Andrew Way
NFQ level	8	Credit Rating	5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

Description

The aim of this course is to introduce the student to the fundamentals of complexity theory.

Learning Outcomes

1. Explain and define the four classes of grammar in the Chomsky hierarchy; design automata for specific problems in each class of the Chomsky hierarchy
2. Define a Turing machine, and explain what it can be used for; write Turing machines to compute simple functions
3. Define time and space complexity
4. Write functions using big-O notation, and order complexities of functions in terms of big-O notation
5. Compute the time complexity of basic algorithmic functions
6. Explain the classes of functions NP, NP-complete, and NP-intermediate; and describe and compare approximate solutions to such problems which run in polynomial time and space
7. Explain the two classes DSPACE and NSPACE, and describe the relationships between time and space complexity classes

Workload	Full-time hours per semester
*Type*	*Hours*	*Description*
Lecture	24	No Description
Assignment	30	No Description
Independent learning	71	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

Sets, relations and functions. Proofs by induction, breadth-first search and diagonalisation.Alphabets, words and languages. Turning machines. Machines and languages. Reducibilitybetween languages..
The class P. Polynomial-time reducibility..

The class NP. NP-complete languages. Cook's theorem. NP-intermediate languages..
The class coNP. The Boolean hierarchy. The polynomial hierarchy. Exponential-time.

complexity classes..
Space Complexity. Space complexity classes. Relations between time and space. Logarithmic space. Polynomial space..

Assessment Breakdown
Continuous Assessment	20%	Examination Weight	80%

Course Work Breakdown
Type	Description	% of total	Assessment Date
Assignment	Implement Algorithm	10%	Week 4
Assignment	Implement Algorithm	10%	Week 10

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

D.P. Bovet and P. Crescenzi: 1994, Introduction to the Theory of Complexity, Prentice Hall, 0139153802
M.R. Garvey and D.S. Johnson: 1979, Computers and intractability: a guide to the theory of NP completeness, Freeman, 0716710455
H.R. Lewis & C.H. Papadimitriou: 1998, Elements of the Theory of Computation, 2, Prentice Hall,
B.M. Moret: 1998, The Theory of Computation, Addison-Wesley,
J.E. Savage: 1998, Models of Computation, Addison-Wesley,
A.K. Dewdney: 1989, The New Turing Omnibus, Freeman & Co,

Other Resources

1097, website, Andy Way, 0, CA313 Algorithms & Complexity, DCU, Dublin, Ireland, http://www.computing.dcu.ie/~away/CA313/,

Array

Programme or List of Programmes

BSSA

Study Abroad (DCU Business School)

SHSA

Study Abroad (Science & Health)

Timetable this semester: Timetable for CA313

Date of Last Revision

10-JAN-11

Archives: