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.

Offering and execution

Course offering missing for current semester as well as for previous and coming semesters

Course information

Content and learning outcomes

Course contents *

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.

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 Disposition

No information inserted

Literature and preparations

Specific prerequisites *

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.

Equipment

No information inserted

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 and completion

Grading scale *

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

Examination *

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

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

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.

Other requirements for final grade *

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

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Viggo Kann

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web DD1352

Offered by

CSC/Theoretical Computer Science

Main field of study *

Information Technology, Technology

Education cycle *

First cycle

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.

Contact

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

Ethical approach *

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

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.