# DD2354Algorithms and Complexity6.0 credits

## Algoritmer och komplexitet

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

Second cycle

C
• #### Subject area

Information Technology
• #### Grade scale

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

At present this course is not scheduled to be offered.

## Learning outcomes

The goals of the course are to give the students

• the fundamental skills needed to develop algorithms using data structures and analyze their correctness and efficiency,
• an introduction to complexity theory,

so that they will be able to

• design programs that use computer resources efficiently,
• realize that there are problems that are impractical or even impossible to solve by a computer.

Principles for construction of algorithms: Decomposition, greedy algorithms, dynamic programming. Algorithm analysis. Probalistic algorithms. Approximation. Selected applications to sets, graphs, arithmetic, and geometry.

Computability and complexity: Reduction. Complexity classes P (polynomial time), NP (non-deterministic polynomial time), and NC (efficiently parallelizable problems). NP-complete problems. Undecidable problems.

## Eligibility

Single course students: 90 university credits including 45 university credits in Mathematics or Information Technology. English B, or equivalent.

## Literature

To be announced at least 4 weeks before course start at course web page.

## Examination

• MAS1 - Test, 1.5 credits, grade scale: A, B, C, D, E, FX, F
• MAS2 - Test, 1.5 credits, grade scale: A, B, C, D, E, FX, F
• TEN1 - Examination, 3.0 credits, grade scale: A, B, C, D, E, FX, F

In this course all the regulations of the code of honor at the School of Computer science and Communication apply, see: http://www.kth.se/csc/student/hederskodex/1.17237?l=en_UK.

## Requirements for final grade

Test (MAS1; 1,5 university credits and MAS2; 1,5 university credits), examination (TEN1; 3 university credits).

## Offered by

CSC/Computer Science

## Contact

Johan Karlander, tel: 790 6340, e-post: johank@nada.kth.se

Johan Karlander

## Supplementary information

This course has been replaced by DD2352.

Only one of the following courses can be counted in your degree: 2D1352/DD1352, 2D1354/DD2354, 2D1353.