Lecturer: Grigoriy Khlytin @kgrigoriy
- что такое алгоритм, как записать алгоритм в виде псевдокода
- модель вычислений RAM-машина, различия с реальным железом
- базовый анализ сложности алгоритмов, введение в O-нотацию
- рекурсия, рекуррентные соотношения, оценка времени через дерево рекурсивных вызовов
- асимптотические нотации, индукция, мастер-теорема
- статический массив, динамический массив, амортизация
- немного про выделение памяти
- связные списки: интерфейс, реализации, задачи
- стек, очередь, дек: интерфейс, реализации, задачи
- сортировка подсчетом
- несколько простых квадратичных сортировок
- разделяй и властвуй, merge sort
- понятие случайности и мат. ожидания, quick sort, простая k-я статистика
- теорема о сортировках на сравнениях
- бинарный поиск
- бинарный поиск по ответу
- тернарный поиск
- интерфейс множества: insert, remove
- куча, минимум в множестве
- дерево поиска
- декартово дерево поиска как упорядоченное множество, немного про обход деревьев, итераторы
- декартово дерево как продвинутый массив: дд по неявному ключу
- префиксные суммы, идея предпросчета
- идея отложенных операций в массиве
- разреженная таблица
- понятие хеш-функции
- неупорядоченное множество, хеш-таблица
- строка как массив символов, полиномиальный хеш
- поиск подстроки в тексте
- деление на тяжелые и легкие объекты
- декомпозиция массива
- декомпозиция запросов: по времени, по пространству
- алгоритм мо
- какие бывают графы
- список ребер, список смежности, матрица смежности
- dfs, время входа и время выхода, топологическая сортировка
- компоненты связности, компоненты сильной связности, компоненты ребер 5824 ной двусвязности: мосты
- bfs, bfs с k очередями
- алгоритм дейкстры и форда-беллмана
- минимальное остовное дерево + система непересекающихся множеств на практике
- базовые примеры
- отличия от полного перебора и жадных алгоритмов
- дп по префиксу, дп по подотрезку, примеры задач
- рюкзак
- мемоизация с хеш-мапой