|
|
|
||
|
A course about basic types of algorithms and data structures needed for their implementation.
|
|
||
|
Naučit základní datové struktury, algoritmy a metody teoretické informatiky |
|
||
|
It is necessary to get course credit and pass the examination (in arbitrary order). Credit is given for solving homeworks, including potential additional homeworks at the end of the semester. The nature of this requirement excludes the possibility of repeated attempts to get credit, which means that if you do not obtain enough points for homeworks, there is no other way how to get credit.
The examination consists of a written and oral part. The written part precedes the oral part, a failure in the written part implies failing the whole exam, so the oral part is skipped in such cases. |
|
||
|
|
||
|
It is necessary to understand the theory presented at the lectures and to be able to apply it to solving of algorithmic problems. |
|
||
|
Asymptotic notation. Tree structures, binary search trees, AVL trees, Red-black trees. Hashing, solving of collisions, analysis of average case. Sorting. Analysis of average case for quicksort, randomization. Lower bound for sorting (decision trees), linear-time sorting based on indexing by keys. Graph algorithms, depth-first search, breadth-first search, strongly connected components, transitive closure, topological sorting. Extreme paths in graphs. Method of critical path - PERT. Dijkstra alg., Bellman-Ford alg. (searching of negative cycles), Floyd-Warshall alg. for all paths. Minimal spanning tree. Kruskal alg., Prim-Jarnik alg. Method Divide and conquer. General schema, solving of recurrent equations. Master theorem. Applications: binary searching, mergesort, Strassen alg. Eucleid alg., LUP decomposition.
|