Algorithms and data structures

Course guarantor:

Lecturer:

Tutor:

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:

Further information:

nutno doplnit

No time-table has been prepared for this course

The course is a part of the following study plans: