# Algorithms and Data Structures DSBA 2023/24

Перейти к: навигация, поиск

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
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

• 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

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

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