Text algorithms 1000-2N09ALT
1. Introduction to Basic properties of texts.
2. Simple combinatorics of periodicities.
3. Advanced serach for exact patterns..
4. Suffix trees.
5. Subword graphs.
6. Repetitions.
7. Symmetries.
8. Compression
9. Two-dimensional texts.
10. Problems of computational biology.
11. Stringology of fractals.
12. Advanced serach for approximate patterns.
13. Word equations.
14. Algorithms on compressed texts.
Type of course
Prerequisites
Course coordinators
Learning outcomes
Student has basic knowledge of basic problems and techniques in algorithmics on teksts, in particular:
1. He can prove correctness and can construct efficient algorithms
2. Knows main combinatorail propertis of words
3. has basic knowledge about basic data structures related to texts
4. knows basic alfgorithms, in particular algoritgms of Knutha-Morris-Pratt, Boyer-Moore and Karkainen Sanders
5. can design fast algorithms related to texts, sequences and trees
Capabitities(K_U07):
The student can understand algorithmic problem in this area and can, by himself, propose effcient algorithmic solution
Potrafi samodzielnie wyspecyfikować problem algorytmiczny z tej dzidziny, dokonać jego analizy i zaproponować wydajne rozwiązanie.
Social skills (K_K01-K_K09):
The student can search for related informations and judge their suitability.
Assessment criteria
The final grade is a result of a written exam. Most active students during the semester will be exempted from the exam.
In the case of completing the course by a doctoral student, the student will read a selected recent research article and a chat with a lecturer about the article will be a part of the exam.
Bibliography
1. M. Crochemore, W. Rytter, Text algorithms, the book available free at: http://www.mimuw.edu.pl/~rytter/BOOKS/text-algorithms.pdf
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: