NDAA09007U Computability and Complexity (CoCo)
MSc Programme in Computer Science
MSc Programme in Physics
In computing, there is continual tension between time usage and
space usage, and what can be computed and what cannot be computed
at all. The purpose of this course is to explore these issues.
Content:
- Regular languages
- Context-free languages
- Turing machines
- Decidability
- Reducibility
- Complexity
- Complexity classes (P, NP, PSPACE, EXPSPACE, L, and NL)
- Intractability
At course completion, the successful student will have:
Knowledge of
- Computational models such as finite automata, pushdown automata, and Turing machines, the languages recognised by some of these models, and techniques for showing their limitations, such as the pumping lemmas for regular and for context-free languages.
- The power and limits of algorithmic solvability, with focus on the computationally unsolvable Halting problem.
- The reducibility method for proving that additional problems are computationally unsolvable.
- How to analyse algorithms and their time and space complexity and how to classify problems according to the amount of time and space required to solve them.
- Known computational problems that are solvable in principle but not in practice, i.e. intractable problems.
Skills in
- Reading and writing specifications of languages using computational models and grammars.
- Classifying given languages according to type (regular, context-free, etc.) and algorithmic problems according to complexity (time and space).
- Showing the equivalence between certain machine models.
- Presenting the relevant constructions and proofs in writing, using precise terminology and an appropriate level of technical detail.
Competences to
- Reason reliably about language classes and computational models and their strengths and limitations, and about the complexity of algorithms and algorithmic problems.
- Communicate effectively about the theory of computation, both for accessing advanced topics from the research literature, and convincingly presenting the results of own work.
Is expected to be: Introduction to the Theory of Computation, Michael Sipser, International third edition. See Absalon when the course is set up.
Academic qualifications equivalent to a BSc degree is recommended.
- Category
- Hours
- Lectures
- 36
- Preparation
- 157
- Theory exercises
- 9
- Exam
- 4
- Total
- 206
As
an exchange, guest and credit student - click here!
Continuing Education - click here!
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- Credit
- 7,5 ECTS
- Type of assessment
- Written examination, 4 hours under invigilationAll books and notes may be brought to the exam.
In 2022 the exam will be held as an ITX-analogue exam. This means that the exam assignment will be handed out electronically via the ITX-computer, while the students hand-in must be written with pen and paper. - Exam registration requirements
Assignments will be made each week and be due in the following week. 5 assignments out of the 7 must be completed by the due date and approved to qualify for the exam.
- Aid
- Written aids allowed
The University will make computers available to students taking on-site exams at ITX. Students are therefore not permitted to bring their own computers, tablets or mobile phones. If textbooks and/or notes are permitted, according to the course description, these must be in paper format or uploaded through Digital Exam.
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
- Re-exam
If a student is not qualified then qualification can be achieved by submitting and approval of equivalent assignments no later than two weeks before the re-exam.
The re-exam will also be a 4 hours written exam with invigilation, unless 10 or fewer students register for the re-exam; in this case the re-exam will be a 25 minutes oral examination without preparation. All aids are allowed at the oral examination.
Criteria for exam assesment
See Learning Outcome.
Course information
- Language
- English
- Course code
- NDAA09007U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 3
- Schedule
- A
- Course capacity
- No limit
The number of seats may be reduced in the late registration period - Course is also available as continuing and professional education
- Study board
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Contracting faculty
- Faculty of Science
Course Coordinators
- Christian Wulff-Nilsen (koolooz@di.ku.dk)