|
Lecturer(s)
|
-
Babichev Sergii, prof. DSc.
-
Fišer Jiří, Mgr. Ph.D.
-
Maškov Viktor, doc. RNDr. Mgr. DrSc.
-
Škvor Jiří, RNDr. Ph.D.
|
|
Course content
|
1. Theoretical foundations of algorithmization: asymptotic complexity (Landau asymptotic notation), locality principle (implications for caches) 2. Data structures: basic principles, linear data structures, hash tables (hash functions), sparse arrays 3. Data structures: tree structures (binary ordered trees, heaps), tree balancing 4. Data structures: graphs (Fibonacci heaps, weighted graphs) 5. Recursive algorithms: divide and conquer (quick sort, merge sort, closest pair of points) 6. Recursive algorithms: dynamic programming 7. Greedy algorithms: deterministic greedy algorithms (e.g., finding the skeleton of a graph) 8. Greedy algorithms: heuristics (the traveling salesman problem) 9. Probabilistic algorithms: pseudo-random number generators, randomized data structures and classical algorithms, Monte Carlo methods 10. Computational geometry: convex hull, Delaunay triangulation, Voronoi diagram 11. Computational geometry: BSP tree, quadtree/octree and R-tree, Minkowski sum and its applications 12. Cluster analysis: hierarchical clustering, density clustering (DBSCAN), centroid clustering (k means), graph algorithms (cliques) 13. Text processing (suffix trees, string distance, approximate pattern matching)
|
|
Learning activities and teaching methods
|
|
unspecified
|
|
Learning outcomes
|
The lectures focus on the formal description of algorithms and examples of their application in practice. In the course of the exercises, individual algorithms are implemented or their implementation in standard libraries is discussed (comparison of implementation efficiency) and their practical use is suggested.
|
|
Prerequisites
|
basics of procedural programming (loops, procedures), elementary data types (numbers, string, booleans), principles of efficient data representation (hashes, binary trees)
|
|
Assessment methods and criteria
|
unspecified
Credit: seminar work (implementation of a non-trivial data structure or algorithm) Exam: oral, focused on the practical use of algorithms and data structures in Python/R
|
|
Recommended literature
|
|