# DD1352 Algorithms, Data Structures and Complexity 9.0 credits

## Algoritmer, datastrukturer och komplexitet

Second course in computer science focusing on algorithms, data structures and complexity. Same course contents as DD2352 but with a larger lab component.

#### Educational level

First cycle-
#### Academic level (A-D)

C #### Subject area

Information Technology

Technology

#### Grade scale

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

At present this course is not scheduled to be offered.

## Intended learning outcomes

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

- develop and implement algorithms with data structures and analyze them with respect to correctness and efficiency,
- compare alternative algorithms and data structures with respect to efficiency and reliability,
- define and translate central concepts such as P, NP, NP-completeness and undecidability,
- compare problems with respect to complexity using reductions,
- explain how problems of high complexity can be handled

so that they will be able 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

Principles for construction of algorithms: Divide and conquer, greedy algorithms, dynamic programming, local and exhaustive search. Algorithm analysis. Approximation algorithms and heuristics. Selected applications to sets, graphs, arithmetic, and geometry.

Data structures: Review of hash tables and heaps; balanced trees and Bloom filters. Use and implementation of data structures.

Computability and complexity: Reductions. Complexity classes P (polynomial time) and NP (non-deterministic polynomial time). NP-complete problems. Undecidable problems. Coping with untractable problems.

Terminology in Swedish and English.

## Eligibility

For non-program students: completed upper secondary education including documented proficiency in Swedish corresponding to Swedish B, English corresponding to English A. Furthermore: 15 hp in mathematics, including discrete mathematics and probability, and 12 hp in computer science or programming.

## Recommended prerequisites

DD1339/DD1340/DD1341 Introduction to Computer Science (or DD1320/DD1321/DD1345, SF1630/SF1631 Discrete Mathematics (can be taken concurrently), and SF1901 Probability Theory and Statistics, or the equivalent.

## Literature

Kleinberg-Tardos: Algorithm Design, 2005, Pearson, ISBN 978-0321372918 +

Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126.

## Examination

- LAB1 - Laboratory Assignments, 3.0, grade scale: P, F
- MAS1 - Master's test, 1.5, grade scale: A, B, C, D, E, FX, F
- MAS2 - Master's test, 1.5, grade scale: A, B, C, D, E, FX, F
- TEN2 - Examination, 3.0, grade scale: A, B, C, D, E, FX, F

Under special circumstances, other examination formats may be used.

In this course, the code of honor of the school is applied, see: http://www.kth.se/csc/student/hederskodex.

## Requirements for final grade

The final grade is the minimum grade of MAS1, MAS2 and TEN2.

## Offered by

CSC/Theoretical Computer Science

## Contact

Viggo Kann, tel: 790 6292, e-post: viggo@kth.se

## Examiner

Viggo Kann <viggo@kth.se>

## Supplementary information

The course will be replaced from 2017/2018 by the new course DD2350.

Only one of the following courses may be included in your degree: 2D1352, 2D1353, 2D1354, DD1352, DD2350, DD2352, DD2354.

## Add-on studies

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

## Version

Course syllabus valid from: Autumn 2016.

Examination information valid from: Autumn 2007.