Algorithms and Computability


Recommended prerequisite for participation in the module

The module builds on knowledge gained in modules: The Theoretical Foundations of Computer Science, Algorithms and Data Structures and Syntax and Semantics.

Content, progress and pedagogy of the module

This is an English translation of the module. In case of discrepancy between the translation and the Danish version, the Danish version of the module is valid.

Learning objectives


The student must gain knowledge of the following theories and methods:

  • algorithm design techniques such as share-and-rule, greedy algorithms, dynamic programming, backtracking, branch-and-bound algorithms, randomized algorithms and linear programming
  • techniques in advanced algorithm analysis such as amortized analysis, analysis of expected complexity and experiments with algorithms
  • examples of core algorithms and data structures for solving a number of problems from different areas of computer science such as algorithms for external memory, multi-threaded algorithms, search in text, advanced graph algorithms and geometric calculations
  • decisive and recognizable decision-making problems; Turing machines; Church-Turing thesis; examples of reduction
  • complexity theory: deterministic and nondeterministic Turing machines and their time complexity; time complexity classes; polynomial reductions; NP completeness; examples of NP-complete problems


  • be able to account accurately and using the subject's terminology and notation for important results within calculation complexity and for how and to what extent these results can be used to classify calculation problems, including complexity analysis and applications of reductions
  • explain the principles behind the most important algorithm design and analysis techniques
  • select and apply algorithm design and analysis techniques for a given problem
  • recognize a range of problems from different areas of computer science and select the most appropriate algorithms and data structures to solve them


  • be able to apply concepts and techniques within computational complexity to analysis of computational problems
  • when facing a computer science problem, be able to develop and analyze efficient algorithms and data structures for solving the problem

Type of instruction

The teaching is organized in accordance with the general teaching methods for the education, cf. section 17.

Extent and expected workload

The student is expected to spend 27.5 hours per ECTS, which for this activity means 137.5 hours.



Name of examAlgorithms and Computability
Type of exam
Written or oral exam
Assessment7-point grading scale
Type of gradingInternal examination
Criteria of assessmentThe criteria of assessment are stated in the Examination Policies and Procedures

Additional information

Kontakt: Studienævn for datalogi via eller 9940 8854

Facts about the module

Danish titleAlgoritmer og beregnelighed
Module codeDSNSWCB611
Module typeCourse
Duration1 semester
Language of instructionDanish
Empty-place SchemeYes
Location of the lectureCampus Copenhagen
Responsible for the module


Education ownerBachelor of Science (BSc) in Engineering (Software)
Study BoardStudy Board of Computer Science
DepartmentDepartment of Computer Science
FacultyThe Technical Faculty of IT and Design