- UCAS course code
- FG3C
- UCAS institution code
- M20
Course unit details:
Computation and Complexity
Unit code | MATH43012 |
---|---|
Credit rating | 15 |
Unit level | Level 4 |
Teaching period(s) | Semester 2 |
Available as a free choice unit? | No |
Overview
Quite a lot of the mathematics you have studied so far involves using algorithms to solve computational problems. For example, you have probably used Euclid's algorithm to solve the problem of finding the greatest common divisor of two integers. In this course, we abstract a level further, and study the properties of problems and algorithms themselves. The kind of questions we ask are "is there an algorithm to solve EVERY problem?" and "what problems can be solved by an EFFICIENT algorithm?".
Compared with most of mathematics, this area is in its infancy, and many important things remain unknown. The course will take you to the point where you understand the statement of one of the most important open questions in mathematics and computer science: the "P vs NP" problem, for which the Clay Mathematics Foundation is offering a $1,000,000 prize. And who knows, perhaps one day you will be the one to solve it!
Pre/co-requisites
Unit title | Unit code | Requirement type | Description |
---|---|---|---|
Computation and Complexity | MATH63012 | Anti-requisite | Compulsory |
Students are not permitted to take, for credit, MATH43012 in an undergraduate programme and then MATH63012 in a postgraduate programme at the University of Manchester, as the courses are identical.
Aims
The course unit aims
- to introduce the main model of computation currently being employed in the theory of computation, Turing machines;
- to introduce the key parameters quantifying computational complexity (deterministic, non-deterministic, time, space) and the relationships between them.
Learning outcomes
On successful completion of the course unit students should
- define Turing machines, discuss their capabilities and limitations, and construct and analyse simple examples;
- define the key concepts of computation and complexity (including the main computability and complexity classes), discuss the relationships between them, and prove simple seen and unseen facts about them;
- recall and analyse a range of computational problems and their properties;
- state, apply and prove some of the main theorems of computation and complexity theory;
- classify and compare the computability and complexity of decision problems in simple cases.
Syllabus
0. INTRODUCTION (approx 1 hour): outline introduction to computability and complexity; course practicalities.
1. COMPUTABILITY (approx 9 hours): problems and solutions; alphabets and languages; Turing machines; recursiveness and the Church-Turing Thesis; multitape machines; coding machines and non-recursive languages; universal computation; non-determinism.
2. COMPUTATIONAL COMPLEXITY (approx 7 hours): time and space; linear speed up and space reduction; complexity classes; lower bounds and crossing arguments; space and time hierarchy theorems; tractability and P vs NP; polynomial time reduction.
3. COMPLETENESS (approx 8 hours): NP-completeness; SAT and the Cook-Levin Theorem; NP-completeness by reduction; further examples of NP-complete languages; NP-intermediacy and Ladner's Theorem; PSpace-completeness; oracles and the Baker-Gill-Solovay Theorem.
4. SPACE COMPLEXITY (approx 3 hours): Savitch's Theorem; the Immerman-Szelepcsenyi Theorem.
Assessment methods
Method | Weight |
---|---|
Other | 20% |
Written exam | 80% |
- Coursework: two take home tests weighting 10% each.
- End of course examination: weighting 80%.
Feedback methods
Recommended reading
The course notes are self-contained and you should not need to refer to any books. But if you would like an alternative viewpoint, the following texts cover most of the course material:
- Bovet and Crescenzi, Introduction to the Theory of Complexity, 1994
- Papadimitriou, Computational Complexity, 1994.
- Sipser, Introduction to the Theory of Computation (second edition), 2006.
Study hours
Scheduled activity hours | |
---|---|
Lectures | 11 |
Tutorials | 11 |
Independent study hours | |
---|---|
Independent study | 128 |
Teaching staff
Staff member | Role |
---|---|
Nora Szakacs | Unit coordinator |
Additional notes
The independent study hours will normally comprise the following. During each week of the taught part of the semester:
· You will normally have approximately 75-120 minutes of video content. Normally you would spend approximately 2.5-4 hrs per week studying this content independently
· You will normally have exercise or problem sheets, on which you might spend approximately 2-2.5hrs per week
· There may be other tasks assigned to you on Blackboard, for example short quizzes, short-answer formative exercises or directed reading
· In some weeks you may be preparing coursework or revising for mid-semester tests
Together with the timetabled classes, you should be spending approximately 9 hours per week on this course unit.
The remaining independent study time comprises revision for and taking the end-of-semester assessment.
The above times are indicative only and may vary depending on the week and the course unit. More information can be found on the course unit’s Blackboard page.