Algorithms and data structures

Course guarantor:

Tomáš Valla

Lecturer:

Tomáš Valla

Tutor:

Jiřina Scholtzová, Tomáš Valla

Supervisor:

Department of Theoretical Computer Science

Synopsis:

The course covers the most basic of the efficient algorithms, data structures and graph theory that every computer scientist should know. As part of the exercise, students are introduced to the use of explained algorithms for solving practical problems. Furthermore, students gain basic knowledge of the design and use of finite automata, regular expressions, the use of context-free grammars and the design and use of stack automata. They are introduced to the Turing machine and to the complexity classes P and NP.

Requirements:

Syllabus of lectures:

1.Basic mathematical concepts sets, relations, graph, sequence, tree.

2.Time and memory complexity of algorithms. Examples of linear, polynomial and exponential complexity.

3.Basic abstract data types queue, stack, table, tree, search trees and their balancing.

4.Recursive algorithms and divide-and-conquer method.

5.Sort algorithms.

6.Randomized algorithms and passwords.

7.Dynamic programming.

8.Minimum chart skeletons.

9.Shortest paths in graphs.

10.Automata as calculation models: Formal language, Finite automaton and minimal deterministic finite automaton.

11.Regular expressions, basic properties of regular formal languages.

12.Stack automaton and basic properties of context-free languages.

13.Turing machine, recursive-countable and recursive languages. Classes P and NP.

Syllabus of tutorials:

The exercises follow the topics of the lectures.

Study Objective:

To acquaint students with basic and more advanced algorithms and data structures. The student will also get the basics of graph theory and the most important graph algorithms. The goal is not only to understand the algorithms taught, but also to be able to apply them in problem solving and to be able to modify them for similar tasks.

Study materials:

Mandatory:

Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, 2022.

Recommended:

Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2022.

Michael Sipser: Introduction to the Theory of Computation, MIT Přess, 2006.

John Hopcroft, Rajeev Motwani, Jeffrey Ullman: Introduction to Automata Theory, Languages, 2019.

Note:

nutno doplnit

Further information:

nutno doplnit

Time-table for winter semester 2025/2026:

Time-table is not available yet

Time-table for summer semester 2025/2026:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomTH:A-1242 Valla T. 12:45–14:15 (lecture parallel1) Thákurova 7 (budova FSv) roomTH:A-1242 Scholtzová J. Valla T. 14:30–16:00 (lecture parallel1 parallel nr.101) Thákurova 7 (budova FSv)
Wed
Thu
Fri

The course is a part of the following study plans:

• Teaching Informatics for Secondary Schools (compulsory course in the program)