DD2350 Algorithms, Data Structures and Complexity 9.5 credits

Algoritmer, datastrukturer och komplexitet

  • Education cycle

    Second cycle
  • Main field of study

    Computer Science and Engineering
  • Grading scale

    A, B, C, D, E, FX, F

Course offerings

Autumn 18 adk18 for programme students

Intended learning outcomes

After completion of the course, students should be able to:

  • develop and implement algorithms with data structures and analyse them with respect to correctness and efficiency,
  • compare alternative algorithms and data structures regarding efficiency and reliability,
  • define and translate central concepts such as P, NP, NP-completeness and undecidability,
  • compare problems with respect to complexity by means of reductions,
  • handle problems with high complexity

in order to

  • independently construct computer programs that use time and memory efficiently,
  • in professional life identify and attack problems that are unrealistically resource demanding or not possible to solve on a computer.

Course main content

Design principles of algorithms: Decomposition, greedy algorithms, dynamic programming, local and exhaustive search. Algorithm analysis. Approximation algorithms and heuristics. Applications with algorithms for problems on sets, graphs, arithmetic and geometry. Implementation of algorithms.

Data structures: Review of hash tables and heaps; balanced trees, Bloom filters. Use and implementation of data structures. Computability and complexity: The concept of reduction, the complexity classes P (polynomial time) and NP (non-deterministic polynomial time). NP-complete problems, undecidable problems. Coping with computationally intractable problems. Terminology in Swedish and English.

Eligibility

Programming and computer science corresponding to DD1338/DD1320/DD1321/DD1325/DD1327/DD1339/ID1020.

Recommended prerequisites

Discrete mathematics corresponding to SF1671 and SF1688 or one of SF1630, SF1662, SF1679 (can be taken in parallel. Probability theory and statistics corresponding to SF1901.

Literature

Will be announced on the course web no later than 10 weeks before the start of the course.

Examination

  • LAB1 - Laboratory assignments, 4.0, grading scale: A, B, C, D, E, FX, F
  • MAS1 - Individual master´s test, 1.5, grading scale: A, B, C, D, E, FX, F
  • MAS2 - Individual master´s test, 1.5, grading scale: A, B, C, D, E, FX, F
  • TEN1 - Theory examination, 2.5, grading scale: P, F

Under certain circumstances, other examination forms may be used.
In this course, the code of honor of the school is applied, see: http://www.kth.se/en/csc/student/hederskodex

Offered by

CSC/Theoretical Computer Science

Contact

Viggo Kann (viggo@kth.se)

Examiner

Viggo Kann <viggo@kth.se>

Supplementary information

Grading critera will be published at the start of the course.

The course has replaced DD1352.

DD2350 cannot be combined with DD1352, DD2352, or DD2354.

Add-on studies

DD2440 Advanced Algorithms, DD2442 Seminars in Theoretical Computer Science, DD2445 Complexity Theory, DD2448 Foundations of Cryptography, and DD2458 Problem Solving and Programming under Pressure.

Version

Course syllabus valid from: Autumn 2018.
Examination information valid from: Autumn 2017.