• DFS і BFS як два погляди на обхід графу

• Топологічне сортування й детекція циклів: порядок збірки, розв'язання залежностей, dependency hell у пакетних менеджерах

• Знаходження найкоротших шляхів: Dijkstra vs. Bellman-Ford

• Бінарні дерева пошуку (BST) та як їх балансувати: AVL, Treap

• Trie і Ternary Search Tree

Практика

• State machine як граф: вершини — стани системи, ребра — дозволені переходи, і граф ніде не заданий явно

• Пишемо web crawler на BFS — та сама модель, що в основі індексаторів пошуковиків

• Автодоповнення на Trie/TST: префіксний пошук із ранжуванням за популярністю — те, що відпрацьовує під рядком пошуку на кожному великому сайті

•  Lowest common ancestor (binary lifting)

• Від рекурсії з memoization до bottom-up таблиці: одна й та сама ідея під двома кутами, і коли який вигідніший за пам'яттю

• Edit distance (Левенштейн): скільки правок між двома рядками — основа spell-check, fuzzy search і автокорекції

• Sequence alignment: git diff, LCS і той самий алгоритм, що вирівнює ДНК у біоінформатиці

• Як виграти в Blackjack та «красиво» зменшити розмір картинки

• Knapsack та оптимальний шлях робота в лабіринті

Практика

• Реалізуємо edit distance і будуємо на ньому мінімальний «did you mean?» — той самий кістяк, що в пошуку й текстових редакторах

• Як LaTeX та Microsoft Word вирівнюють текст по ширині рядка?

• Як компактно представити хеш-таблицю в пам'яті

• Хеш-функції й колізії: chaining vs open addressing, linear probing, load factor і чому resize неминучий

• Bloom Filter: як за крихітну памʼять відповідати “цього точно немає” з ризиком false positive — і економити дорогі походи в БД, як у Cassandra чи Bigtable

• HyperLogLog: порахувати кількість унікальних серед мільярдів за кілька кілобайт — як це рахує unique visitors аналітика

• Rabin–Karp: хешування рядка для пошуку патерну й rolling hash, на якому будується дедуплікація і rsync

Практика

• Reservoir sampling: чесний випадковий семпл із потоку невідомої довжини — те, що працює в MapReduce та аналітиці на льоту

• Shuffle: як чесно перемішати масив так, щоб кожна перестановка мала однакову ймовірність — від Fisher–Yates до типових помилок у “random sort”, які непомітно ламають випадковість

• Коли жадібність взагалі коректна: exchange argument замість «здається, спрацює»

• Кешування як greedy-задача: чому LRU — це лише евристика. Який алгоритм кешування оптимальний?

• Huffman coding: як побудувати оптимальний код без втрат — те, що всередині gzip, JPEG і HTTP-стиснення

• Оптимальне планування подій: коли жадібний підхід працює?

• Minimum Spanning Tree через Kruskal/Prim: найдешевший спосіб з'єднати все — від мереж до кластеризації

Практика

• Реалізуємо Huffman-кодер і стискаємо реальний текстовий файл

• Interval scheduling: максимум несуперечливих задач — основа планувальників, бронювань і розподілу ресурсів

• Динамічні масиви зсередини: amortized O(1) на append, чому ріст саме ×2 і скільки реально коштує append у Python чи push_back у C++

• Як зробити Linked list швидким? Skip list на практиці

• Stack зсередини: реалізація через dynamic array і через linked list. Monotonic stack та як він використовується для аналізу ринку акцій

• Queue зсередини: від наївної реалізації до циклічного буфера — розбираємо, чому черга на масиві не повинна зсувати всі елементи після кожного pop, як head і tail перетворюють масив на кільце

• Heap та priority queue: структура для ситуацій, де дані постійно змінюються, але нам завжди треба швидко дістати “найважливіший” елемент

Практика

• TTL у Redis: як expiry мільйонів ключів робиться без сканування всієї бази

• Перевірка коректності XML та RPN для обчислення виразів

• Top-K найпопулярніших елементів в потоці даних

• Union-Find: міста зʼєднуються дорогами, користувачі — у кластери, вершини графа — в одну компоненту. Як підтримувати це ефективно

•  LRU cache: задача з реальних кешів, браузерів та баз даних

• External sort: як відсортувати 100 GB на машині з 8 GB RAM — те, що реально роблять бази даних і MapReduce

• Quick sort і Quick select: пошук k-ї статистики за O(n) і задача Dutch National Flag

• Зв’язок між Selection sort та Heap sort

• Неасимптотичні оптимізації Merge sort та Insertion sort

• Radix sort: як відсортувати 1 000 000 чисел швидше за Quick sort

• Метод Scanline: обробка подій у відсортованому порядку

Практика

• Як пришвидшити bubble sort в 2 рази, не міняючи основну ідею? А як в 50 разів?

• External merge sort на прикладі того, як PostgreSQL сортує результат ORDER BY, що не вміщається в work_mem

• Convex hull: як оптимально оточити множину точок мінімальною оболонкою

• Інваріанти як спосіб писати код без помилок. Binary search без off-by-one — раз і назавжди, замість вгадування <= чи <

• Лінійний пошук для гри Minesweeper та Run-length encoding. Sentinel linear search

• Коренева декомпозиція (sqrt decomposition): техніка для прискорення коду. Коли segment tree — overkill?

• Binary search не по масиву, а по відповіді: шукаємо мінімальне валідне значення, коли явного відсортованого масиву взагалі немає

• Binary search на невідсортованих і «майже відсортованих» даних

• Jump search і Galloping search: коли бінарний пошук — не єдиний вихід

• Чи можливо в теорії шукати швидше ніж за log n? Нижня межа складності задачі пошуку

Практика

• git bisect як binary search по комітах: знайти один баг-коміт серед тисяч за log(n) кроків 

• Реалізуємо versioned key-value store, який пам'ятає, яке значення мав ключ у будь-який момент часу

•  Знайти кінець лога на S3 без сортування. Append-only лог, файли з послідовними номерами, машина впала — треба знайти найбільший номер. Сканувати весь bucket дорого (LIST коштує як PUT), верхньої межі немає

• Скільки насправді коштує «вигідний» автокредит (binary search on answer). Дилер говорить лише про розмір місячного платежу, а справжню процентну ставку — мовчки приховує

• Two pointers: opposite ends і same direction — паттерни, що перетворюють O(n²) на O(n) без зміни ідеї алгоритму

• Sliding window: робота з рухомим вікном даних і умови монотонності, за яких воно працює

• Prefix sums: O(1) на запит про суму діапазону замість O(n) — фундамент під range queries

• 2D prefix sums та integral images: основа Viola–Jones face detection, що досі живе у camera hardware

• Difference arrays: bulk-оновлення діапазонів за O(1) на запит — як це працює у системах бронювання

Практика

• Алгоритм, що лежить в основі SQL JOIN, повнотекстового пошуку (inverted index у Google і Elasticsearch) та рекомендацій типу «common friends» у соцмережах

• Реалізуємо integral image — структуру з 2D prefix sums, яку у 2001 році використали в алгоритмі Viola–Jones для першого face detection у реальному часі на CPU тих років

• Рекурсія як декомпозиція: звести задачу до меншої копії себе і не втратити контроль над глибиною стека

• Backtracking з відсіканням — як не перебирати очевидно мертві гілки

• Генерація перестановок, підмножин, розміщень, комбінацій — каркас під будь-яку переборну задачу

• Хвостова рекурсія та Tail Call оптимізація

• Beam Search: як шукати не ідеальний, а достатньо хороший розвʼязок

Практика

• Пишемо мінімальний regex engine. Чому деякі регулярки "вбивають" сервіс через catastrophic backtracking (ReDoS) — реальний клас вразливостей

• Рекурсивний спуск, що парсить і рахує арифметичний вираз з дужками й пріоритетами — той самий кістяк, що в інтерпретаторах і калькуляторах

• 8 Queens і Sudoku Solver: як рекурсивно будувати розвʼязок, швидко перевіряти обмеження та відсікати неможливі гілки до того, як перебір вибухне

• Ітеративний перебір як baseline: коректне просте рішення, від якого відштовхуємося в оптимізації

• Прогноз за обмеженнями: як з аналізу коду зрозуміти, чи пройде рішення за часом і пам'яттю, ще до написання коду

• Коли brute force — це і є правильна відповідь: малі n, дедлайн важливіший за мікрооптимізацію, читабельність дорожча за швидкість

• Stress testing — техніка, якою ловлять баги, що проходять крізь звичайні unit-тести

Практика

• Closest pair of points: серед тисяч об'єктів на екрані знайти два найближчі — задача, що виникає у collision detection в іграх, фізичних симуляціях і кластеризації даних

• Convex hull: побудувати мінімальну опуклу оболонку, що охоплює задану множину точок — задача, що лежить в основі визначення меж об'єктів у комп'ютерному зорі, виявлення колізій у CAD-системах та оптимізації маршрутів

• Heavy Hitters у DevOps: як швидко виявляти запити, що генерують більше X% трафіку 

• Аналіз швидкодії API веб-сервера

• Асимптотичний аналіз ітеративних та рекурсивних алгоритмів 

• Аналіз ймовірнісних алгоритмів