På Svenska

DD2354 Algorithms and Complexity 6.0 credits

Algoritmer och komplexitet

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

  • Educational level

    Second cycle

  • Academic level (A-D)

    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.

Course main content

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

Examiner

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.

Add-on studies

DD2440 Advanced Algorithms, DD2441 Seminars in Theoretical Computer Science, DD2446 Complexity Theory, DD2450 Algorithmic Bioinformatics, and DD2458 Problem Solving and Programming under Pressure.

Version

Course plan valid from: Autumn 09.
Examination information valid from: Autumn 07.