Список заданий по продвинутым алгоритмам 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)$.
43. Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
44. Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
45. Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
46. Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
47. С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
48. Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
49. Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
50. Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
51. Обозначим как $m_k(G)$ количество паросочетаний размера $k$ в двудольном графе $G$, каждая доля которого содержит по $n$ вершин. Пусть граф содержит больше $k$ ребер. Докажите, что существует ребро $uv$, такое что $m_k(G)/m_k(G\setminus uv) \le n$.
52. Пусть вероятностный алгоритм $U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем все паросочетания равновероятны. Покажите, как с использованием $U_k$ получить $\varepsilon$-$\delta$-FRPAS для доли паросочетаний, содержащих заданное ребро $uv$ в графе $G$.
53. Покажите, как с использованием $U_k$ из предедыдущего задания получить $\varepsilon$-$\delta$-FRPAS для числа $m_k(G)$.
54. Будем называть полиномиальный вероятностный алгоритм $U_k$ равномерным с точностью до $\rho$ генератором, если он получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем для любого паросочетания $M$ $|P(U_k(G)=M) - 1/m_k(G)| \le \rho/m_k(G)$. Пусть $\rho \le 1/n^b$ для некоторого $b$. Подберите константу $b$, чтобы можно было решить задание 84, используя равномерный с точностью до $\rho$ генератор.
55. Подберите константу $b$, чтобы можно было решить задание 85, используя равномерный с точностью до $\rho$ генератор.
56. Пусть полиномиальный вероятностный алгоритм $\hat U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$ или $k-1$, причем все паросочетания равновероятны. Пусть $r = m_k(G)/m_{k-1}(G)$ удовлетворяет условию $1/n^2 \le r \le n^2$. Докажите, что с помощью $\hat U_k$ можно получить $\varepsilon$-$\delta$-FRPAS для $m_k(G)$.
57. Подберите константу $b$, чтобы можно было решить задание 88, используя равномерный с точностью до $\rho \le 1/n^b$ генератор.
58. Докажите, что если степень любой вершины в графе не меньше $n/2$, то выполнено условие $1/n^2 \le r \le n^2$ для задания 88.
59. Соедините предыдущие задания, чтобы получить из существования равномерного с точностью до $\rho \le 1/n^b$ генератора $\hat U_k$ для любого $k$ $\varepsilon$-$\delta$-FPRAS для числа совершенных паросочетаний в двудольном графе, где степени всех вершин не меньше $n/2$.
60. Рассмотрим $\varepsilon$-$\delta$-FPRAS $A$ для числа паросочетаний в двудольном графе. Используя $A$, постройте полиномиальный вероятностный алгоритм, который является равномерным генератором с точностью до $\rho = o(1)$.
61. Пусть существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в двудольном графе, степень каждой вершины которого равна хотя бы $\beta n$, где $0 < \beta < 1$. Докажите, что существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в произвольном двудольном графе.
62. Рассмотрим алгоритм приближения числа $\pi$. Будем генерировать точки с равномерным распределением в квадрате $1 \times 1$ и считать долю попавших в круг диаметром 1, вписанный в этот квадрат. Оцените число итераций, необходимое, чтобы приблизить $\pi$ с точностью до $\varepsilon$.
63. Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
64. Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?