Просмотр исходного текста страницы Algorithms and Data Structures DSBA 2023/24

= About =
This page contains basic information for the course Algorithms and Data Structures in 2023/2024 academic year at Bachelor’s Programme 'HSE and University of London Double Degree Programme in Data Science and Business Analytics' (DSBA).

= Professors and assistants = 
The lecturer of the course is [https://www.hse.ru/org/persons/528651897 Nikita Makarov].

{| class="wikitable"
|-
! Group !! 221 !! 222 !! 223 !! 224
|-
| Teacher || [https://www.hse.ru/org/persons/305061980 Andrey Borevskiy] || [https://www.hse.ru/org/persons/866476408 Julio Carrasquel] || [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov] || [https://www.hse.ru/org/persons/191485259 Vladimir Kurenkov]
|-
| Assistant || Artem Makarenkov || Anastasiya Romanova || Aleksandr Petelin || Aleksandr Petelin
|}

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

==Passed and planned lectures==
'''9.09'''
* Introduction to the course
* Asymptotic notation
* Sorting algorithms: insertion sort, heap sort (including building a heap), merge sort
* Lower bounds of sorting
* Counting sort
''Bibliography'': Cormen, ch. 2, 3, 6, 8

'''16.09'''
* Radix sort
* Trees, main properties
* Binary search trees, main operations: searching, inserting, removing
* Balanced BST, AVL-tree
''Bibliography'': Cormen, ch. 8, 12, 13

'''23.09'''
* Red-black tree
* Treaps
''Bibliography'': Cormen, ch. 13

'''30.09'''
* Tries, compact tries
* PATRICIA trie, searching and inserting
* B-tree
''Bibliography'': Cormen, ch. 18; Mehta, Sahni, ch. 28

'''7.10'''
* Recap for previous topics
* Lecture quiz #1

'''13.10'''
* Hash tables
* String matching problem
* Z-algorithm
* Knuth-Morris-Pratt algorithm
''Bibliography'': Cormen, ch. 11; Gusfield, ch. 1, 2

'''20.10'''
* Knuth-Morris-Pratt algorithm
* Boyer-Moore algorithm
* Aho-Corasick algorithm
''Bibliography'': Gusfield, ch. 2, 3

'''11.11'''
* Suffix tree
* Ukkonen's algorithm
* Applications: longest common substring, suffix array
''Bibliography'': Gusfield, ch. 5, 6, 7

'''18.11'''
* Dynamic programming
* Two conveyors problem
* Longest common subsequence
* Matrix-chain multiplication
''Bibliography'': Cormen, ch. 15

'''25.11'''
* Dynamic programming, matrix-chain multiplication
* Greedy algorithms
* Activity-selection problem
* 0-1 knapsack problem, fractional knapsack problem
''Bibliography'': Cormen, ch. 15, 16

'''2.12'''
* Huffman codes
* Longest increasing subsequence
* Longest common subsequence (greedy algorithm)
''Bibliography'': Cormen, ch. 16

'''9.12'''
* Text compression
* Dictionary models: LZ-77, LZ-78
* Symbolwise models: arithmetic coding, Huffman codes
''Bibliography'': Witten, Moffat, Bell, ch. 2

'''16.12'''
* Lecture quiz #2
* Symbolwise models: adaptive Huffman codes
* Run-Length Encoding
''Bibliography'': Witten, Moffat, Bell, ch. 2

'''13.01'''
* Burrows-Wheeler transform
* Move-to-Front transform
* Prediction by partial matching
''Bibliography'': Witten, Moffat, Bell, ch. 2

'''27.01'''
* Graphs, main definitions, representations of graphs
* BFS, DFS, their applications: shortest paths, topological sort, strongly connected components
* Single-source shortest paths: Bellman-Ford algorithm, Dijkstra's algorithm
''Bibliography'': Cormen, ch. 22, 24

'''3.02'''
* All pairs shortest paths: matrix multiplication, Floyd-Warshall algorithm, Johnson's algorithm
''Bibliography'': Cormen, ch. 25

'''24.02 '''
* Disjoint sets
* Minimum spanning tree, Kruskal's algorithm, Prim's algorithm
* Maximum flow, Ford-Fulkerson method
* Maximum bipartite matching, Kuhn's algorithm
* Deterministic finite automata, basic definitions, samples
''Bibliography'': Cormen, ch. 21, 23, 26, Hopcroft, ch.2

'''2.03'''
* Lecture quiz #3
* Deterministic finite automata
* Nondeterministic finite automata
* Equivalence of DFA and NFA
* NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch.2

'''9.03'''
* Regular expressions, basic definitions
* Converting DFA to RE
* Converting RE to NFA with epsilon-transitions
''Bibliography'': Hopcroft, ch.3

'''16.03'''
* Equivalence of automata
* The pumping lemma
* Closure properties for regular languages
''Bibliography'': Hopcroft, ch.4

'''6.04'''
* Context-free grammars
''Bibliography'': Hopcroft, ch.5

'''13.04'''
* Pushdown automata, acceptance by final state, by empty stack, equivalence of acceptances
''Bibliography'': Hopcroft, ch.6

'''20.04'''
* Deterministic pushdown automata
* Chomsky normal form for context-free grammars
* The pumping lemma for context-free languages
''Bibliography'': Hopcroft, ch.6, 7

'''25.05'''
* The Turing machine
* Suffix array, how to build without suffix tree
''Bibliography'': Hopcroft, ch.8

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

'''8.06'''
* Discrete Fourier transform
* Fast Fourier transform
* Problems solving
''Bibliography'': Cormen, ch.30

'''15.06'''
* Treaps with implicit keys
* Problems solving

==List of topics for exam in module 1==
* Asymptotic notation
* Sorting algorithms: insertion sort, heap sort, merge sort, counting sort, radix sort
* Binary search trees: properties, main operations
* Balanced BST: red-black trees, AVL-trees, treaps
* Tries, compact tries
* B-trees
* Hashing
* String matching problem
* Z-algorithm
* Knuth-Morris-Pratt algorithm
* Boyer-Moore algorithm
* Aho-Corasick algorithm

==List of topics for exam in module 4==
* Dynamic programming: two conveyors problem, longest common subsequence, matrix-chain multiplication, 0-1 knapsack problem
* Greedy algorithms: activity-selection problem, fractional knapsack problem, Huffman codes, longest increasing subsequence, longest common subsequence
* Text compression
* Dictionary models: LZ-77, LZ-78
* Symbolwise models: arithmetic coding, Huffman codes, adaptive Huffman codes
* Text modification: Run-Length Encoding, Burrows-Wheeler transform, Move-to-Front transform, Prediction by partial matching
* Graphs, main definitions, representations of graphs
* Graphs, BFS, DFS, their applications: shortest paths, topological sort, strongly connected components
* Graphs, single-source shortest paths: Bellman-Ford algorithm, Dijkstra's algorithm
* Graphs, all pairs shortest paths: matrix multiplication, Floyd-Warshall algorithm, Johnson's algorithm
* Graphs, minimum spanning tree, Kruskal's algorithm, Prim's algorithm
* Graphs, maximum flow, Ford-Fulkerson method, maximum bipartite matching, Kuhn's algorithm
* Deterministic finite automata, nondeterministic finite automata, equivalence of DFA and NFA, NFA with epsilon-transitions, equivalence of automata
* Regular expressions, converting DFA to RE, converting RE to NFA with epsilon-transitions
* Context-free grammars
* Pushdown automata, acceptance by final state, by empty stack, equivalence of acceptances
* The Turing machine

= Grading =
Exams are conducted at the end of module 1 and module 4. Both of them has two parts: oral and written.

Final Grade = Module 1 Grade * 0.3 + Module 4 Grade * 0.7

Module X Grade = Exam Grade * 0.4 + Homework Grade * 0.2 + Lectures Quizzes * 0.2 + Seminar Practice * 0.2

Exam Grade = Oral Part Grade + Written Part Grade

Exam Grade, Homework Grade, Lectures Quizzes and Seminar Practice are rational numbers between 0 and 10. Oral Part Grade and Written Part Grade are integer numbers between 0 and 5. 

All fractional parts are rounded up in the final estimate.

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.

On the first retake the cumulative course grade is taken into consideration. On the second retake there are following rules:
- If the cumulative grade + 2nd retake grade >= 4, then the student receives the sum of these marks, multiplied by their coefficients.
- If the cumulative grade + 2nd retake grade < 4, but the 2nd retake grade > 7, then the student is given a 4.
- If the 2nd retake grade is <7 and the cumulative grade is <4, the student receives a failing grade.