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.