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
Literature
- Introduction to Algorithms, 4th Edition by Thomas H. Corman
- The C++ Programming Language, 4th Edition by Bjarne Stroustrup