Algorithms in Practice

Analysis​

• Аналіз швидкодії типового API WEB-серверу

• Найчастіші перформанс помилки в продакшн

• Heavy Hitters для DevOps

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

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

​

Brute-force and Two pointers technique

• Техніка написання стрес-тестів

• Ітеративний перебір або як вирішити задачу "в лоб"

• Клас задач, що покриваються методом двох вказівників

• Префікс-суми на масиві та матриці

​

Searching and Sqrt decomposition

• Sentinel та як він дозволяє пришвидшити код

• Як писати код без помилок використовуючи інваріанти

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

• Коренева ідея як техніка до пришвидшення коду

• Jump search та Galloping search

• Binary search в продакшн системах та на невідсортованих даних

• Нижня оцінка на задачу пошуку

​

Sorting and Divide and Conquer

• External sort для сортування гігабайтів даних

• Задача Convex Hull або як оптимально оточити русню стіною

• Quick sort та Quick select. Задача Dutch National Flag

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

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

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

• Метод Scanline

​

Heap and Linear data structures

• Find most similar websites

• Як реалізувати підтримку TTL в Redis

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

• Ефективна реалізація динамічних масивів

• Linked list та його варіації для використання в MemSQL

• Monotonic Stack. Circular Queue

• Перевірка XML на коректність. RPN for expression evaluation

​

Greedy algorithms

• LRU cache та оптимальний cache eviction алгоритм

• Huffman coding або як стискати дані?

• Задача планування розпорядку подій

• Minimum spanning tree

​

Recursion

• Реалізація regular expressions

• Комбінаторні об'єкти та їх перебір

• Backtracking або як заповнити Sudoku

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

​

Probabilistic algorithms and data structures

• Reservoir sampling на MapReduce

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

• Вирішення колізій. Chaining та Linear Probing

• Bloom filter або що роботи якщо дані не влазять в пам'ять?

• Алгоритм Рабіна-Карпа для задачі Pattern matching

​

Dynamic programming

• The algorithm behind spell checkers

• Як LaTeX та Microsoft Word вирівнюють текст

• Git diff та причому тут обчислювальна біологія?​

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

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

​

Graphs and Trees

• Розберемо DFS та BFS і реалізуємо Web Crawler та PSTree Linux cmd

• Circular dependencies errors і при чому тут Topological sort?

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

• Binary search tree та як їх легко балансувати? AVL, Treap

• Ефективна реалізація auto-complete system на Ternary search tree