Undergraduate Course: Computational Complexity (INFR11102)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 11 (Year 4 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | This module studies the problem of classifying computational problems according to their intrinsic difficulty or 'complexity'. We begin by defining a standard computational model, the Turing machine, which is useful for abstracting out complexity aspects of computational problems. We define various complexity resources, such as time, space, non-determinism , randomness and non-uniformity, and learn how to classify computational problems according to their resource requirements. Among other topics, we discuss the central problem of theoretical computer science, the P vs NP problem, and explain its importance using the notions of reductions and completeness. |
| Course description |
* The computational model: Turing machines
* NP and NP completeness
* Space complexity
* Diagonalisation
* The polynomial hierarchy
* Circuits
* Randomised computation
* Counting complexity
Relevant QAA Computing Curriculum Sections: Concurrency and Parallelism, Data Structures and Algorithms, Theoretical Computing
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser.
Participants should have some facility with mathematical modes of reasoning. |
Information for Visiting Students
| Pre-requisites | None |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2020/21, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 1 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 20,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
78 )
|
| Assessment (Further Info) |
Written Exam
50 %,
Coursework
50 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Students will be given written assignments to reinforce the material taught in class. This includes two marked coursework as well as bi-weekly tutorial sheets. The tutorial sheets will not be marked, but their solutions will be discussed during the tutorials.
Each coursework contains five problems. The coursework will be focusing on testing basic computational complexity notions and solving problems related to them. Mathematical skills will be important to solve these problems. One should expect to spend about 2-10 hours on each coursework.
|
| Feedback |
Not entered |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S1 (December) | | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- Students will be able to formulate computational models with resource constraints, and be able to describe relationships between these models.
- Students will be able to analyse computational problems from a complexity perspective, and so locate them within the complexity landscape.
- Students will be able to apply mathematical skills and knowledge from earlier years (eg., from logic and discrete mathematics) to concrete problems in computational complexity.
- Students will gain an appreciation of the broader importance of fundamental problems in computer science, such as the P vs NP problem.
|
Reading List
1. Sanjeev Arora and Boaz Barak, 'Computational Complexity: A Modern Approach', Cambridge University
Press, 2009. Required
2. Michael Sipser, 'Introduction to the Theory of Computation', PWS, 1997. Background reading
3. Christos Papadimitriou, 'Computational Complexity', Addison-Wesley, 1994. Supplementary reading
4. Uwe Schoening, 'Gems of Theoretical Computer Science', Springer Verlag, 1998. Supplementary
reading |
Contacts
| Course organiser | Dr Heng Guo
Tel: (0131 6)51 3175
Email: hguo@exseed.ed.ac.uk |
Course secretary | Miss Clara Fraser
Tel: (0131 6)51 4164
Email: clara.fraser@ed.ac.uk |
|
|
University Homepage