Up to *the home page of the course (in Swedish)*

på svenska

## Course description 1997/98

# 2D1353 Algorithms, Data Structures, and Complexity

KTH credits | 6 | Lectures | 48 |

Level | C | Tutorials | 24 |

Grading, KTH | U, 3, 4, 5 | Lab work | - |

Compulsory for | D | Other | Individual work |

Elective for | E, | Periods | 3-4 |

Language | English |

Rand Waltzman, +46 - 8 - 790 6337,
rand@nada.kth.se
Second course in computer science focusing on algorithms, data structures and
complexity.
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. Selected applications to
sets, graphs, arithmetic, and geometry.
*Computability and complexity*: Reduction. Complexity classes P
(polynomial time), NP (non-deterministic polynomial time). NP-complete
problems. Undecidable problems.

2D1340 (or 2D1341) Introduction to Computer Science and 5B1203 Discrete
Mathematics (can be taken concurrently) or the equivalent.
2D1440 Advanced Algorithms, 2D1443 Parallel Computations and
2D1446 Complexity Theory
A written examination (TEN1; 4 cr.).

Laboratory assignments (LAB1; 2 cr.).
Reading list available at the department. In 96/97: T. Cormen, D
Leiserson & R. Rivest: Introduction to algorithms, MIT Press, 1994.
Link to course description 1996/97

Up to *the home page of the course (in Swedish)*

Responsible for this page: <www-kurs@nada.kth.se>

Latest change June 9, 1997

Technical support: <webmaster@nada.kth.se>