SubjectsSubjects(version: 821)
Course, academic year 2017/2018
   Login via CAS
Algorithms and Data Structures I - NTIN060
English 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 to 2018
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: 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
  • M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5,
  • 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.

Charles University | Information system of Charles University |