Algorithms and Data Structures 1 - NTIN060
Title: Algoritmy a datové struktury 1
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
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
Guarantor: prof. RNDr. Ondřej Čepek, Ph.D.
Mgr. Martin Mareš, Ph.D.
doc. Mgr. Jan Hubička, Ph.D.
Teacher(s): Sudatta Bhattacharya, M.Sc.
prof. RNDr. Ondřej Čepek, Ph.D.
Mgr. Tomáš Domes
Mgr. Jelena Glišić
RNDr. Jan Hric
Bc. Vojtěch Káně
Mgr. Kate Konczycki
RNDr. Petr Kučera, Ph.D.
Mgr. Vladan Majerech, Dr.
Mgr. Martin Mareš, Ph.D.
RNDr. Jiří Švancara, Ph.D.
Bc. Tomáš Turek
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Is co-requisite for: NPFL145
Opinion survey results   Examination dates   SS schedule   Noticeboard   
Annotation -
Introductory lecture on the basic types of algorithms and data structures necessary for their implementation. It follows the lecture NPRG062 Algorithmization in the previous semester.
Last update: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)
Aim of the course - Czech

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

Last update: T_KTI (23.05.2008)
Course completion requirements -

It is necessary to get course credit and pass the examination (in arbitrary order).

For credit you need to get 100 points out of at least 150 possible continuously awarded for homework, tests, and other activities.

The ongoing nature of the inspection does not imply a right to request corrective tests nor alternative homework assignments.

In justified cases (long-term illness, stay abroad, etc.) the lecturer may set individual conditions for credit granting.

The examination can be written, oral, or combined. It can take presence or distance form. The form of the exam is determined by the teacher.

Last update: Mareš Martin, Mgr., Ph.D. (06.02.2023)
Literature - Czech
  • 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, http://pruvodce.ucw.cz/
  • Videozáznamy přednášek
Last update: Hric Jan, RNDr. (03.10.2017)
Requirements to the exam -

It is necessary to understand the theory presented at the lectures and to be able to apply it to solving of algorithmic problems.

Last update: Mareš Martin, Mgr., Ph.D. (02.03.2018)
Syllabus -

Optional topics in square brackets, the rest is mandatory.

1. Means for describing the complexity of algorithms and operations with data structures

  • measurement of data size, number of algorithm steps as a function of data size
  • RAM computational model
  • asymptotic notation

2. Tree data structures

  • binary search trees
  • AVL trees
  • (a,b)-trees
  • [red-black trees]

3. Hashing

  • a description of simple collision resolution strategies
  • analysis of the average time complexity of the search
  • universal hashing

4. Sorting

  • average case analysis for Quicksort, Randomized Quicksort
  • lower bound on the complexity of comparison sorting algorithms (decision trees)

5. Basic graph algorithms

  • depth-first search on an undirected graph, detection of bridges and articulations
  • depth-first search on a directed graph, transitive closure, topological numbering
  • [detection of components of strong connectivity in linear time]

6. Extreme paths in graphs

  • extreme paths in a directed acyclic graph, the critical path method
  • Dijkstra's algorithm (refresher of binary heaps, comparison of implementation using an array and a binary heap)
  • Bellman-Ford's algorithm (looking for negative cycles)
  • [Floyd-Warshall's algorithm]

7. Minimum spanning tree

  • Jarník's and Borůvka's algorithm
  • [Kruskal's algorithm and data structure for Union-Find]

8. Divide and conquer method

  • general schema of divide and conquer algorithms, describing their complexity by recurrent equations
  • substitution method for recurrent equations and "master theorem (cook-book)"
  • simple applications: binary search, Merge sort, multiplication of numbers (Karatsuba-Ofman)
  • more complex applications: Strassen's multiplication of matrices, [median search in linear time in the worst case]

9. Dynamic programming

  • general principle of dynamic programming
  • edit-distance of strings
  • [optimal search trees]

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