THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2017/2018

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Computational Complexity (INFR11102)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Year 4 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryThis 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
* Diagonalization
* The polynomial hierarchy and alternations
* Circuits
* Randomized computation
* Hardness of approximation and the PCP theorem

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-requisitesNone
High Demand Course? Yes
Course Delivery Information
Academic year 2017/18, Available to all students (SV1) Quota:  None
Course Start Semester 2
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 75 %, Coursework 25 %, Practical Exam 0 %
Additional Information (Assessment) Three collections of pencil-and-paper exercises issued at approximately three-week intervals.

You should expect to spend approximately 25 hours on the coursework for this course.

If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.
Feedback Not entered
No Exam Information
Learning Outcomes
On completion of this course, the student will be able to:
  1. Students will be able to formulate computational models with resource constraints, and be able to describe relationships between these models.
  2. Students will be able to analyse computational problems from a complexity perspective, and so locate them within the complexity landscape.
  3. 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.
  4. 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
Additional Information
Course URL http://course.inf.ed.ac.uk/cmc/
Graduate Attributes and Skills Not entered
KeywordsNot entered
Contacts
Course organiserDr Heng Guo
Tel: (0131 6)51 3175
Email: hguo@exseed.ed.ac.uk
Course secretaryMr Gregor Hall
Tel: (0131 6)50 5194
Email: gregor.hall@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information