Список заданий по продвинутым алгоритмам 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$ из них.
22. Обозначим как $BP(n)$ время умножения булевых матриц размера $n \times n$ над $\vee, \wedge$. Обозначим как $MM(n)$ время умножения целочисленных матриц размера $n \times n$ над $+, \times$. Докажите, что $BP(n) = O(MM(n))$.
23. Докажите, что можно найти транзитивное замыкание графа за время $O(BP(n))$.
24. Пусть $A$ и $B$ - матрицы размера $n \times n$. Пусть $R \subset \{1, 2, \ldots, n\}$, $|R|=r$. Обозначим как $A^R$ матрицу, которая получается из $A$ удалением всех столбцов, кроме столбцов из множества $R$. Аналогично, обозначим как $B_R$ матрицу, которая получается из $B$ удалением всех строк, кроме строк из множества $R$. Докажите, что произведение матриц $A^R\cdot B_R$ может быть найдено за время $O((n/r)^2 MM(r))$, где $MM(r)$ - время умножения матриц размером $r\times r$.
25. Пусть $MM(n)=n^{2+\varepsilon}$, $\varepsilon>0$. Модифицируйте алгоритм построения BPWM, чтобы он работал за $MM(n) \log n$. Почему эта идея не сработает, если $MM(n) = O(n^2)$?
26. Докажите лемму с лекции про то, что если в урне $n$ шаров, из которых $w$ белых и $n/2\le wr \le n$, а событие $A$ означает, что из $r$ наугад выбранных из урны шаров оказался ровно один белый, то $P(A) \ge 1/2e$.
27. Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
28. Как воспользоваться алгоритмом построения BPWM для поиска кратчайших путей между всеми вершинами в графе?
29. Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
30. Дерево Кинг. Дано взвешенное дерево $T$. Запустим на дереве $T$ алгоритм Борувки, когда множество вершин $S$ объединяется в новую вершину $s$ для каждой вершины из $u$ добавим ребро из $u$ в $s$ с весом, равным минимальному весу ребра, инцидентного $u$ на этом шаге (того ребра, которое выбирает алгоритм Борувки). Докажите, что задача максимума на пути между листьями в полученном дереве эквивалентна задаче максимума на пути в исходном дереве $T$.
31. Рассмотрим ветвящееся дерево (у каждой внутренней вершины хотя бы два сына, все листья на одном уровне), пусть в нем $n$ вершин. Пусть есть $m$ запросов на пары листьев, для которых необходимо найти максимальное ребро на пути. Разобьем каждый запрос на два запроса на вертикальном пути до $LCA$ этих листьев, таким образом имеем $2m$ вертикальных путей. Для вершины $v$ обозначим как $A(v)$ множество вертикальных путей, проходящих через $v$. Обозначим как $D_i$ множество вершин на расстоянии $i$ от корня, как $d_i$ число вершин на расстоянии $i$ от корня ($d_i=|D_i|$). Докажите, что $\sum\limits_{u\in D_i}\lceil\log(1+|A(u)|)\rceil<\sum\limits_{u\in D_i}\left(1+\log(1+|A(u)|)\right)\le d_i+d_i \log\frac{d_i+2m}{d_i}$.
32. В условиях предыдущей задачи докажите, что $\sum\limits_{i\ge 0}\left(d_i + d_i\log\frac{d_i+2m}{d_i}\right)\le n+n\log\frac{n+2m}{n}+2n$.
33. Докажите, что $\sum\limits_{u}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
34. Готовимся к алгоритму линейной верификации MST. Введем операцию на множествах целых чисел: $A \downarrow B = \{b \in B | \exists a \in A : a < b \mbox{ and there is no } b′ \in B \mbox{ with } a < b′ < b\}$. Докажите, что $A\downarrow B \subset B$, $|A \downarrow B| \le |A|$, $(A\cup B)\downarrow C = (A \downarrow C) \cup (B \downarrow C)$, $A \downarrow (B \cup C) \subset (A \downarrow B) \cup (A \downarrow C)$.
35. Докажите, что если $A \downarrow B = \varnothing$, то $A \downarrow C = A \downarrow (C \setminus B)$.
36. Докажите, что если $A \downarrow B \subset C \subset B$, то $A \downarrow B = A \downarrow C$.
37. Докажите, что если $\sup(B \cap C) < \inf(B \setminus C)$, то $A \downarrow (B \cap C) = (A \downarrow B) \cap C$ (будем считать, что $\sup\varnothing = -\infty$, $\inf\varnothing = +\infty$).
38. Докажите, что если $A \subset B$, то $A \downarrow C = A \downarrow (B \downarrow C)$.
39. Будем хранить множество чисел от 0 до $w-1$, где $w$ - размер машинного слова, как битовую маску. Докажите, что если $A$ задается маской $a$, а $B$ задается маской $b$, то $A \downarrow B$ задается маской $b\&(\sim(a|b){\verb!^!}(a+(a|\sim b)))$.
40. Обозначим как $d(u)$ глубину вершины $u$. Обозначим как $w(v)$ вес ребра из $v$ в родителя. Обозначим как $p^j(u)$ вершину, которая получается из $u$ переходом $j$ раз к родителю. Обозначим как $M_v = \{j\,|\,1 \le j \le d(v): w(p^j(v)) > w(p^k(v)) \mbox{ for all } k = j + 1, \ldots, d(v)\}$. Пусть $u$ - предок $v$. Докажите, что максимальный вес ребра на пути из $u$ в $v$ находится на ребре в родителя из вершины $p^j(v)$, где $j$ - единственный элемент множества $\{d(u)\}\downarrow M_v$.
41. Обозначим как $D_v = \{d(u) | \mbox{ there is a query path $uw$ that contains $v$}\}$. Пусть $S_v = D_v \downarrow M_v$. Докажите, что в условии предыдущей задачи $\{d(u)\}\downarrow M_v = \{d(u)\} \downarrow S_v$.
42. Предложите алгоритм подсчета $D_v$ для всех вершин дерева за $O(n + m)$ (считайте, что битовые операции выполняются за $O(1)$.