Algorithms and Data Structures 2
- Students will continue to study algorithm design principles.
- Students will elaborate important concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.
- Students will study design principles of selected advanced data structures.
- Students will practice efficiently implementing algorithms and data structures as C++ applications.
- Students will concern selected algorithms on strings.
- Students will concern selected graph algorithms.
- Students will study basic concepts on theory of automata.
- Introduction to Algorithms-2 and Recap from Algorithms-1.
- Minimum Spanning Trees (MST). Greedy algorithms finding MST: Prim's algorithm, Kruskal's algorithm.
- Disjoint-Set Forests.
- Introduction to Automata. Deterministic Finite Automata. Nondeterministic Finite Automata.
- Regular Expressions. Implementation in C++ and Python.
- Decision and Closure Properties of Regular Languages.
- Context-Free Languages. Properties of Context-Free Languages.
- Parse Trees. Normal Forms for Context-Free Grammars.
- Pushdown Automata. Equivalence of CFG's and PDA's.
- Range Minimum Queries (RMQ).
- Cartesian Trees and RMQ.
- Tries and String Matching. Aho-Corasick Automata.
- Suffix Trees.
- Suffix Arrays.
- HomeworkStudents’ skills in programming are tested using automated testing. This way, a student is assigned an individual task, prepares it by using a personal computer and, then, submits it by using a special service, such as Yandex.Contest or a repository-based tool. The specific solution is subject to further clarification.
- In-Class tasksStudents’ skills in programming are tested using automated testing. This way, a student is assigned an individual task, prepares it by using a personal computer and, then, submits it by using a special service, such as Yandex.Contest or a repository-based tool. The specific solution is subject to further clarification.
- Bonus Points
- Ongoing Assessment PrevThe ongoing assessment grade is accumulated throughout all the classes and is related to a participant’s activity.
- Final ExamЭкзамен письменный. Прокторинг не требуется. Экзамен будет проходить в Zoom, в формате микро-квизов с ограниченим по времени + компьютерная программа
- Ongoing Assessment
- Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613
- Michael Sipser. (2005). Introduction to the Theory of Computation, Second Edition.
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2014). Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition: Vol. 3rd ed. Pearson.