\documentclass[12pt]{article}

\usepackage{amsfonts,amssymb}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{color}
\usepackage{listings}
\usepackage{hyperref}

\usepackage{tikz}
\usepackage{float}


\lstset{language=C++,
                basicstyle=\footnotesize \ttfamily,
                keywordstyle=\color{blue}\ttfamily,
                stringstyle=\color{red}\ttfamily,
                commentstyle=\color{green}\ttfamily,
                morecomment=[l][\color{magenta}]{\#}
}


%\textheight=230mm
%\textwidth=180mm
%\topmargin=-5mm

\textheight=230mm
\textwidth=190mm
%\oddsidemargin=5mm
%\evensidemargin=-5mm
\marginparwidth=0pt
\topmargin=0cm
\renewcommand{\baselinestretch}{0.9}
%\footnotesep=3ex

\title{Алгоритмы и структуры данных. \\ Сортировки и порядковые статистики, решаем вместе.}

%\author{Артюхин С., Евстропов Г., Иващенко Д., Смирнов И. \\ hse.algo@gmail.com}
\date{}

\begin{document}

\voffset=-10mm
\hoffset=-30mm
\font\Got=eufm10 scaled\magstep2 \font\Got=eufm10

\maketitle
\begin{enumerate}

\item Обсудите рандомизированный алгоритм поиска порядковой статистики. Используя схему доказательства асимптотики алгоритма по индукции, покажите, что рандомизированный поиск порядковой статистики работает за ожидаемое линейное время.
% Это упражнение на тренировку доказательства асимптотики алгоритма по индукции, его обязательно нужно сделать именно так.
% Пусть ожидаемое время работы алгоритма t(n) = O(n), то есть существует C, такое что t(n) <= c * n.
% Выпишем рекурсивную оценку. t(n) <= Theta(n) + max_k (1 / n (sum_{i = 1}^{k} t(n - i) + sum_{i = k}^{n} t(i))), то есть мы платим линию за раскидывание массива на две части и дальше идём в ту часть, куда попало число k. Для оценки сверху нас устроит каждый раз выбирать наиболее неподходящее значение k.
% Подставим рекурсивную оценку на t(n - i) и t(i)
% t(n) <= A * n + max_k (1 / n (sum_{i = 1}^k c * (n - i) + sum_{i = k}^{n} c * (i))) <= A * n + max_k c * (k * (2n - k) / 2 + ((n - k + 1) * (n + k) / 2)) / n <= |k = n / 2| <= A * n + c * (1 / n) * ((n / 2) * (3n/2) / 2 + (n / 2) * (3n / 2) / 2) <= A * n + c * 3/4 * n <= |C >= 4 * A| <= c * n
% Почему можно так дерзко подставить k = n / 2? Способы по убыванию дерзости.
% 1. Просто в силу симметрии это очевидно
% 2. Функция от k - парабола, причём выпуклая вверх, так как при k^2 стоит минус. В силу симметрии

\item Покажите, как реализовать алгоритм сортировки вставками, чтобы время его работы составляло $O(n + inv)$, где $inv$~--- количество инверсий в массиве.
% При добавлении нового элемента мы свапаем его пока свапается, каждый раз убивая одну инверсию.

\item Пусть у вас есть массив с элементами некоторого типа, для любой пары элементов вам доступна операция сравнения. Некоторые элементы равны, но при этом всё равно отличимы по вспомогательной информации. Разрешается изменять вспомогательную информацию элементов (то есть никак не используемую при сравнении). Также имеется функция \emph{MagicSort} которая за линейное время сортирует массив элементов данного типа. Обращение к данной функции возможно только как к чёрному ящику.  Предложите, как на основе функции \emph{MagicSort} построить устойчивый алгоритм сортировки за линейное время.
% Не принимать решения вида "посортируем пары", так как алгоритм именно чёрный ящик - не разрешается менять используемые при сортировке поля.
% Правильные решения бывают разные, одно из них: в качестве вспомогательной информации будем тащить номер элемента в массиве, после сортировки выделим классы эквивалентности и с помощью сортировки подсчётом отсортируем пары <класс эквивалентности, номер в массиве>

\item Оцените время работы алгоритма быстрой сортировки Хоара, в случае если в качестве $pivot$ элемента выбирается:
\begin{enumerate}
    \item Элемент стоящий посередине, то есть $a[(lb + rb) / 2]$. Оцените время работы в худшем случае, в среднем (ожидаемое) и на случайных данных.
    \item Медиана случайных $\sqrt{rb - lb + 1}$ элементов. Оцените время работы в худшем, в среднем (ожидаемое) и на случайных данных.
\end{enumerate}
% пункт 1: в худшем и в среднем O(n^2), на случайных O(n \log n)
% в худшем можно построить явно пример, где на середину всё время подсовывается максимум или минимум. Понятие "ожидаемое" не имеет смысла, так как схема детерменированная.
% Почему на случайных n log n? Мы не готовы это строго аргументировать, первый элемент понятно почему случайный, дальше в рекурсивных кусках "примерно" случайные перестановки.
% пункт 2: в худшем O(n \sqrt{n}), так как всегда отрезаем хотя бы корень пополам. В среднем и на случайных O(n \log n)
% Если за линейное время отрезать корень, то получаем t(n) = Theta(n) + t(n - sqrt{n}), можно доказать по индукции (а можно и не доказывать).
% Почему медиана случайных даёт оценку O(n log n)?
% Мы знаем рекурсивную оценку для случайного выбора ведущего элемента:
% t(n) = Theta(n) + sum_k (t(k) + t(n - k)) / n.
% При этом мы знаем, что во-первых эта рекуррента решается в O(n log n), во-вторых для сортировки тем хуже, чем ближе k к 1 или к n.
% Из соображений здравого смысла понятно, что у медианы sqrt(n) случайных распределение ближе к середине, чем у просто случайно выбранного.
% Если хочется доказать прям строго, то можно записать рекурренту так:
% t(n) <= Theta(n) + P(k < n / 4 or k > 3n / 4) * t(n - 1) + P(k >= n / 4 and k <= 3n / 4) * (t(3n / 4) + t(n / 4)). Теперь надо оценить вероятность, что больше половины загремит в первую четверть, или наоборот в последнюю четверть. Заметим, что рекуррента сойдётся к O(n log n) даже если показать P(k < n / 4 or k > 3n / 4) <= 1 / 2, как для случайного выбора вещущего элемента. Вероятность, что медианным будет элемент с индексом k равняется c(k - 1, sqrt(n) / 2) * c(n - k, sqrt(n) / 2) / c(n, sqrt(n)), то есть количество выбрать половину слева, умноженное на количество способов выбрать половину справа, поделить на количество способов выбрать sqrt(n) из n всего. Тут уже можно выписать явную формулу и честно предъявить, что монотонно растёт с приближением к середине, значит вероятность медиане загреметь в первую или последнюю четверть ниже 1 / 2.

\item Даны $n$ строк суммарной длины $L$. Чему будет равно математическое ожидание времени работы алгоритма быстрой сортировки, при условии что лексикографическое сравнение двух строк выполняется наивно?
% L log n, потому что на каждом шаге каждый элемент только один раз будет сравниваться с барьерным, то есть суммарное время работы на одном уровне рекурсии не превосходит L.

\item Инверсией называется пара $(i, j)$, такая что $i < j$ и $a_i > a_j$. Обсудите как модифицировать алгоритм сортировки слиянием, чтобы параллельно вычислять число инверсий.
% При слиянии двух списков, когда берём минимальный элемент из правого списка, прибавляем к числу инверсий текущий размер левого списка.

\pagebreak

    \item Супер-инверсией называется тройка $(i, j, k)$, такая что $i < j < k$ и $a_i > a_j > a_k$. Предложите алгоритм подсчёта количества супер-инверсий за время $O(n \log n)$, основанный на сортировке слиянием. Как обобщить алгоритм на поиск $k$-инверсий, то есть наборов $i_1 < i_2 < \ldots < l_k$, что $a_{i_1} > a_{i_2} > \ldots > a_{i_k}$.
% Заметим, что в алгоритме сортировки слиянием мы могли не просто считать число инверсий, но и для любого элемента хранить, для какого количества инверсий он является правым концом. Вычислим это первой итерацией.
% Теперь делаем вторую итерацию, но когда в слиянии раньше происходило прибавление размера левого списка, теперь происходит прибавление суммы вычисленной ранее функции количества обычных инверсий по всему левому списку.

\item Пусть некоторый алгоритм выбирает случайную пару элементов $(i, j)$ и меняет их местами, если они нарушают условие упорядоченности. Покажите, что математическое ожидание количества действий данного алгоритма:
\begin{enumerate}
    \item $O(n^4)$;
    \item $O(n^2 \log n)$;
\end{enumerate}
% Пусть в массиве сейчас x инверсий, тогда мы ткнёмся в неправильную пару с вероятностью не менее x / n^2. Тогда ожидаемое количество действий до уменьшения инверсии не более n^2. Поскольку инверсий не более n^2, получаем n^2 * n^2 = n^4
% Однако, на самом деле это оценка сильно сверху. Нам требуется просуммировать n^2 / i по всем i от 1 до n^2, это будет n^2 log n.
% Мб и эту оценку можно улучшить, потому что мы можем убивать больше одной инверсии за раз. Но я не знаю как там что-то доказать.

\item Докажите, что поиск элемента в отсортированном массиве, использующий лишь операции сравнения, в худшем случае работает не быстрее, чем за $O(\log~n)$.
    % Рассмотрим дерево работы программы в зависимости от сравнений. У дерева должно быть хотя бы n листьев, значит его глубина состваляет хотя бы log n


\end{enumerate}


\end{document}