Algorithms and Data Structures 1 - NTIN060

• Title: Algoritmy a datové struktury 1
• Form of teaching: lecture+practicals
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2025
• Duration in semesters: 1
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Maximum number of enrolled students: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Repeated enrollment: 2 / 2 / 2 / 2
• Guarantor: prof. RNDr. Ondřej Čepek, Ph.D.; Mgr. Martin Mareš, Ph.D.; doc. Mgr. Jan Hubička, Ph.D.
• Class: Informatika Bc.
• Classification: Informatics > Theoretical Computer Science
• Is co-requisite for: NPFL145

Annotation

English

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)

Czech

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci. Navazuje na výklad v přednášce NPRG062 Algoritmizace v předchozím semestru.

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

Aim of the course

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

Last update: T_KTI (23.05.2008)

Course completion requirements

English

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

For the course credit you need to get 100 points out of at least 150 possible points awarded for homework, tests, and other activities. The distribution of these points is always set up in a way that points awarded for at least two written or electronically submitted outputs (e.g. 2 homework assignments, or 1 homework assignment and 1 test, or 2 tests) are not necessary to reach the 100 point limit.

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. The form of the exam is determined by the teacher.

Last update: Čepek Ondřej, prof. RNDr., Ph.D. (31.08.2026)

Czech

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí).

Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za řešení domácích úloh, písemné testy a další aktivity. Rozdělení bodů je vždy nastaveno tak, aby body za alespoň dva písemné nebo elektronicky odevzdané výstupy (např. za 2 domácí úkoly, nebo za 1 domácí úkol a za 1 test, nebo za 2 testy) nebyly potřeba k dosažení hranice 100 bodů.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.

Zkouška může být písemná, ústní nebo kombinovaná. Formu zkoušky určuje vyučující.

Last update: Čepek Ondřej, prof. RNDr., Ph.D. (31.08.2026)

Literature

• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms (4th Edition), Sathya Publishers 2023
• M. Mareš, T. Valla: Průvodce labyrintem algoritmů (2. vydání), CZ.NIC Praha 2022, https://pruvodce.ucw.cz/
• S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorithms, McGraw-Hill Education 2006
• J. Erickson: Algorithms, 2023, https://jeffe.cs.illinois.edu/teaching/algorithms/
• Videozáznamy přednášek

Last update: Maxová Jana, RNDr., Ph.D. (17.05.2025)

Course assessment methods and requirements for successful completion, grading scheme

English

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)

Czech

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

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

Syllabus

English

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. 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]

3. 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]

4. Minimum spanning tree

• Jarník's and Borůvka's algorithm

• [Kruskal's algorithm and data structure for Union-Find]

5. Tree data structures

• binary search trees

• AVL trees

• (a,b)-trees

• [red-black trees]

6. 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]

7. Sorting

• average case analysis for Quicksort, Randomized Quicksort

• lower bound on the complexity of comparison sorting algorithms (decision trees)

• sorting in linear time, Counting-Sort, [Radix-sort]

8. Hashing

• a description of simple collision resolution strategies

• analysis of the average time complexity of the search

• universal hashing

9. Dynamic programming

• general principle of dynamic programming

• edit-distance of strings

• [optimal search trees]

Last update: Čepek Ondřej, prof. RNDr., Ph.D. (12.02.2026)

Czech

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami

• měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat

• [výpočetní model RAM]

• asymptotická notace

2. Základní grafové algoritmy

• prohledávání do hloubky na neorientovaném grafu, detekce mostů a artikulací

• prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování

• [detekce komponent silné souvislosti v lineárním čase]

3. Extremální cesty v grafech

• extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty

• Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou)

• Bellmanův-Fordův algoritmus (hledání záporných cyklů)

• [Floydův-Warshallův algoritmus]

4. Minimální kostra grafu

• Jarníkův a Borůvkův algoritmus

• [Kruskalův algoritmus a datová struktura pro Union-Find]

5. Stromové datové struktury

• binární vyhledávací stromy

• AVL stromy

• (a,b)-stromy

• [červeno-černé stromy]

6. Metoda rozděl a panuj

• obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi

• substituční metoda řešení rekurentních rovnic a „master theorem (kuchařka)“

• jednoduché aplikace: binární vyhledávání, Merge sort, [násobení čísel (Karatsuba-Ofman)]

• složitější aplikace: Strassenovo násobení matic, [hledání mediánu v lin. čase v nejhorším případě]

7. Třídění

• analýza průměrného případu pro Quicksort, randomizovaný Quicksort

• dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)

• třídění v lineárním čase, Counting-sort, [Radix-sort]

8. Hešování

• popis jednoduchých strategií řešení kolizí

• analýza průměrné časové složitosti vyhledávání

• univerzální hešování

9. Dynamické programování

• obecný princip dynamického programování

• editační vzdálenost řetězců

• [optimální vyhledávací stromy]

Last update: Čepek Ondřej, prof. RNDr., Ph.D. (12.02.2026)