Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Algorithms and Data Structures I - NTIN060

Title:	Algoritmy a datové struktury I
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
Semester:	summer
E-Credits:	5
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	Mgr. Martin Mareš, Ph.D. prof. RNDr. Ondřej Čepek, Ph.D.
Class:	Informatika Bc.
Classification:	Informatics > Theoretical Computer Science

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

A course about basic types of algorithms and data structures needed for their implementation.

Aim of the course - Czech

Last update: T_KTI (23.05.2008)

Naučit základní datové struktury, algoritmy a metody teoretické informatiky

Literature - Czech

Last update: RNDr. Jan Hric (03.10.2017)

Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001
Videozáznamy přednášek

Syllabus -

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

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.