DD232V Algorithms and Complexity 7.5 credits

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.

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.

• Knowledge of algorithms and data structures, 6 credits, equivalent to completed course DD1320.
• Knowledge and skills in programming, 6 credits, equivalent to completed course DD100N.
• Knowledge of linear algebra, 7.5 credits, equivalent to completed course SF1624.
• Knowledge of one-variable analysis, 7.5 credits, equivalent to completed course SF1625.
• Knowledge of discrete mathematics, 7.5 credits, equivalent to completed course SF1698.
• Skills in English equivalent to the upper secondary school course English B/English 6.

• MAS1 - Mastery Test, 1.5 credits, grading scale: A, B, C, D, E, FX, F
• MAS2 - Mastery Test, 1.5 credits, grading scale: A, B, C, D, E, FX, F
• LAB1 - Laboratory Work, 1.5 credits, grading scale: P, F
• TEN2 - Written Exam, 3.0 credits, grading scale: P, 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. If the course is discontinued, students may request to be examined during the following two academic years.

The mastery tests consist of individual assignments that are submitted in written form and presented orally.

Per Austrin

• 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.