Text algorithms
General data
Course ID: | 1000-2N09ALT |
Erasmus code / ISCED: |
11.303
|
Course title: | Text algorithms |
Name in Polish: | Algorytmy tekstowe |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
6.00
|
Language: | English |
Type of course: | elective monographs |
Prerequisites: | Algorithms and data structures 1000-213bASD |
Short description: |
The lecture covers basic algorithms on texts (strings), as well as related algorithmic techniques and data structures (suffix trees, subword graphs). The classical problems are string-matching, repetitions, symmetries and compression. Also some problems will be discussed related to computational biology and textual generation of two-dimensional fractals. The course covers also some algorithmics on compressed texts, the complexity status of basic problems can unexpectably change to NP or PSPACE completeness in the compressed setting. A relatively short part of the course is devoted to combinatorics on words. |
Full description: |
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. |
Bibliography: |
1. M. Crochemore, W. Rytter, Text algorithms, the book available free at: http://www.mimuw.edu.pl/~rytter/BOOKS/text-algorithms.pdf |
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 methods and 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. |
Classes in period "Winter semester 2023/24" (past)
Time span: | 2023-10-01 - 2024-01-28 |
Navigate to timetable
MO TU W CW
TH FR CW
WYK
|
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Jakub Radoszewski | |
Group instructors: | Arkadiusz Czarkowski, Tomasz Nowak, Jakub Radoszewski, Wojciech Rytter | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Jakub Radoszewski | |
Group instructors: | Jakub Radoszewski, Wojciech Rytter, Wiktor Zuba | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.