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 Nikita Makarov.

Group	221	222	223	224
Teacher	Andrey Borevskiy	Julio Carrasquel	Vladimir Kurenkov	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.