1. komponenta

Lecture type	Total
Lectures	45
Exercises	30

COURSE AIMS AND OBJECTIVES:
Enable student to:
- perform time and space complexity analysis of a given algorithm;
- implement advanced classical algorithms and data structures;
- create mathematical models of real-world problems (typically, in terms of graph theory or combinatorial optimization), and then choose or design appropriate solution algorithms, and determine their complexity;
- develop new data structures and algorithms to solve new, non-standard problems.

COURSE DESCRIPTION AND SYLLABUS:
1. Algorithm complexity. Problems and algorithms; time and space complexity. Complexity classes: P and NP, NP-completeness. Algorithm complexity analysis: recursive algorithms; amortized analysis of algorithms.
2. Sorting. Overview of classical sorting algorithms. Sorting in linear time. Finding the i-th element and the median element.
3. Trees and heaps. Fenwick structure and interval trees. B-trees. Splay trees. Fibonacci heap. Disjoint sets structure.
4. Graph algorithms. Depth and breadth first search. Spanning trees. Shortest path algorithms. Maximum flow algorithms.
5. Selected classical algorithms. String searching. Computational geometry algorithms.
6. Randomized and online algorithms. Motivation and examples of randomized algorithms. Analysis of randomized algorithms. Online algorithms and the notion of competitiveness.

1. Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, MIT Press, 2022.
2. Randomized Algorithms, R. Motwani, P. Raghavan, Cambridge University Press, 1995.
3. Algorithms, R. Sedgewick, Addison-Wesley Professional, 2011.
4. The Algorithm Design Manual, S. S. Skienna, Springer, 2020.
5. Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, J. Hromkovič, Springer-Verlag, 2005.

Mandatory course - Regular study - Computer Science and Mathematics