Просмотр кода страницы 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 [https://www.hse.ru/ba/data/courses/1071074261.html this page]. 

= Teachers and assistants = 

{| class="wikitable" style="text-align:center"
|-
! Group !! 241 !! 242 !! 243 !! 244 !! 245 !! 246
|-
| Lecturer
| colspan="6" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
| colspan="4" | [https://t.me/seemur Simon Kondakov]
|-
| Teaching Assistant
| tg: [https://t.me/leon1dl @leon1dl]
| tg: [https://t.me/Mellodizzz @Mellodizzz]
| tg: [https://t.me/yksee @yksee]
| tg: [https://t.me/polina_gur @polina_gur]
| tg: [https://t.me/d_poly @d_poly]
| tg: [https://t.me/NaviMash @NaviMash]
|-
| Lecturer Assistant
| colspan="6" | [https://t.me/svbudygin @svbudygin]
|}

= Grading =

You may find [https://docs.google.com/spreadsheets/d/1Qh4uXaAZy-nX-dYlA_CtAo4zoWhvwC1ekL4p5-8As0A/edit?gid=1121952238#gid=1121952238 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 =

{| class="wikitable" style="text-align:center"
|-
! 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