Nada

Nadas institutionssymbol

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

på svenska

Course description 1997/98

2D1353 Algorithms, Data Structures, and Complexity

KTH credits6Lectures48
LevelCTutorials24
Grading, KTHU, 3, 4, 5Lab work-
Compulsory forDOtherIndividual work
Elective forE,Periods3-4
LanguageEnglish

Coordinator

Rand Waltzman, +46 - 8 - 790 6337, rand@nada.kth.se

Abstract

Second course in computer science focusing on algorithms, data structures and complexity.

Goals

The goals of the course are to give the students so that they will be able to

Syllabus

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.

Prerequisites

2D1340 (or 2D1341) Introduction to Computer Science and 5B1203  Discrete Mathematics (can be taken concurrently) or the equivalent.

Follow-up

2D1440 Advanced Algorithms, 2D1443 Parallel Computations and 2D1446 Complexity Theory

Examination

A written examination (TEN1; 4 cr.).
Laboratory assignments (LAB1; 2 cr.).

Course material

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>