Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Stringology

Login to KOS for course enrollment Display time-table
Code Completion Credits Range
PI-STR ZK 4 3C
Course guarantor:
Jan Holub
Lecturer:
Jan Holub
Tutor:
Jan Holub
Supervisor:
Department of Theoretical Computer Science
Synopsis:

Algorithms for processing and searching in text.

Algorithms presented on the basis of finite automata as models of computation.

Principles of processing compressed text and parallel algorithms

Requirements:
Syllabus of lectures:

1. General principles of processing and searching in text.

2. Finite automata as a basic model of computation for text algorithms.

3. Finite automata as indexing tools.

4. Searching regularities in text (repetitions, periods, borders,.).

5. Methods based on simulation of finite automata.

6. Pattern matching in compressed text.

7. Parallel methods in stringology.

8. Searching for the longest common factor and subsequence in a set of strings.

9. String cover, superstring construction.

10. Use of text algorithms for more complex data structures (trees, matrices,.)

Syllabus of tutorials:
Study Objective:

The goal of the module is to present methods of construction of string processing algorithms. The construction is based on theory of finite automata. There are hundreds of tasks that are classified into many classes. For each class of tasks, a construction of appropriate algorithms is presented.

Study materials:

1. Crochemore, M., Rytter, W.: Jewels of stringology. World Scientific Publishing, 2003.

2. Melichar, B., Holub, J. Polcar, T.: Text searching algorithms. Available on: http://www.stringology.org/athens/, 2005.

Note:
Time-table for winter semester 2024/2025:
Time-table is not available yet
Time-table for summer semester 2024/2025:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-12-11
For updated information see http://bilakniha.cvut.cz/en/predmet1602106.html