DD2350 Algorithms, Data Structures and Complexity 9.5 credits
Algoritmer, datastrukturer och komplexitet
Education cycleSecond cycle
Main field of studyComputer Science and Engineering
Grading scaleA, B, C, D, E, FX, F
Autumn 18 P1 (6.0 credits), P2 (3.5 credits)
Language of instruction
Form of study
Number of places
Stefan Nilsson <email@example.com>
Viggo Kann <firstname.lastname@example.org>
Searchable for all programmes
Part of programme
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.
Programming and computer science corresponding to DD1338/DD1320/DD1321/DD1325/DD1327/DD1339/ID1020.
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.
Will be announced on the course web no later than 10 weeks before the start of the course.
- 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
CSC/Theoretical Computer Science
Viggo Kann (email@example.com)
Viggo Kann <firstname.lastname@example.org>
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.
DD2440 Advanced Algorithms, DD2442 Seminars in Theoretical Computer Science, DD2445 Complexity Theory, DD2448 Foundations of Cryptography, and DD2458 Problem Solving and Programming under Pressure.
Course syllabus valid from: Autumn 2018.
Examination information valid from: Autumn 2017.