Computability and Computational Complexity
| Code | School | Level | Credits | Semesters |
| COMP3072 | Computer Science | 3 | 10 | Spring Malaysia |
- Code
- COMP3072
- School
- Computer Science
- Level
- 3
- Credits
- 10
- Semesters
- Spring Malaysia
Summary
You will begin by considering the attempts to characterise the problems that can theoretically be solved by physically possible computational processes, along with the practical implications. You will then consider the area of complexity theory, looking at whether or not problems can be solved under limitations on resources such as time or space. You will examine the classes P and NP, and how to show problems are NP-complete. You will also consider other practically important classes such as: “PSPACE”, and its relevance to adversarial games; and“NC” relevant to understanding of parallel computation and the limitations of its effectiveness. You will also consider classes “BPP” for probabilistic computation, and “BQP” relevant to quantum computing, along with the ideas of “post-quantum cryptography” based on NP-hard problems. You will look at the practical implications of computability and complexity in the context of real-world problems, such as vehicle routing, scheduling, timetabling, and machine learning, and quantum computing.
Target Students
Available to Level 3 and Level 4 students in the School of Computer Science. Available to inter-campus mobility students and other exchange students in computer science. This module is not available to students not listed above, without explicit approval from the module convenor(s). This module is part of the Foundations of Computer Science theme in the School of Computer Science.
Classes
- One 2-hour lecture each week for 11 weeks
Assessment
- 20% Coursework 1: Continuous assessment. Some assessment(s) may be under invigilated in-class test conditions.
- 80% Exam 1 (2-hour): 2 hr written examination.The reassessment for this module will be 100% Examination.
Assessed by end of spring semester
Educational Aims
The overall aim of the course is to provide an understanding of the concepts of computability and computational complexity. In particular, course objectives are as follows: To provide an appreciation of the many attempts that have been made to define the class of computable functions and to indicate that all the sensible attempts to do this have been shown to be equivalent. To appreciate impossibility proofs based upon diagonalisation arguments. To introduce the fact that there are problems that cannot possibly be solved on a computer. To show how, apparently different, computable problems of practical importance are related in respect of their algorithmic complexity and how this relates to the design and choices of algorithms for solving them in standard classical computers, and also quantum computers.Learning Outcomes
Knowledge and Understanding
To understand the theory of computation via mathematical methods.
Intellectual Skills
To apply and deploy mathematical ability, practices and tools;
To understand and logically evaluate the problems in computability and complexity;
To think independently about the issues while giving due weight to previous work;
To understand the ideas of the theory of computability and complexity and relate them to particular problems.
Professional Skills
To extend their own abilities by specialising or generalising from their previous knowledge.
Transferable Skills
The ability to solve problems using mathematics, by consulting external sources if necessary.
Conveners
- Dr Yasir Hafeez