Algorithms and data structures 2 2020/21
Lecturers and Teachers
|Lecturer|| Sergey Shershakov |
|Workshop Instructors|| Piatskii G.
About the course
The training course “Algorithms and Data Structures (part 2)” is offered to students of Bachelor Program “HSE and University of London Double Degree Programme in Data Science and Business Analytics” (area code 01.03.02) at the Faculty of Computer Science of the National Research University — Higher School of Economics (HSE). The course is classified as an compulsory subject (Б.Пр.Б unit / base module,Б.Пр. – Major disciplines of 2020–2021 academic year working сurriculum); it is a two-module course (semester A quartiles 1 and 2). The syllabus is prepared for teachers responsible for the course (closely related disciplines), teaching assistants, students enrolled in the course as well as experts and statutory bodies carrying out assigned or regular accreditations. The course is dedicated to selected advanced algorithms and data structures. It also involves the basics of the automata theory and the complexity theory. The lectures and practical classes are closely inter-related. The lectures are primarily intended to introduce new topics, whereas the practical classes are intended for solving specific problems and implementing them as C++ programs. Successful completion of “Introduction to Programming” and “Algorithms and Data Structures (part 1)” courses is the sole prerequisite for being enrolled in this course.
The course will cover the following topics
1. Introduction to Algorithms-2 and Recap from Algorithms-1.
2. Minimum Spanning Trees (MST). Greedy algorithms finding MST: Prim's algorithm, Kruskal's algorithm.
3. Disjoint-Set Forests.
4. Introduction to Automata. Deterministic Finite Automata. Nondeterministic Finite Automata.
5. Regular Expressions. Implementation in C++ and Python.
6. Decision and Closure Properties of Regular Languages.
7. Context-Free Languages. Properties of Context-Free Languages.
8. Parse Trees. Normal Forms for Context-Free Grammars.
9. Pushdown Automata. Equivalence of CFG's and PDA's.
10. Range Minimum Queries (RMQ).
11. Cartesian Trees and RMQ.
12. Tries and String Matching. Aho-Corasick Automata.
13. Suffix Trees.
14. Suffix Arrays.