|
Module Title |
Algorithms & Complexity
|
|
Module Code |
CA313
|
|
School |
Computing
|
Online Module Resources
|
| Module Co-ordinator | Prof Andy Way | Office Number | L2.01C |
|
Level |
3
|
Credit Rating |
5
|
|
Pre-requisite |
None
|
|
Co-requisite |
None
|
|
|
Module Aims
|
The aim of this course is to introduce the student to the fundementals of complexity theory.
|
|
Learning Outcomes
|
As a result of this course the student will: · understand the fundementals of complexity classes; · understand the relationship between these complexity classes; and · appreciate of the implications of these classes on computation.
|
|
Indicative Time Allowances
|
|
|
Hours
|
|
Lectures |
24
|
|
Tutorials |
0
|
|
Laboratories |
0
|
|
Seminars |
0
|
|
Independent Learning Time |
51
|
|
|
|
|
Total |
75
|
|
Placements |
|
|
Assignments |
|
|
|
NOTE
|
Assume that a 5 credit module load represents approximately 75 hours' work, which includes all teaching, in-course assignments, laboratory work or other specialised training and an estimated private learning time associated with the module.
|
|
Indicative Syllabus
|
|
· 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 | | Continuous Assessment | 20% | Examination Weight | 80% |
|
|
Indicative Reading List
|
|
Essential Introduction to the Theory of Complexity , D.P. Bovet and P. Crescenzi, Prentice Hall,1994 ISBN: 0139153802Supplementary Computers and intractability: a guide to the theory of NP-completeness , M.R. Garvey and D.S. Johnson, Freeman, 1979ISBN: 0716710455.
|
|
|
|
Programme or List of Programmes
|
| BSSA | Study Abroad (DCU Business School) |
| 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) |
| SHSA | Study Abroad (Science & Health) |
| SHSAO | Study Abroad (Science & Health) |
| Timetable this semester: Timetable for CA313 |
| Date of Last Revision | 28-NOV-08 |
| Archives: | |
