Algorithms and Data Structures DSBA 2025/2026

About

This page contains basic information for the course Algorithms and Data Structures in 2024/2025 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	241	242	243	244	245	246
Lecturer	Nikita Makarov
Seminar Instructor	Vladimir Kurenkov		Simon Kondakov
Teaching Assistant	tg: @leon1dl	tg: @Mellodizzz	tg: @yksee	tg: @polina_gur	tg: @d_poly	tg: @rina_mlv
Lecturer Assistant	@svbudygin

Grading

You may find your grades.

Formula

Final Grade = M1 * 0.4 + M3 * 0.6

Mi = 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 14:40 till 17:40.

Lecture Materials

Sep 6

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

Bibliography: Cormen, ch. 2, 3, 8

Sep 13

• 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

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

Sep 27

• Red-black trees, basic operations
• Treaps, basic operations

Bibliography: Cormen, ch. 13

Oct 4

• Treaps, how to insert and to remove items using split and merge
• Treaps with implicit keys
• Tries, compact tries, basic operations
• 2-3-4 trees, basic operations: search, insert

Bibliography: Mehta, ch. 28

Oct 11

• Quiz #1
• 2-3-4 trees, basic operations: delete
• B-trees, basic operations

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

Oct 18

• Hash tables, collisions, collision resolution by chaining, open addressing
• PATRICIA trie, basic operations

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

Oct 25

• Exam in module 1

Nov 8

• Exact string matching, naive algorithm, the preprocessing approach, Z-algorithm, the simplest linear-time algorithm
• The Knuth-Morris-Pratt algorithm

Bibliography: Gusfield, ch. 1, 2

Nov 15

• The Boyer-Moore algorithm
• The Aho-Corasick algorithm

Bibliography: Gusfield, ch. 2, 3

Nov 22

• Suffix trees: basic definition, naive algorithm to build
• Suffix trees: Ukkonen's algorithm

Bibliography: Gusfield, ch. 5, 6

Nov 29

• Quiz #2
• Suffix trees applications: generalized suffix tree, the longest common substring for two and more strings
• Suffix arrays: building using suffix tree, exact string matching

Bibliography: Gusfield, ch. 6, 7

Dec 6(preliminarily)

• Suffix arrays: exact string matching
• Dynamic programming

Bibliography: TBD

List of topics for exam in module 1

• 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
• Treaps with implicit keys
• Tries, compact tries, basic operations
• 2-3-4 trees, basic operations
• B-trees, basic operations
• Hash tables, collisions, collision resolution by chaining, open addressing