Неделя 9

Лекция 9. Двоичная куча: почти полное дерево на массиве, формулы индексов, просеивание вверх и вниз, построение за линейное время $\Theta(n)$, пирамидальная сортировка на месте, модуль heapq.

Семинар 9. Практика после лекции 9: своя куча на массиве, push / pop_min / heapify, паттерн поиска $k$ экстремумов за $O(n \log k)$, кортежи в heapq. Зачёт по контесту на algo.ai.msu.ru.

Лекция 9a (пятница). Динамическое программирование: мемоизация и одномерные задачи. Перекрывающиеся подзадачи, Top-Down против Bottom-Up, Фибоначчи и кузнечик, восстановление ответа, размен монет и крах жадного алгоритма, 5 шагов ДП. Практика по этому материалу — на семинаре 10.