Algorithms and Complexity
7.5 credits cr.
- Gå till denna sida på svenska webben
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.
The courses mentioned under Eligibility are old versions of courses, and correspond to the current courses DA3018 Computer Science for Mathematicians and MM5023 Mathematics III - Combinatorics.
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.
The course consists of three elements; theory, two individual assignments and practical exercises.
The education consists of lectures, exercises, and practical exercises.
Examination for the course is done with a written and oral examination, and written and oral presentation of the practical exercises and the individual assignments. To pass the course, you need to pass all four elements.
A list of examiners can be found on
ScheduleThe 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 literatureNote that the course literature can be changed up to two months before the start of the course.