Course syllabus - Computational complexity
Scope
7.5 credits
Course code
MAA513
Valid from
Autumn semester 2020
Education level
Second cycle
Progressive Specialisation
A1N (Second cycle, has only first-cycle course/s as entry requirements).
Main area(s)
Mathematics/Applied Mathematics
School
School of Education, Culture and Communication
Ratified
2019-12-09
Literature lists
Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.
-
Books
The nature of computation
Oxford : Oxford University Press, 2011 - 985 s.
ISBN: 9780199233212 LIBRIS-ID: 11354166
Objectives
The objective of the course is to give the student the opportunity to acquire basic knowledge of the theory of computational complexity and its applications.
Learning outcomes
Upon completion of the course, the student is expected to be able to
1. define the complexity classes P, NP, PSPACE, BPP and BPQ, and explain how they are related
2. explain some central NP-hard problems, such as the traveling salesperson problem and 3-SAT, and some problems in P
3. carry out simple proofs by reduction to show that a problem is NP-hard
4. describe approximation algorithms for certain NP-hard problems
5. explain expected areas of use, and limitations of, quantum computers
Course content
- Turing machines, formal languages, boolean circuits
- Big-O notation
- Complexity classes: P, NP, PSPACE, BPP, BQP
- Approximation algorithms and approximability
- Quantum algorithms, limitations of quantum computing
- Applications within optimization, machine learning, data analysis, and mathematical proof
Specific requirements
Discrete Mathematics, 7.5 credits, Probability, 7.5 credits and Programming, 7.5 credits, or equivalent. In addition, Swedish B/Swedish 3 and English A/English 6 are required. In cases when the course is offered in English, the requirement for Swedish B/Swedish 3 is excluded.
Examination
TEN1, Written examination, 7.5 credits, individual written examination concerning learning outcomes 1-5, grades Fail (U), 3, 4 or 5.
A student who has a certificate from MDU regarding a disability has the opportunity to submit a request for supportive measures during written examinations or other forms of examination, in accordance with the Rules and Regulations for Examinations at First-cycle and Second-cycle Level at Mälardalen University (2020/1655). It is the examiner who takes decisions on any supportive measures, based on what kind of certificate is issued, and in that case which measures are to be applied.
Suspicions of attempting to deceive in examinations (cheating) are reported to the Vice-Chancellor, in accordance with the Higher Education Ordinance, and are examined by the University’s Disciplinary Board. If the Disciplinary Board considers the student to be guilty of a disciplinary offence, the Board will take a decision on disciplinary action, which will be a warning or suspension.
Grade
Pass with distinction, Pass with credit, Pass, Fail