Algorithms and Data Structures 2 faculty subject.

In course Algorithms and Data Structures 2 student learns about the basic tools for the analysis of algorithms complexity and problem complexity.

Basic mathematical tools
order functions O, Ω, Θ and differences between them;
what is the complexity of a problem and what is the
complexity of a solution;
probability and randomization;
models of computation;
basic analysis of data structures and algorithms.
Radix trees (trie)
basic implementation,
path and level compression.
Disjoint sets and amortization.
Dictionary
deterministic solutions,
probabilistic solutions.
Priority queue
basic abstract data structure (heap),
extended abstract data structure (binomial and
Fibonacci heap, vEB).
Sorting
problem complexity,
method of exhaustive search,
method of divide and conquer
method of use of existing data structures,
sorting in linear time,
sorting in parallel.
Rank and select
dynamic data structure (extended trees),
static data structure (median).
Method of dynamic programming. Algorithms of graphs and networks
topological sorting,
greedy method: minimum spanning tree,
relaxation method: shortest paths,
maximum network flow,
parallel algorithms and Internet.
Selected algorithms
optimization problems: use of Bloom's filter, method
branch and bound;
mathematical algorithms and cryptography: matrix
multiplication, solving system of equations, FFT,
maximum common divisor, modular arithmetic,
exponents;
algorithms on strings and bioinformatics: pattern
search.
With all problems we will also take a brief look at
parallel solutions.

Student gets familiar with basic methods for analysis and design of data structures and algorithms, and learns how to evaluate their quality.
General competencies: abstract and analytical thinking, capability to define and formalize the problem, literature study and approach to a seminar work. Specific competencies: modularization, encapsulation and abstraction; basics of engineering knowledge in a sense of integration of existing solutions, evaluation of quality of a solution, differentiation between the problem and solution (one of), knowledge of applying an algorithmic approach – how to develop an algorithm to solve a problem.

Student learns basic terms in data structures and algorithms design. (S)he learns how to analyze problems and then combine solutions into a general solution, and evaluate their quality.