Кто читает:: Департамент больших данных и информационного поиска

Статус:: Курс обязательный

Когда читается:: 1-й курс, 3, 4 модуль

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

Пяцкий Георгий Геннадьевич

Рудаков Кирилл Александрович

Шершаков Сергей Андреевич

Full Syllabus

Abstract

The training course “Algorithms and Data Structures” 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 2019–2020 academic year working сurriculum); it is a two-module course (semester B quartiles 3 and 4). 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 the basics of design and analysis of algorithms. It also involves learning fundamental data structures implemented by the C++ Standard Library (STL). 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 by coding programs in C++. Successful completion of “Introduction to Programming” course is the sole prerequisite for being enrolled in this course.

Learning Objectives

Students will study algorithm design principles.
Students will learn how to analyze the complexity of an algorithm in terms of time and space.
Students will study design principles of basic data structures.
Students will practice implementing algorithms and data structures as C++ applications.

Expected Learning Outcomes

Students will learn basic concepts and methods of designing algorithms.
Students will acquire skills in designing data structures by using C++.
Students will learn approaches to analysis of algorithms complexity in terms of time and space.
Students will improve team-working skills by using collaborative working tools.
Students will improve presentation skills.
Students will improve self- and peer-review skills.
Students will improve skills in writing reports and technical documentation, including rapidly changing documentation using wiki and other specific tools.

Course Contents

MergeSort, Recurrences, and Asymptotics.
Solving recurrences and the master theorem.
Recurrence relations (substitution method, recursion trees). The Selection problem.
Heaps.
Quicksort, Probability and Randomized Algorithms.
Sorting Lower Bounds, BucketSort, RadixSort.
Trees, Binary Search Trees, AVL Trees, Red-Black Trees, Treaps
Hashing.
More on Graphs. Topological Sort.
Strongly connected components, Dijkstra’s algorithm.
Dynamic Programming and shortest paths: Bellman-Ford and Floyd-Warshall.
Examples of dynamic programming: Longest common subsequence, Knapsack, Independent Set.
Greedy algorithms, activity selection problem.
Minimum spanning tree: Boruvka, Kruskal, Prim.
Minimum Cut: Karger’s Algorithm.
Max Flow and the Ford-Fulkerson Algorithm.

Assessment Elements

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

Interim Assessment

Interim assessment (4 module)
0.4 * Final Exam + 0.6 * Ongoing Assessment

Bibliography

Recommended Core Bibliography

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.

Recommended Additional Bibliography

Davis, S. R. (2014). C++ For Dummies (Vol. 7th ed). Hoboken: For Dummies. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=784132
Gregoire, M. (2018). Professional C++ (Vol. Fourth edition). Indianapolis, IN: Wrox. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1729638

Бакалаврская программа «Прикладной анализ данных»

Контакты

Algorithms and Data Structures