Swedish name: Beräkningskomplexitet
This syllabus is valid: 2024-09-02 and until further notice
Course code: 5DV200
Credit points: 7.5
Education level: Second cycle
Main Field of Study and progress level:
Computing Science: Second cycle, has second-cycle course/s as entry requirements
Grading scale: Pass with distinction, Pass with merit, Pass, Pass with distinction, Pass, Fail
Responsible department: Department of Computing Science
Revised by: Faculty Board of Science and Technology, 2024-02-14
Some algorithms solve a computational problem more efficiently than others. An important aspect of working as a computer scientist is to find efficient ways to solve a given problem. Sometimes one is successful, sometimes not. But how do we know in the latter case whether this is due to our own inability or lies in the nature of the problem, i.e. whether the problem can be solved effectively at all? Each problem has an inherent computational complexity that determines if it is solvable and, if so, how efficiently it can be solved. This leads to a categorization of problems in different classes with regard to their inherent complexity. Understanding this is important because it shows which level of efficiency one can reasonably expect. On the one hand, this leads to more efficient algorithms to the extent possible. On the other hand, it prevents the computer scientist from wasting energy by trying to achieve the impossible.
The course addresses and formalises this inherent complexity of computational problems, resulting in the categorization of problems into different complexity classes, known and unknown relationships between these classes, and the concept of complete problems. The following aspects are addressed: Formalization of computational complexity (primarily in terms of time and memory space) and its practical significance, the speedup theorem and the extended Church-Turing thesis, deterministic and non deterministic complexity classes (predominantly (N)TIME(f(n)), (N)SPACE(f(n)), P, NP, (N)EXPTIME, L, NL, PSPACE; complement classes to those) and what is known or unknown about their mutual relationship, reducing a problem to another one, completeness.
Module 1, Concepts, results and proofs, 3 ECTS credits, consists of lectures that introduce and discuss concepts, results and their proofs according to the above contents desciption. Every lecture is related to one ore more sections of the textbook and provides an introduction to the material without considering any details. The goal is to make it easier for the student to obtain a deeper understanding by working with the material themselves.
Module 2, Deepening, reflection, and discussion, 4.5 ECTS credits, consists of the student's own work with the textbook, and student-guided discussion sessions. When the teacher has presented an overview of sections in the textbook, the student reads those sections and prepares a basic presentation of the material as a basis for discussion with the classmates. A mandatory summary of the central points is handed in before the next lecture (about 1 page). The summary shall in particular mention aspects the student did not manage to comprehend or feels uncertain about. The same holds for possible exercises that the teacher may specify to provide guidance. Students will then be selected in random order to present the material based on their own understanding, and to lead the discussion in the class. Every student has to make at least one such presentation.
Knowledge and understanding
Upon completion of the course, the student will, with mathematical accuracy, be able to define, explain and discuss
Competence and skills
Upon completion of the course, the student should be able to
Judgement and approach
Upon completion of the course, the student should be able to
At least 90 ECTS, including 60 ECTS Computing Science. At least 7.5 ECTS discrete mathematics; 7.5 ECTS data structures and algorithms; and 7.5 ECTS formal languages. Proficiency in English equivalent to the level required for basic eligibility for higher studies.
The teaching is as described in section Contents and consists of both overview lectures and student-led presentations and discussions of the material.
Module 1 (FSR 1-4, 6-8) is examined by a written exam in halls. The grades given on this module are Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5).
Module 2 (FSR 1-8) is examined by written assignments and oral presentations. In Module 2, one of the grades Fail (U) and Pass (G) is given.
On the course in its entirety, one of the grades Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5) is given. The grade on the course is determined by the grade on Module 1.
Adapted examination
The examiner can decide to deviate from the specified forms of examination. Individual adaptation of the examination shall be considered based on the needs of the student. The examination is adapted within the constraints of the expected learning outcomes. A student that needs adapted examination shall no later than 10 days before the examination request adaptation from the Department of Computing Science. The examiner makes a decision of adapted examination and the student is notified.
This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If in
doubt, consult the student counselors at the Department of Computing Science and / or the program director of your
program.
If the syllabus has expired or the course has been discontinued, a student who at some point registered for the course is guaranteed at least three examinations (including the regular examination) according to this syllabus for a maximum period of two years from the syllabus expiring or the course being discontinued.
The literature list is not available through the web. Please contact the faculty.