Неделя 5
Лекция. Начинается с короткого входного теста по лекциям 2–4 (5 минут, три задачи, разбор сразу). Затем — мастер-теорема для рекуррент $aT(n/b)+\Theta(n^c)$: три случая и дерево рекурсии как рабочий инструмент; на коллоквиуме она не требуется. Дальше — слияние двух упорядоченных массивов: два указателя, инвариант результата, устойчивость. Сортировка слиянием: рекурсивная схема, корректность, дерево вызовов, $\Theta(n\log n)$ времени и $\Theta(n)$ дополнительной памяти. Быстрая сортировка, разбиения Ломуто и Хоара: инварианты и разные контракты границ. Хорошее и вырожденное дерево, случайный опорный, повторяющиеся ключи. В конце — закрепление $O$ / $\Omega$ / $\Theta$ и случаев входа.
Семинар. Пишете руками то, что на лекции было инвариантом: слияние двух упорядоченных массивов, сортировку слиянием и устойчивость по ключу, разбиение Ломуто с проверкой контракта, быструю сортировку, вырожденный вход и случайный опорный элемент. Проверки встроены в ноутбук, отдельного файла тестов нет. Встроенную сортировку на этой паре используем только как эталон проверки, не как решение. Контест недели на algo.ai.msu.ru — девять задач LeetCode; ноутбук семинаристу не сдаёте, достаточно задач на платформе.
На неделе 6 — коллоквиум 1 по лекциям 1–5. Вопросы, задачи и правила опубликованы заранее, список закрытый: коллоквиум. Готовьтесь по нему, а не по догадкам. Стек, очередь и дек — лекция и практика недели 7.