University of Warsaw - Central Authentication System

Text algorithms

General data

Course ID:	1000-2N09ALT
Erasmus code / ISCED:	11.303 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
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 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
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	Selected timetable range: weekly course term Navigate to timetable MO TU W CW TH FR CW WYK
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
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	Selected timetable range: weekly course term Navigate to timetable
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Jakub Radoszewski
Group instructors:	Jakub Radoszewski, Wojciech Rytter, Wiktor Zuba
Students list:	(inaccessible to you)
Examination:	Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.