Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

String Algorithms - NTIN087

Title:	Textové algoritmy
Guaranteed by:	Department of Software and Computer Science Education (32-KSVI)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2015
Semester:	winter
E-Credits:	3
Hours per week, examination:	winter s.:2/0, 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
Additional information:	http://ksvi.mff.cuni.cz/~dvorak/vyuka/NTIN087/

Guarantor:	doc. RNDr. Tomáš Dvořák, CSc.
Teacher(s):	doc. RNDr. Tomáš Dvořák, CSc.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

A survey of algorithms and data structures for efficient computation of patterns in strings with applications.

Last update: T_KSVI (23.05.2006)

Course completion requirements -

The course is concluded with an oral exam. Questions posed in the exam explore the topics included in the syllabus to the extent that these topics are covered in lectures.

Last update: Dvořák Tomáš, doc. RNDr., CSc. (13.10.2017)

Literature -

M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2014.

M. Crochemore, T. Lecroq, W. Rytter,  125 Problems in Text Algorithms,  Cambridge University Press, 2021.

G. Navarro, M. Raffinot, Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences, Cambridge University Press, 2007.

W. Smyth, Computing Patterns in Strings, Addison Wesley, 2003.

Last update: Dvořák Tomáš, doc. RNDr., CSc. (03.10.2022)

Syllabus -

Introduction to string algorithms

Data structures: suffix tree and its variants, suffix array, suffix automata

Exact and approximate pattern matching

String distance and the longest common subsequence

Regular expression matching

Applications in bioinformatics and data compression

Last update: Dvořák Tomáš, doc. RNDr., CSc. (13.10.2017)

Entry requirements - Czech

Knowledge at the level of the subjects Algorithms and Data Structures I and II, Automata and Grammars.

Last update: T_KSVI (04.05.2015)