Computability and Complexity (CoCo)

Course content

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

 

In addition, the course covers topics in complexity that reflect the current state of research as well as instructor and participant backgrounds and interests; the particular topic(s) change from year to year. Please contact the course organizer for more information on the topics covered.

Education

MSc Programme in Computer Science
MSc Programme in Physics

Learning outcome

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.

 

Lectures and exercise classes.

Is expected to be: Introduction to the Theory of Computation, Michael Sipser, International third edition. See Absalon when the course is set up.

Basic algorithms and discrete mathematics course(s). The course "Logic in Computer Science" would be useful, but is not essential.

Academic qualifications equivalent to a BSc degree is recommended.

Written
Individual
Collective
Continuous feedback during the course
ECTS
7,5 ECTS
Type of assessment
Written examination, 4 hours under invigilation
Type of assessment details
All books and notes may be brought to the exam.
The course has been selected for ITX exam.
See important information about ITX-exams at Study Information, menu point: Exams -> Exam types and rules -> Written on-site exams (ITX).
Aid
Written aids allowed

As the exam is an ITX-exam, the University will make computers available to students at the exam. Students are therefore not permitted to bring their own computers, tablets, calculators, or mobile phones.

Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Criteria for exam assessment

See Learning Outcome.

Single subject courses (day)

  • Category
  • Hours
  • Lectures
  • 36
  • Preparation
  • 157
  • Theory exercises
  • 9
  • Exam
  • 4
  • English
  • 206

Kursusinformation

Language
English
Course number
NDAA09007U
ECTS
7,5 ECTS
Programme level
Full Degree Master
Duration

1 block

Placement
Block 3
Schedulegroup
A
Capacity
No limit
The number of seats may be reduced in the late registration period
Studyboard
Study Board of Mathematics and Computer Science
Contracting department
  • Department of Computer Science
Contracting faculty
  • Faculty of Science
Course Coordinator
  • Jakob Nordström   (2-6d7143676c316e7831676e)
Saved on the 10-11-2022

Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students