Foreign students. Data Structures and Algorithms I 2025

General information

Teacher

• Галанов Илья Юрьевич

Course program

Unit 1: Introduction 1. Introduction. Complexity. RAM-model. 2. Linked Lists. Stack implementation using a linked list or an array. Keeping minimum in a stack. Correct brackets sequence checking. Monotonic stack

Unit 2: Sorting 1. Sortings. Lower bound for comparisons in the sort. Insertion sort. Bubble Sort. Selection Sort. 2. Quick Sort. 3. Merge Sort. Master Theorem. 4. Binary Heap. Sift Up, Sift Down, Insert, GetMin, ExtractMin and DecreaseKey. Heap Sort

Unit 3: Trees 1. Binary Search Trees. Insert & Delete & BST Sort. 2. Balanced Binary search Trees. AVL Tree. Height of AVL Tree on n nodes.

Unit 4: Hashing 1. Hash Table Chaining. Insert & Delete & Search 2. Hash Table Open Addressing. Insert & Delete & Search 3. Bloom Filter. Insert & Search. Applications

Links

• Телеграм чат
• Materials (will be updated during the course)
• Lectures from previous years

Literature

• Introduction to Algorithms, 4th Edition by Thomas H. Corman
• The C++ Programming Language, 4th Edition by Bjarne Stroustrup