Algorithms and Data Structures DSBA 2023/24

About

This page contains basic information for the course Algorithms and Data Structures in 2023/2024 academic year at Bachelor’s Programme 'HSE and University of London Double Degree Programme in Data Science and Business Analytics' (DSBA).

Professors and assistants

The lecturer of the course is Nikita Makarov.

Group	221	222	223	224
Teacher	Andrey Borevskiy	Julio Carrasquel	Vladimir Kurenkov	Vladimir Kurenkov
Assistant	Artem Makarenkov	Anastasiya Romanova	Aleksandr Petelin	Aleksandr Petelin

Lectures

Lectures are held on Saturdays from 14:40 till 17:40.

Passed and planned lectures

9.09

• Introduction to the course
• Asymptotic notation
• Sorting algorithms: insertion sort, heap sort (including building a heap), merge sort
• Lower bounds of sorting
• Counting sort

Bibliography: Cormen, ch. 2, 3, 6, 8

16.09

• Radix sort
• Trees, main properties
• Binary search trees, main operations: searching, inserting, removing
• Balanced BST, AVL-tree

Bibliography: Cormen, ch. 8, 12, 13

23.09

• Red-black tree
• Treaps

Bibliography: Cormen, ch. 13

30.09

• Tries, compact tries
• PATRICIA trie, searching and inserting
• B-tree

Bibliography: Cormen, ch. 18; Mehta, Sahni, ch. 28

7.10

• Recap for previous topics
• Lecture quiz #1

13.10

• Hash tables
• String matching problem
• Z-algorithm
• Knuth-Morris-Pratt algorithm

Bibliography: Cormen, ch. 11; Gusfield, ch. 1, 2

20.10

• Knuth-Morris-Pratt algorithm
• Boyer-Moore algorithm
• Aho-Corasick algorithm

Bibliography: Gusfield, ch. 2, 3

List of topics for exam in module 1

• Asymptotic notation
• Sorting algorithms: insertion sort, heap sort, merge sort, counting sort, radix sort
• Binary search trees: properties, main operations
• Balanced BST: red-black trees, AVL-trees, treaps
• Tries, compact tries
• B-trees
• Hashing
• String matching problem
• Z-algorithm
• Knuth-Morris-Pratt algorithm
• Boyer-Moore algorithm
• Aho-Corasick algorithm

Grading

Exams are conducted at the end of module 1 and module 4. Both of them has two parts: oral and written.

Final Grade = Module 1 Grade * 0.3 + Module 4 Grade * 0.7

Module X Grade = Exam Grade * 0.4 + Homework Grade * 0.2 + Lectures Quizzes * 0.2 + Seminar Practice * 0.2

Exam Grade = Oral Part Grade + Written Part Grade

Exam Grade, Homework Grade, Lectures Quizzes and Seminar Practice are rational numbers between 0 and 10. Oral Part Grade and Written Part Grade are integer numbers between 0 and 5.

All fractional parts are rounded up in the final estimate.

If plagiarism is detected, the assessment element will be assigned a score of "0".

If the student is suspected of preparing the task not on his own, the teacher has the right to initiate additional verification or defense of this particular assessment element. Then such an assessment element will be graded based on the additional verification or the defense.

On the first retake the cumulative course grade is taken into consideration. On the second retake there are following rules: - If the cumulative grade + 2nd retake grade >= 4, then the student receives the sum of these marks, multiplied by their coefficients. - If the cumulative grade + 2nd retake grade < 4, but the 2nd retake grade > 7, then the student is given a 4. - If the 2nd retake grade is <7 and the cumulative grade is <4, the student receives a failing grade.