• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Бакалаврская программа «Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных"»

05
Декабрь

Algorithms and Data Structures 2

2020/2021
Учебный год
ENG
Обучение ведется на английском языке
4
Кредиты
Статус:
Курс обязательный
Когда читается:
2-й курс, 1, 2 модуль

Преподаватель

Course Syllabus

Abstract

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.
Learning Objectives

Learning Objectives

  • 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.
Expected Learning Outcomes

Expected Learning Outcomes

  • Refreshing the knowledge about the topics of ADS-1.
Course Contents

Course Contents

  • 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.
Assessment Elements

Assessment Elements

  • non-blocking Homework
    Students’ 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.
  • non-blocking In-Class tasks
    Students’ 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.
  • non-blocking Bonus Points
  • non-blocking Ongoing Assessment Prev
    The ongoing assessment grade is accumulated throughout all the classes and is related to a participant’s activity.
  • non-blocking Final Exam
    Экзамен письменный. Прокторинг не требуется. Экзамен будет проходить в Zoom, в формате микро-квизов с ограниченим по времени + компьютерная программа
  • non-blocking Ongoing Assessment
Interim Assessment

Interim Assessment

  • Interim assessment (2 module)
    0.4 * Final Exam + 0.6 * Ongoing Assessment
Bibliography

Bibliography

Recommended Core Bibliography

  • 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.

Recommended Additional Bibliography

  • Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2014). Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition: Vol. 3rd ed. Pearson.