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

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) \log(n))$.
24. Докажите, что можно найти транзитивное замыкание графа за время $O(BP(n))$.
25. Пусть $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$.
26. Пусть $MM(n)=n^{2+\varepsilon}$, $\varepsilon>0$. Модифицируйте алгоритм построения BPWM, чтобы он работал за $MM(n) \log n$. Почему эта идея не сработает, если $MM(n) = O(n^2)$?
27. Докажите лемму с лекции про то, что если в урне $n$ шаров, из которых $w$ белых и $n/2\le wr \le n$, а событие $A$ означает, что из $r$ наугад выбранных из урны шаров оказался ровно один белый, то $P(A) \ge 1/2e$.
28. Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
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. $1 | p_i=1 | L_{max}$.
52. $1 | r_i, d_i=d | L_{max}$.
53. $1 | prec, r_i, p_i=1 | L_{max}$.
54. Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
55. $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
56. $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
57. $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
58. $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
59. $1 || \sum U_i$
60. $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
61. Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
62. Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
63. $P | pmtn, r_i | C_{max}$
64. $P | pmtn, r_i | L_{max}$
65. $Q | pmtn, r_i | C_{max}$
66. $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
67. $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца
68. $P | p_i = 1 | \sum w_iC_i$
69. $P | p_i = 1, pmtn | \sum w_iC_i$
70. $Q | pmtn | \sum C_i$
71. $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
72. $Q | pmtn | f_{max}$
73. $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
74. Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
75. $P|intree, p_i=1|L_{max}$
76. $F | p_{ij} = 1 | \sum C_i$
77. $F2 | pmtn | C_{max}$
78. $F | p_{ij} = 1 | \sum U_i$
79. $F | p_{ij} = 1 | \sum w_iU_i$
80. $O | p_{ij} = 1 | C_{max}$
81. $O | p_{ij} = 1 | \sum C_i$
82. $O | p_{ij} = 1 | \sum w_iC_i$
83. $O | p_{ij} = 1, d_i | -$
84. $O | p_{ij} = 1 | \sum U_i$
85. $O | p_{ij} = 1 | \sum w_iU_i$
86. $O | p_{ij} = 1, r_i | C_{max}$
87. $O2 | p_{ij} = 1, prec | \sum C_i$