Список заданий по продвинутым алгоритмам 2023 осень

1. Докажите, что дисперсия возвращаемого значения в алгоритме Морриса не превышает $1/2n^2$
2. Докажите, что дисперсия возвращаемого значения в алгоритме Флажолета-Мартина не превышает $1/(t+1)^2$
3. Доминирующий элемент. Рассмотрим алгоритм, который ищет элемент, который встречается хотя бы $n/2$ раз в потоке $[a_1, \ldots, a_n]$. Пусть $0 \le a_i < N$ и $N \ge 2n$. Докажите, что детерминированный алгоритм, использующий $o(n\log(N/n))$ бит, не может решить поставленную задачу. Указание: рассмотрите состояние после половины элементов потока.
4. Предложите алгоритм, использующий $O(\log(N+n))$ бит, который решает предыдущую задачу в предположении, что доминирующий элемент существует.
5. Обобщите предыдущий алгоритм на случай $\varepsilon$-частых элементов: будем называть элемент $\varepsilon$-частым, если он составляет хотя бы $\varepsilon$ долю элементов во вводе. Как зависит память от $\varepsilon$?
6. Все различные. Докажите или опровергните, что любой детерминированный алгоритм, который всегда корректно отвечает, верно ли, что все элементы во вводе $[a_1, a_2, \ldots, a_n]$ различны, должен использовать хотя бы $\Omega(n\log(2N/n))$ памяти.
7. Недостающий элемент. Задан массив $[a_1, a_2, \ldots, a_{n-1}]$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно один раз. Найдите недостающий элемент, используя $O(\log n)$ памяти.
8. Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{n-2}]$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно один раз. Найдите недостающие элементы, используя $o(n)$ памяти.
9. Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{2n-1}]$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно два раза, а один — один раз. Найдите этот элемент, используя $o(n)$ памяти.
10. Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{2n-2}]$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно два раза, а два — по одному разу. Найдите эти элементы, используя $o(n)$ памяти.
11. В алгоритме KMV обозначим как $Z$ количество элементов, для которых $h(v) < kM/(1-\varepsilon)t$. Докажите, что $P(Z<k)<1/6$.
12. Задача приблизительного подсчета числа вхождений. Biased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$++, а в качестве $query(x)$ будем возвращать $cnt[h(x)]$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Оцените $P(query(x) > a(x) + \varepsilon n)$.
13. CountMin. В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $\min(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(query(x) > a(x) + \varepsilon n) < \delta$?
14. Задача приблизительного подсчета числа вхождений. Unbiased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства, а также случайную знаковую функцию $s: U \to \{-1,1\}$. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$ += s(x), а в качестве $query(x)$ будем возвращать $cnt[h(x)]\cdot s(x)$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Чему равно $E[query(x)]$?
15. В условиях предыдущей задачи докажите, что $D[query(x)] \le \frac{1}{m}\sum_y a(y)^2$.
16. В условиях предыдущих двух задач обозначим как $\lVert a \rVert_2 = \sqrt{\sum_x a(x)^2}$. Оцените $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2)$.
17. CountSketch В предыдущих трех задачах, чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $median(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2) < \delta$?
18. Сравните оценки по времени, памяти и точности для CountMin и CountSketch. Сделайте вывод, когда какой из них лучше.
19. Поиск $k$ самых частых. Используем тот или иной апроксимационный алгоритм (CountMin или CountSketch), мы хотим найти $k$ самых частых элементов в последовательности $a_1, \ldots, a_n$. Будем поддерживать $set$ из $k$ самых частых, упорядоченный по оценке на число их вхождений. Рассматривая очередной элемент, добавляем его в set, если его оценка на число вхождений становится больше, чем у самого редкого в $set$-е. Оцените вероятность, что для всех $x$ в $set$-е в конце выполнено $a(x) \ge (1-\varepsilon)a(y)$, где $y$ - это $k$-й по частоте встречаемости элемент.
20. Изменим алгоритм из предыдущего задания, будем вместо $k$ хранить $2k$ элементов, а в конце оставим $k$ из них. Как изменится вероятность?
21. Оцените зависимость вероятности из предыдущих двух заданий от $c$, если вместо $k$ хранится $ck$ элементов, а в конце оставим $k$ из них.