Stockholm university
Gå till denna sida på svenska webben

Algorithms and Complexity

What does an algorithm cost, in time and memory? Learn to compare alternative algorithms, construct computer programs that use time and memory efficiently and identify and attack problems that are unrealistically resource demanding or not possible to solve on a computer.

In this course you will learn to develop and implement algorithms and analyze them with respect to correctness and efficiency; define the concepts P, NP, NP-completeness, undecidability, etc, to be able to identify and attack problems that are unrealistically resource demanding or not possible to solve, and to construct computer programs that use time and memory efficiently.

Course contents

Principles for construction of algorithms: Decomposition, greedy algorithms, dynamic programming, local and total search. Algorithm analysis. Approximation, algorithms and heuristics. Selected applications to sets, graphs, arithmetic, and geometry. Implementation of algorithms.

Data structures: Repetition of hash tables and heaps; balanced trees and randomised data structures. Use and implementation of data structures.

Computability and complexity: Reduction. Complexity classes P (polynomial time) and NP (non-deterministic polynomial time). NP-complete problems. Undecidable problems. Coping with untractable problems.

  • Course structure

    The course consists of three elements; theory, individual assignment and practical exercises.

    Teaching format

    The education consists of lectures, exercises, and practical exercises.

    Assessment

    The course is assessed through written examination, written and oral presentation of the practical exercises, and a home assignment and oral presentation of the assignment.

    Examiner

    A list of examiners can be found on

    Exam information

  • Schedule

    The schedule will be available no later than one month before the start of the course. We do not recommend print-outs as changes can occur. At the start of the course, your department will advise where you can find your schedule during the course.

  • Course literature

    Note that the course literature can be changed up to two months before the start of the course.

    Cormen, Leiserson, Rivest, and Stein: Introduction to algorithms.

    List of course literature Department of Mathematics

  • More information

    New student
    During your studies

    Course web

    We do not use Athena, you can find our course webpages on kurser.math.su.se.

  • Contact

Selected reading

Three students outdoors in front of a computer.

Step-by-step guide

Here we explain all the different steps you need to go through when applying to a course or programme. Please read the instructions carefully.

Two happy students looking at a mobile phone.

Meet us online and around the world

Stockholm University arranges regular webinars and participates in educational fairs and events virtually and around the world to meet students and inform them about our study programmes. Meet us and ask what it's like to study with us!

Students of Stockholm University

Every year Stockholm University welcomes thousands of international students from all over the world. Each bringing their own backpack full of experiences, expectations and dreams. Each with their own story.

Photo montage of close-ups of researchers.

Our researchers. Your teachers

As a student at Stockholm University, you will have direct contact with leading researchers in your field and access to the most recent scientific findings. Our researchers. Your teachers. Meet a few of them here.

Mikaela Sörman

Hear from our alumni

Are you wondering what former students thought about your programme? Are you curious about what your education can lead to after graduation? Hear from our alumni!

Show more