About

This page contains basic information for the course Algorithms and Data Structures 1 in 2025/2026 academic year at Bachelor’s Programme in Data Science and Business Analytics (DSBA).

The full syllabus can be accessed at this page.

Teachers and assistants

Group	251	252	253	254	255	256	257
Lecturer	Nikita Makarov
Seminar Instructor	Vladimir Kurenkov			Simon Kondakov
Teaching Assistant	tg: @leon1dl	tg: @yksee	tg: @NaviMash	tg: @polina_gur	tg: @d_poIy	tg: @Mellodizzz	tg: @Ignkos
Lecturer Assistant	@ilyamaranin

Grading

You may find your grades.

Formula

Final Grade = E * 0.4 + HW * 0.2 + Q * 0.2 + S * 0.2

E - exam grade: rational number [0, 10] = sum of the grade for the oral and written parts, out of 5 each
HW - homework grade: rational number [0, 10]
Q - lecture quizzes grade: rational number [0, 10]
S - seminar practice grade: rational number [0, 10]

rounding: each element in the formulae is rounded up

Plagiarism policy

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.

Home assignments

Contest	Deadline	Topic

Lectures

Lectures are held on Saturdays from 13:00 till 16:00.

Lecture Materials

Apr 18

Introduction to the course
Asymptotic notation
Sorting algorithms: insertion sort, merge sort, quicksort
Lower bounds of sorting
Counting sort

Bibliography: Cormen, ch. 2, 3, 4, 7, 8

Apr 25

Radix sort
Binary search trees, basic operations (searching, insertion, deletion, rotation), tree traversal (inorder, preorder, postorder)
AVL-trees, main properties, searching, insertion

Bibliography: Cormen, ch. 12, Knuth, vol. 3, ch. 6.2.3

May 16

AVL-trees, main properties, insertion, deletion
Red-black trees, main properties, insertion

Bibliography: Cormen, ch. 13, Knuth, vol. 3, ch. 6.2.3

May 23

Red-black trees, deletion
Tries, main properties, basic operations, compact tries, PATRICIA trie

Bibliography: Cormen, ch. 13, Mehta, ch. 28

May 30

Quiz #1 (sorting, trees)
PATRICIA trie, deletion

Bibliography: Mehta, ch. 28

Jun 6

B-trees, main properties, basic operations, 2-3-4 trees
Treaps, basic operations, split and merge operations

Bibliography: Cormen, ch. 18, Seidel, Aragon, "Randomized Search Trees"

Jun 13

Treap with implicit keys
Segment tree
Fenwick tree
Hash tables, collisions, collision resolution by chaining

Bibliography: Aragon, "Randomized Search Trees", Mehta, ch. 11, 18, Cormen, ch. 11

List of topics for exam in module 4

Asymptotic notation
Lower bounds of sorting using comparisons
Sorting algorithms: insertion sort, merge sort, heap sort, counting sort, radix sort
Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
Binary search trees, basic operations (insert, delete, rotate, find min/max)
AVL-trees, basic operations
Red-black trees, basic operations
Treaps, basic operations
Treap with implicit keys
Tries, compact tries, basic operations
2-3-4 trees, basic operations
B-trees, basic operations
Segment tree, basic operations
Hash tables, collisions, collision resolution by chaining