- Design principles of algorithms: decomposition, greedy algorithms, dynamic programming, local and exhaustive search.
- Algorithm analysis.
- Approximation algorithms and heuristics.
- Applications with algorithms for problems on sets, graphs, arithmetic, and geometry.
- Implementation of algorithms.
- Data structures: review of hash tables and heaps; balanced trees, Bloom filters, persistent data structures.
- Use and implementation of data structures.
- Computability and complexity: the concept of reduction, the complexity classes P (polynomial time) and NP (non-deterministic polynomial time).
- NP-complete problems, undecidable problems.
- Coping with computationally intractable problems.
- Terminology in Swedish and English.
After passing the course, the student should be able to:
- Develop and implement algorithms with data structures and analyse them with respect to correctness and efficiency
- Compare alternative algorithms and data structures regarding efficiency and reliability
- Define and translate central concepts such as P, NP, NP-completeness and undecidability
- Compare problems with respect to complexity by means of reductions
- Handle problems with high complexity
In order to:
- Independently design computer programs that use time and memory efficiently and thereby contribute to economically and environmentally sustainable development
- In professional life, identify and tackle problems that are unrealistically resource-demanding or not possible to solve on a computer