Foreign students. Data Structures and Algorithms I 2025

Материал из Public ATP Wiki
Версия от 10:56, 25 февраля 2025; Irinaiv (обсуждение | вклад) (General information)
Перейти к: навигация, поиск

General information

Teacher

  • Galanov Ilia Iurevich

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