# 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 (preliminarily)

• Dynamic programming, matrix-chain multiplication
• Greedy algorithms
• Activity-selection problem
• Huffman codes

Bibliography: Cormen, ch. 15, 16

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