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: @NaviMash
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 (sorting, trees)
• 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 (string matching)
• 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

• Suffix arrays: exact string matching
• Dynamic programming, two conveyors problem

Bibliography: Gusfield, ch. 7, Cormen, ch. 15

Dec 13

• Dynamic programming: two conveyors problem, matrix-chain multiplication, the longest common subsequence, the Levenstein distance
• Greedy algoirthms: an activity-selection problem, Huffman codes

Bibliography: Cormen, ch. 15, 16

Jan 10

• Greedy algoirthms: the longest increasing subsequence, LCS-problem with greedy approach
• Greedy algorithms: Huffman codes, correctness of Huffman's algorithm

Bibliography: Cormen, ch. 16

Jan 17

• Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
• Dictionary models: LZ-77, LZ-78, LZW
• Static and semistatic Huffman codes, tree serialization

Bibliography: Witten, ch. 1, 2, Atallah, ch. 12

Jan 24

• Adaptive Huffman codes
• Arithmetic coding
• RLE

Bibliography: Atallah, ch. 12, Witten, ch. 2

Jan 31

• Quiz #3 (dynamic programming, greedy algorithms)
• RLE implementation
• Burrows-Wheeler transform
• Move to front

Bibliography: Witten, ch. 2

Feb 7

• Graphs, main definitions, representation of graphs
• Breadth-first search, single-source shortest paths in non-weighted graph
• Depth-first search, topological sort, strongly connected components
• Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm

Bibliography: Cormen, ch. 22, 24

Feb 14

• Single-source shortest paths, Dijkstra's algorithm
• All-pairs shortest paths, "matrix multiplication", Floyd-Warshall algorithm, Johnson's algorithm
• Maximum flow, main definitions

Bibliography: Cormen, ch. 24, 25, 26

Feb 21

• Maximum flow, Ford-Fulkerson method, Edmonds-Karp algorithm
• Push-relabel algorithm
• Maximum bipartite matching, Ford-Fulkerson method, Kuhn's algorithm

Bibliography: Cormen, ch. 26

Mar 7

• Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
• Disjoint sets: linked list representation, disjoint-set forest
• Polynomials, coefficient representation, point-value representation, main operations
• Discrete Fourier transform
• Fast Fourier transform

Bibliography: Cormen, ch. 21, 23, 30

Mar 14

• Quiz #4 (graphs)
• Deterministic finite automata
• Nondeterministic finite automata
• Equivalence of DFA and NFA

Bibliography: Hopcroft, ch. 2

Mar 21

• Finite automata with epsilon-transitions
• Regular expressions
• Converting RE to NFA with epsilon-transitions
• Converting DFA's to RE
• Context-free languages
• Context-free grammar, derivations using a grammar, leftmost and rightmost derivations
• Parse trees

Bibliography: Hopcroft, ch. 3, 4, 5

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

List of topics for exam in module 3

• Exact string matching, naive algorithm, the preprocessing approach, Z-algorithm, the simplest linear-time algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, Aho-Corasick algorithm
• Suffix trees: basic definition, naive algorithm to build, Ukkonen's algorithm
• Suffix trees applications: generalized suffix tree, the longest common substring for two and more strings
• Suffix arrays: building using suffix tree, exact string matching
• Dynamic programming, two conveyors problem, knapsack problem, matrix-chain multiplication, the longest common subsequence, the Levenstein distance
• Greedy algoirthms: an activity-selection problem, Huffman codes, the longest increasing subsequence, LCS-problem with greedy approach, knapsack problem
• Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
• Symbolwise models: static and semistatic Huffman codes, tree serialization, adaptive Huffman codes, arithmetic coding
• Dictionary models: LZ-77, LZ-78, LZW
• Text modifications: RLE, Burrows-Wheeler transform, Move-to-front
• Graphs: main definitions, representation of graphs, breadth-first search, single-source shortest paths in non-weighted graph, depth-first search, topological sort, strongly connected components
• Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
• Disjoint sets: linked list representation, disjoint-set forest
• Single-source shortest paths: Bellman-Ford algorithm, Dijkstra's algorithm
• All-pairs shortest paths: "matrix multiplication", Floyd-Warshall algorithm, Johnson's algorithm
• Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm, push-relabel algorithm
• Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
• Polynomials: coefficient representation, point-value representation, discrete Fourier transform, fast Fourier transform
• Regular languages: deterministic finite automata, nondeterministic finite automata, equivalence of DFA and NFA, finite automata with epsilon-transitions, regular expressions, converting RE to NFA with epsilon-transitions, converting DFA's to RE