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

Bibliography: Cormen, ch. 22, 24

3.02

• All pairs shortest paths: matrix multiplication, Floyd-Warshall algorithm, Johnson's algorithm

Bibliography: Cormen, ch. 25

17.02 (preliminary)

• Disjoint sets
• Minimum spanning tree, Kruskal's algorithm, Prim's algorithm
• Maximum flow, Ford-Fulkerson method
• Maximum bipartite matching

Bibliography: Cormen, ch. 21, 23, 26

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

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