Wiki - Факультет компьютерных наук - Вклад [ru]

Algorithms and Data Structures DSBA 2026/2027

2026-09-19T15:56:26Z

Nkmakarov:

= About =

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

= Teachers and assistants =

{| class="wikitable"
! Group !! 251 !! 252 !! 253 !! 254 !! 255 !! 256
|-
| Lecturer || colspan="6" style="text-align:center;" | [https://t.me/nkmakarov Nikita Makarov]
|-
| Seminar Instructor
| colspan="2" style="text-align:center;" | [https://t.me/vvk101 Vladimir Kurenkov]
| [https://t.me/Tony_zaika Anton Shnipov]
| [https://t.me/l_AnnaPronina_l Anna Pronina]
| colspan="2" style="text-align:center;" | [https://t.me/seemur Simon Kondakov]
|-
| Teaching Assistant
| [https://t.me/leon1dl Leonid Pavlov]
| [https://t.me/marshmel_m Maria Sudarikova]
| [https://t.me/CITNAD Dmitriy Gusev]
| [https://t.me/an4stic Anastasia Bronnikova]
| [https://t.me/dandelii Maria Samoylova]
| [https://t.me/ihelpe Yana Pavlova]
|-
| Lecturer Assistant || colspan="6" style="text-align:center;" | [https://t.me/yankiiesss Yana Arseneva]
|}
= Grading =

You may find [https://docs.google.com/spreadsheets/d/1PeiFEfWqn1XlL9qGyLEoYXrZZVTlliexcuZyXVyOE78/edit?gid=0#gid=0 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 =

{| class="wikitable"
! Contest !! Deadline !! Topic
|-
| || ||
|}

= Lectures =

Lectures are held on '''Saturday, 14:40-17:40'''.

== Lecture Materials ==

'''Sep 5'''

* 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, 3

'''Sep 12'''

* The Boyer-Moore algorithm
* The Aho-Corasick algorithm

''Bibliography'': Gusfield, ch. 2, 3

'''Sep 19'''

* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm
* Suffix trees applications: generalized suffix tree, the longest common substring for two strings, matching statistics

''Bibliography'': Gusfield, ch. 5, 6, 7

== List of topics for exam ==

* [тема 1]
* [тема 2]
* [тема 3]

Algorithms and Data Structures 1 DSBA 2025/2026

2026-06-14T17:24:20Z

Nkmakarov: List of topics for exam

= 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 [https://www.hse.ru/ba/data/courses/1072953806.html this page].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 251 !! 252 !! 253 !! 254 !! 255 !! 256 !! 257
|-
| Lecturer
| colspan="7" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
| Seminar Instructor
| colspan="3" | [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/yksee @yksee]
| tg: [https://t.me/NaviMash @NaviMash]
| tg: [https://t.me/polina_gur @polina_gur]
| tg: [https://t.me/d_poIy @d_poIy]
| tg: [https://t.me/Mellodizzz @Mellodizzz]
| tg: [https://t.me/Ignkos @Ignkos]
|-
| Lecturer Assistant
| colspan="7" | [https://t.me/ilyamaranin @ilyamaranin]
|}

= Grading =

You may find [https://docs.google.com/spreadsheets/d/1gNh2U8CpNMmzElsEsvcixd7GORehiour6SQlFfzRdhc/edit?usp=sharing 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 =

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

Algorithms and Data Structures 1 DSBA 2025/2026

2026-06-14T17:22:02Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-06-06T18:45:00Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-05-30T16:59:01Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-05-24T14:31:11Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-05-16T15:50:05Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-05-16T15:49:39Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-04-25T16:13:47Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures 1 DSBA 2025/2026

2026-04-25T16:06:31Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-03-21T19:00:04Z

Nkmakarov: Update list of topics

= 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

Algorithms and Data Structures DSBA 2025/2026

2026-03-21T18:59:02Z

Nkmakarov: List of topics for exam

= 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, two conveyors 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
* 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

Algorithms and Data Structures DSBA 2025/2026

2026-03-21T18:48:21Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-03-14T19:00:55Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-03-07T18:29:47Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-02-21T17:22:27Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-02-15T17:31:51Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-02-07T17:31:27Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-02-02T00:57:45Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-01-25T14:42:37Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-01-23T20:35:43Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-01-18T21:29:15Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2026-01-10T17:37:31Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-12-14T19:42:05Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-12-06T20:17:42Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-11-29T23:40:01Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-11-24T18:55:29Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-11-17T12:33:49Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-11-11T11:32:09Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-11-09T20:50:53Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-10-30T12:27:34Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-10-18T17:47:20Z

Nkmakarov: Update list of topics for the first module exam

Algorithms and Data Structures DSBA 2025/2026

2025-10-18T17:43:59Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-10-11T18:51:05Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-10-07T11:02:08Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-09-27T18:35:42Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-09-15T17:54:18Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2025/2026

2025-09-15T17:52:12Z

Nkmakarov:

Algorithms and Data Structures DSBA 2024/25

2025-06-14T17:55:13Z

Nkmakarov: Fix misprint

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

'''Apr 12'''
* Discrete Fourier transform
* Fast Fourier transform
* Deterministic finite automata
''Bibliography'': Cormen, ch. 30, Hopcroft, ch. 1, 2

'''Apr 19'''
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* Finite automata with epsilon-transitions
* Regular expressions
''Bibliography'': Hopcroft, ch. 2, 3

'''Apr 26'''
* Regular expressions
* Converting DFA's to RE
* Converting RE to NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch. 3

'''May 31'''
* Regular languages, the pumping lemma
* Equivalence of automata
* Context-free languages
* Context-free grammar, derivations using a grammar
''Bibliography'': Hopcroft, ch. 4, 5

'''Jun 7'''
* Derivations using a grammar, leftmost and rightmost derivations
* Parse trees
* Ambiguity in grammars and languages
''Bibliography'': Hopcroft, ch. 5

'''Jun 14'''
* Pushdown automata
''Bibliography'': Hopcroft, ch. 6

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==
* Suffix trees: naive algorithm to build a suffix tree, Ukkonen's algorithm, applications of suffix trees
* Suffix arrays: building with and without suffix tree, string matching problem using suffix array
* Dynamic programming: longest common subsequence, Levenstein distance, two conveyors problem, knapsack problem
* Greedy algorithms: activity selection problem, knapsack problem, longest increasing subsequence, Huffman codes
* Text compression: static, semistatic and adaptive models, symbolwise and dictionary models
* Symbolwise models: Huffman codes, arithmetic coding, adaptive Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
* Text modification: Burrows-Wheeler transform, move-to-front transform, RLE
* Graphs: main definitions, representation of the graphs, BFS, DFS, their applications (strongly connected components, topological sort)
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
* Disjoint sets: linked list representation, disjoint-set forest
* Single-source shortest path: Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest path: "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: DFA, NFA, NFA with epsilon transitions, regular expressions, equivalence of DFA, NFA and RE
* Context-free languages: context-free grammar, derivations, parse trees, pushdown automata

Algorithms and Data Structures DSBA 2024/25

2025-06-14T17:54:53Z

Nkmakarov: Update list of topics for exam

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

'''Apr 12'''
* Discrete Fourier transform
* Fast Fourier transform
* Deterministic finite automata
''Bibliography'': Cormen, ch. 30, Hopcroft, ch. 1, 2

'''Apr 19'''
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* Finite automata with epsilon-transitions
* Regular expressions
''Bibliography'': Hopcroft, ch. 2, 3

'''Apr 26'''
* Regular expressions
* Converting DFA's to RE
* Converting RE to NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch. 3

'''May 31'''
* Regular languages, the pumping lemma
* Rquivalence of automata
* Context-free languages
* Context-free grammar, derivations using a grammar
''Bibliography'': Hopcroft, ch. 4, 5

'''Jun 7'''
* Derivations using a grammar, leftmost and rightmost derivations
* Parse trees
* Ambiguity in grammars and languages
''Bibliography'': Hopcroft, ch. 5

'''Jun 14'''
* Pushdown automata
''Bibliography'': Hopcroft, ch. 6

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==
* Suffix trees: naive algorithm to build a suffix tree, Ukkonen's algorithm, applications of suffix trees
* Suffix arrays: building with and without suffix tree, string matching problem using suffix array
* Dynamic programming: longest common subsequence, Levenstein distance, two conveyors problem, knapsack problem
* Greedy algorithms: activity selection problem, knapsack problem, longest increasing subsequence, Huffman codes
* Text compression: static, semistatic and adaptive models, symbolwise and dictionary models
* Symbolwise models: Huffman codes, arithmetic coding, adaptive Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
* Text modification: Burrows-Wheeler transform, move-to-front transform, RLE
* Graphs: main definitions, representation of the graphs, BFS, DFS, their applications (strongly connected components, topological sort)
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
* Disjoint sets: linked list representation, disjoint-set forest
* Single-source shortest path: Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest path: "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: DFA, NFA, NFA with epsilon transitions, regular expressions, equivalence of DFA, NFA and RE
* Context-free languages: context-free grammar, derivations, parse trees, pushdown automata

Algorithms and Data Structures DSBA 2024/25

2025-06-14T17:23:26Z

Nkmakarov: Update list of lectures

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

'''Apr 12'''
* Discrete Fourier transform
* Fast Fourier transform
* Deterministic finite automata
''Bibliography'': Cormen, ch. 30, Hopcroft, ch. 1, 2

'''Apr 19'''
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* Finite automata with epsilon-transitions
* Regular expressions
''Bibliography'': Hopcroft, ch. 2, 3

'''Apr 26'''
* Regular expressions
* Converting DFA's to RE
* Converting RE to NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch. 3

'''May 31'''
* Regular languages, the pumping lemma
* Rquivalence of automata
* Context-free languages
* Context-free grammar, derivations using a grammar
''Bibliography'': Hopcroft, ch. 4, 5

'''Jun 7'''
* Derivations using a grammar, leftmost and rightmost derivations
* Parse trees
* Ambiguity in grammars and languages
''Bibliography'': Hopcroft, ch. 5

'''Jun 14'''
* Pushdown automata
''Bibliography'': Hopcroft, ch. 6

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==

Algorithms and Data Structures DSBA 2024/25

2025-06-07T18:58:00Z

Nkmakarov: Update list of lectures

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

'''Apr 12'''
* Discrete Fourier transform
* Fast Fourier transform
* Deterministic finite automata
''Bibliography'': Cormen, ch. 30, Hopcroft, ch. 1, 2

'''Apr 19'''
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* Finite automata with epsilon-transitions
* Regular expressions
''Bibliography'': Hopcroft, ch. 2, 3

'''Apr 26'''
* Regular expressions
* Converting DFA's to RE
* Converting RE to NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch. 3

'''May 31'''
* Regular languages, the pumping lemma
* Rquivalence of automata
* Context-free languages
* Context-free grammar, derivations using a grammar
''Bibliography'': Hopcroft, ch. 4, 5

'''Jun 7'''
* Derivations using a grammar, leftmost and rightmost derivations
* Parse trees
* Ambiguity in grammars and languages
''Bibliography'': Hopcroft, ch. 5

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==

Algorithms and Data Structures DSBA 2024/25

2025-04-21T13:37:32Z

Nkmakarov: Update list of lectures

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

'''Apr 12'''
* Discrete Fourier transform
* Fast Fourier transform
* Deterministic finite automata
''Bibliography'': Cormen, ch. 30, Hopcroft, ch. 1, 2

'''Apr 19'''
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* Finite automata with epsilon-transitions
* Regular expressions
''Bibliography'': Hopcroft, ch. 2, 3

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==

Algorithms and Data Structures DSBA 2024/25

2025-04-12T13:05:15Z

Nkmakarov: Update list of lectures

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

'''Mar 22'''
* Big integers, main operations
''Bibliography'': Knuth, vol.2, ch. 4.3

'''Apr 5'''
* Polynomials, coefficient representation, point-value representation, main operations
* Discrete Fourier transform
* Fast Fourier transform
''Bibliography'': Cormen, ch. 30

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==

Algorithms and Data Structures DSBA 2024/25

2025-03-17T12:28:10Z

Nkmakarov: Update list of lectures

= 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/912653105.html this page].

In case you find any inconsistencies on this page, please, contact [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l].

= Teachers and assistants =

{| class="wikitable" style="text-align:center"
|-
! Group !! 231 !! 232 !! 233 !! 234
|-
|| Lecturer
| colspan="5" | [https://www.hse.ru/org/persons/528651897 Nikita Makarov]
|-
|-
|| Seminar Instructor
| colspan="2" | [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy]
| colspan="2" | [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
|| Teaching Assistant
|| Belikov Daniil tg: [https://t.me/DanBel1kov @DanBel1kov]
|| Latyshev Ivan tg: [https://t.me/ivan_latysh @ivan_latysh]
|| Gadaev Isa tg: [https://t.me/elohimapproximation @elohimapproximation]
|| Pavlov Leonid tg: [https://t.me/leon1dl @leon1dl]
|-
|| Head TA
| colspan="5" | Pronina Anna tg: [https://t.me/l_AnnaPronina_l @l_AnnaPronina_l]
|}

= Grading =

You may find your grades [https://docs.google.com/spreadsheets/d/1JeoxJpMexYYpLPCNpzng5Xcr3SczH91BndCNhy9Cs-I/edit?gid=11487808#gid=11487808 here].

== Formula ==

'''Final Grade = M1 * 0.3 + M4 * 0.7'''

'''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
|-
|| [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms
|-
|| [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees
|-
|| [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I
|-
|| [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II
|-
|| [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/72567/enter/ Contest 6] || 18 dec 2024, 23:59:59 || Dynamic Programming
|-
|| [https://official.contest.yandex.ru/contest/75049/enter/ Contest 7] || 22 feb 2024, 23:59:59 || Graphs, DFS
|-
|| [https://official.contest.yandex.ru/contest/75538/enter/ Contest 8] || 12 mar 2024, 23:59:59 || Graphs, BFS, Dijkstra, Bellman-Ford, Floyd
|}

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

== Lecture Materials ==
'''Sep 7'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
* Lower bounds of sorting
* Counting sort
* Radix sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''Sep 14'''
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (insert, delete, rotate)
* AVL-trees, main operations
* Red-black trees, main definitions
''Bibliography'': Cormen, ch. 12, 13

'''Sep 21'''
* Red-black trees, main operations
* Treaps, main operations
* Tries, main operations
''Bibliography'': Cormen, ch. 13, Mehta, ch. 28

'''Sep 28'''
* Tries, compact tries, PATRICIA trie, main operations
* 2-3-4 trees, main operations
* B-trees, main operations
''Bibliography'': Mehta, ch. 28, Cormen, ch. 18

'''Oct 5'''
* Quiz #1
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
''Bibliography'': Gusfield, ch. 1, 2

'''Oct 12'''
* Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
''Bibliography'': Gusfield, ch. 2

'''Oct 19'''
* Exact matching with a set of patterns: Aho-Corasick algorithm
* Exact string matching: Apostolico-Giancarlo algorithm
* Suffix trees: basic definition, naive algorithm to build
''Bibliography'': Gusfield, ch. 3, 5

'''Oct 26'''
* Module 1 Exam

'''Nov 9'''
* Suffix trees: basic definition, naive algorithm to build
* Suffix trees: Ukkonen's algorithm, applications
* Suffix arrays: building using suffix tree, exact string matching
''Bibliography'': Gusfield, ch. 5, 6, 7

'''Nov 16'''
* Suffix arrays: building without suffix tree
* Dynamic programming: longest common subsequence, Levenstein distance
''Bibliography'': Cormen, ch. 15

'''Nov 23'''
* Dynamic programming: two conveyors problem, 0-1 knapsack problem
* Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
''Bibliography'': Cormen, ch. 15, 16

'''Nov 30'''
* Text compression, models: static, semistatic, adaptive, symbolwise models, dictionary models
* Serialization, tree serialization in semistatic Huffman codes
* Dictionary models: LZ-77, LZ-78, LZW
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 7'''
* Quiz #2
* Dictionary models: LZW
* Symbolwise models: arithmetic coding, adaptive Huffman codes
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Dec 14'''
* Symbolwise models: adaptive Huffman codes
* Burrows-Wheeler transform
* Move-to-Front transform
* Run-Length Encoding
''Bibliography'': Witten, ch. 2, Atallah, ch. 12

'''Jan 11'''
* Graphs: main definitions, representation of graphs
* Breadth-first search
* Depth-first search, strongly connected components
''Bibliography'': Cormen, ch. 22

'''Jan 17'''
* Topological sort
* Single-source shortest paths, Bellman-Ford algorithm
''Bibliography'': Cormen, ch. 22, 24

'''Jan 31'''
* Single-source shortest paths, Bellman-Ford algorithm, Dijkstra's algorithm
* All-pairs shortest paths, "matrix multiplication"
''Bibliography'': Cormen, ch. 24, 25

'''Feb 8'''
* All-pairs shortest paths, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''Feb 15'''
* Quiz #3

'''Feb 22'''
* Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm
* Maximum bipartite matching: Ford-Fulkerson method, Kuhn's algorithm
* Minimum spanning trees: Prim's algorithm, Kruskal's algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 1'''
* Disjoint sets: linked list representation, disjoint-set forest
* Maximum flow: push-relabel algorithm
''Bibliography'': Cormen, ch. 22, 26

'''Mar 14'''
* Preparing for the quiz
* All-pairs shortest paths, "matrix multiplication", Johnson's algorithm
* Maximum bipartite matching: Kuhn's algorithm
''Bibliography'': Cormen, ch. 25, 26

'''Mar 15'''
* Quiz #4

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
* Lower bounds of sorting using comparisons
* Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
* Binary search trees, main operations (search, insert, delete, rotate)
* AVL-trees, main operations (search, insert, delete)
* Red-black trees, main operations (search, insert)
* Treaps, main operations (search, insert, delete, split, merge)
* Tries, compact tries, main operations (search, insert, delete)
* 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
* B-trees, main operations (search, insert, delete)
* Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
* Exact matching with a set of patterns: Aho-Corasick algorithm

==List of topics for exam in module 4==

Algorithms and Data Structures DSBA 2024/25

2025-02-27T15:29:45Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2024/25

2025-02-17T18:59:10Z

Nkmakarov:

Algorithms and Data Structures DSBA 2024/25

2025-02-08T19:01:55Z

Nkmakarov:

Algorithms and Data Structures DSBA 2024/25

2025-01-31T20:05:35Z

Nkmakarov: Update list of lectures

Algorithms and Data Structures DSBA 2024/25

2025-01-18T09:58:03Z

Nkmakarov: Update lectures list