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 levelSecond cycle
Academic level (A-D)C
Subject areaInformation Technology
Grade scaleA, B, C, D, E, FX, F
At present this course is not scheduled to be offered.
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.
Single course students: 90 university credits including 45 university credits in Mathematics or Information Technology. English B, or equivalent.
To be announced at least 4 weeks before course start at course web page.
- 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).
Johan Karlander, tel: 790 6340, e-post: firstname.lastname@example.org
This course has been replaced by DD2352.
Only one of the following courses can be counted in your degree: 2D1352/DD1352, 2D1354/DD2354, 2D1353.
DD2440 Advanced Algorithms, DD2441 Seminars in Theoretical Computer Science, DD2446 Complexity Theory, DD2450 Algorithmic Bioinformatics, and DD2458 Problem Solving and Programming under Pressure.
Course plan valid from:
Examination information valid from: Autumn 07.