Undergraduate Course: Computational Complexity (INFR10008)
Course Outline
| School |
School of Informatics |
College |
College of Science and Engineering |
| Course type |
Standard |
Availability |
Available to all students |
| Credit level (Normal year taken) |
SCQF Level 10 (Year 4 Undergraduate) |
Credits |
10 |
| Home subject area |
Informatics |
Other subject area |
None |
| Course website |
http://www.inf.ed.ac.uk/teaching/courses/cmc |
|
|
| Course description |
The module extends a line of study, begun in CS3 Computability and Intractability, in which computational problems are classified according to their intrinsic difficulty or ``complexity.'' We formalise the notion of complexity of a problem as the amount of time (or space) required to solve the problem on a simple universal computing device, namely the Turing machine. We study some fundamental features of computation in this model, such as time and space hierarchies, the relationship between time and space, and between determinism and non-determinism. We introduce a number of natural complexity classes, which are essentially independent of the Turing machine model, and characterise these classes by identifying some of their complete (i.e., hardest) problems. We then introduce a computational model based on Boolean circuits that allows us to classify problems according to their parallel complexities; as with sequential computation, we are able to separate those problems that can be solved efficiently on a parallel computer from those that (apparently) cannot. Next, we examine the role of randomisation (allowing occasional incorrect answers) in making apparently intractable problems easier. We meet a surprising characterisation of the class NP in terms of ``probabilistically checkable proofs,'' and make an equally surprising connection between this new view of NP and non-approximability of combinatorial optimisation problems. Finally, we investigate some really hard problems that are provably intractable. |
Entry Requirements
| Pre-requisites |
|
Co-requisites |
|
| Prohibited Combinations |
|
Other requirements |
Successful completion of Year 3 of an Informatics Single or Combined Honours Degree, or equivalent by permission of the School. Participants should have some facility with mathematical modes of reasoning.
|
| Additional Costs |
None |
Course Delivery Information
|
| Delivery period: 2010/11 Semester 2, Available to all students (SV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | 15:00 - 15:50 | | | | | | Central | Lecture | | 1-11 | | | | 15:00 - 15:50 | |
| First Class |
Week 1, Monday, 15:00 - 15:50, Zone: Central. Room 1.2, 22 Buccleuch Place |
Summary of Intended Learning Outcomes
1 - Students will be able to formulate models of sequential, randomised and parallel compution, and be able to describe the relationships between these models.
2 - They will be able to quantify the resources employed by these models, such as time, space and circuit size/depth.
3 - Students will be able to analyse computational problems from a complexity perspective, and so locate them within the complexity landscape (a landscape which is much refined from that described in Computability and Intractability).
4 - In particular, they will further develop their skill in conducting a completeness proof, which is in a sense a practical skill.
5 - Students will be able to apply mathematical skills and knowledge from earlier years (e.g., from probability theory and logic) to concrete problems in computational complexity.
6 - Students will study the topic in sufficient depth as to gain an appreciation of some of the challenging issues in computer science today (e.g., P =? NP). |
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
Three collections of pencil-and-paper exercises issued at approximately three-week intervals.
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. |
| Please see Visiting Student Prospectus website for Visiting Student Assessment information |
Special Arrangements
| Not entered |
Contacts
| Course organiser |
Dr Amos Storkey
Tel: (0131 6)51 1208
Email: A.Storkey@ed.ac.uk |
Course secretary |
Miss Kate Weston
Tel: (0131 6)50 2701
Email: Kate.Weston@ed.ac.uk |
|
copyright 2010 The University of Edinburgh -
1 September 2010 6:10 am
|
University Homepage