Objectives and outcomes
Students acquire knowledge of the design and analysis of algorithms. They are able to solve algorithmic
problems. They know how to use basic and more complex data structures and algorithms. They
understand the problems of proving algorithm correctness and mathematical tools for showing
them. Moreover, students know algorithmic paradigms and recognize the classes of problems they solve.
They understand the running time of algorithms and know the ways to determine them.
Lectures
Algorithm analysis. Examples of proving algorithm correctness. Asymptotic analysis of the worst and / or
average case. Asymptotic notations Big O, o, Theta, Big Omega, omega. Time (computational) and
space complexity. Calculation of finite sums, recurrent relations, master theorem. Dynamic programming.
Brute force algorithms. Greedy algorithms. A recursive strategy based on division (divide-and-conquer).
Backtracking, branch-and-bound, heuristics. Searching for a pattern in the text (pattern matching). Flow
networks and determination of the maximum flow in the network. Matching in graphs. Examples of
numerical algorithms. Recursion implementation. Reduction of tail recursion to iteration.
Practical classes
Implementation of one of the algorithms presented in lectures. Design and analysis of algorithms for
various algorithmic problems. Special emphasis on recognising the algorithmic paradigm (dynamic
programming, greedy algorithms, divide and conquer, backtrack, etc.) that can be used for solving
algorithmic problems. Development (if possible) of different algorithms for solving one and the same
algorithmic problem, with a comparison of complexity (computational and space).