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.
Information for admitted students autumn 2024
Congratulations! You have been admitted at Stockholm University and we hope that you will enjoy your studies with us.
In order to ensure that your studies begin as smoothly as possible we have compiled a short checklist for the beginning of the semester.
Follow the instructions on whether you have to reply to your offer or not.
universityadmissions.se
Checklist for admitted students
-
Activate your university account
The first step in being able to register and gain access to all the university's IT services.
-
Register at your department
Registration can be done in different ways. Read the instructions from your department below.
-
Read all the information on this page
Here you will find what you need to know before your course or programme starts.
IMPORTANT
Your seat may be withdrawn if you do not register according to the instructions provided by your department.
Information from your department
On this page you will shortly find information on registration, learning platform, etc.
Welcome activities
Stockholm University organises a series of welcome activities that stretch over a few weeks at the beginning of each semester. The programme is voluntary (attendance is optional) and includes Arrival Service at the airport and an Orientation Day, see more details about these events below.
Your department may also organise activities for welcoming international students. More information will be provided by your specific department.
Find your way on campus
Stockholm University's main campus is in the Frescati area, north of the city centre. While most of our departments and offices are located here, there are also campus areas in other parts of the city.
Read more
For new international students
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
-
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.
-
More information
New student
During your studiesCourse web
We do not use Athena, you can find our course webpages on kurser.math.su.se.
-
Contact