SubjectsSubjects(version: 804)
Course, academic year 2017/2018
   Login via CAS
Algorithms and Data Structures I - NTIN060
Czech 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 2017
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: Mgr. Martin Mareš, Ph.D.
doc. RNDr. Ondřej Čepek, Ph.D.
Mgr. Jan Hubička, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: G_I (24.05.2004)

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. Pavel Zakouřil, Ph.D. (11.08.2015)

Syllabus -
Last update: T_KTI (25.04.2016)

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.

Charles University | Information system of Charles University |