Skip to main content

DD2352 Algorithms and Complexity 7.5 credits

Second course in computer science focusing on algorithms and complexity, more theoretical than DD1352.

Choose semester and course offering

Choose semester and course offering to see current information and more about the course, such as course syllabus, study period, and application information.

Headings with content from the Course syllabus DD2352 (Spring 2024–) are denoted with an asterisk ( )

Content and learning outcomes

Course contents

Design principles of algorithms: Divide and conquer, greedy algorithms, dynamic programming. Algorithm analysis. Probabilistic algorithms. Approximation algorithms. Selected applications in sets, graphs, arithmetic and geometry. Implementation of algorithms.

Computability and complexity: Reductions. The complexity classes P (polynomial time), NP (non-deterministic polynomial time), PSPACE (polynomial space) and BPP (probabilistic polynomial time with bounded error). NP completeness and NP hardness reductions. Undecidable problems.

Intended learning outcomes

After passing the course, the student should be able to

  • develop and implement algorithms and reductions, and analyse them with respect to correctness and efficiency
  • compare alternative algorithms considering efficiency
  • define and explain central concepts such as P, NP, NP-completeness and undecidability
  • compare problems with respect to complexity by means of reductions

in order to

  • independently be able to design computer programs that use time and memory efficiently and thereby can contribute to economically and environmentally sustainable development
  • in professional life identify problems that are unrealistically resource demanding or not possible to solve on a computer.

Course disposition

No information inserted

Literature and preparations

Specific prerequisites

Knowledge in basic computer science, 6 credits, equivalent to completed course DD1338/DD1320-DD1328/DD2325/ID1020/ID1021.

Knowledge and skills in programming, 6 credits, equivalent to completed course DD1310-DD1319/DD1321/DD1331/DD1337/DD100N/ID1018.

Knowledge in calculus in one variable, 7.5 higher education credits, equivalent to completed course SF1625.

Course from Upper Secondary School equivalent to the Swedish upper secondary course English B/6.

Active participation in a course offering where the final examination is not yet reported in LADOK is considered equivalent to completion of the course. Being registered for a course counts as active participation. The term 'final examination' encompasses both the regular examination and the first re-examination.

Recommended prerequisites

Knowledge of discrete mathematics is necessary. A student who, at the beginning of the course, has not completed 7.5 higher education credits of discrete mathematics, equivalent to SF1610/SF1662/SF1679/SF1688, must take one of these courses in parallel with DD2352, see Additional Regulations in the course syllabus.

Knowledge of probability theory equvalent to for example SF1901 Probability Theory and Statistics is recommended but could be learnt during the course.

Equipment

No information inserted

Literature

No information inserted

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale

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

Examination

  • LAB1 - Laboratory Work, 1.5 credits, grading scale: P, F
  • MAS1 - Test, 1.5 credits, grading scale: A, B, C, D, E, FX, F
  • MAS2 - Test, 1.5 credits, grading scale: A, B, C, D, E, FX, F
  • TEN1 - Examination, 3.0 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Labs and mastery tests are examined both orally and in writing. The exam is written.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web DD2352

Offered by

Main field of study

Computer Science and Engineering

Education cycle

Second cycle

Add-on studies

DD2440 Advanced Algorithms, DD2452 Seminars in Theoretical Computer Science, Algorithms and Complexity, DD2445 Complexity Theory, and DD2458 Problem Solving and Programming under Pressure.

Contact

Per Austrin, e-post: austrin@kth.se

Supplementary information

This course has replaced DD2354 Algorithms and Complexity.

The course cannot be combined with any of the courses DD1352, DD2350, DD2354.

In this course, the EECS code of honor applies, see:
http://www.kth.se/en/eecs/utbildning/hederskodex

Additional regulations

A student who, at the beginning of the course, has not completed 7.5 higher education credits of discrete mathematics, equivalent to SF1610/SF1662/SF1679/SF1688, must take one of these courses in parallel with DD2352.