Изменения

# Постройте массив, в котором сортировка выбором делает максимальное число обменов# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.# Найдите минимальное число сравнений для сортировки 4 элементов# Найдите минимальное число сравнений для сортировки 5 элементов# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.# Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент. # Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент. # Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.# Предложите алгоритм определения глубины сортирующей сети за $O(k)$, где $k$ - число компараторов.# Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного# Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной# Постройте сортирующую сеть для монеты энтропия максимальна 5 проводов с минимальным числом компараторов# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов. # Разберитесь в случае честной монетытом, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны# Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$# Как найти $s$-й по величине элемент в куче при малых $s$?# Предложите массив, который при превращении в кучу с помощью алгоритма за $O(n)$ требует выполнить максимальное число обменов.# Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.# В массиве есть $k$ элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \log n исходов энтропия максимальна $ действий# Докажите, что нельзя проверить, есть ли в куче два одинаковых элемента быстрее, чем за $\Omega(n \log n)$.# Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.# Проанализировать стек на саморасширяющемся массиве, если они все равновероятныпри полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.# Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти# В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти# Зафиксируйте ваш любимый язык программированияИспользования памяти без инициализации. Задан массив $a[1.. Колмогоровской сложностью n]$K. Требуется поддержать две операции: $set(i, x)$ для слова и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$ называется длина минимальной программы. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.# Счетчик Кнута. Рассмотрим массив $a[0..n-1]$. Будем считать, что в каждом элементе может быть число 0, 1 или 2 и массив представляет собой число $a[0]+a[1]\cdot 2+a[2]\cdot 4 + \ldots + a[n-1]\cdot2^{n-1}$. Требуется реализовать операцию добавления $2^k$ к числу, представленному в массиве за истинное $O(1)$ и $O(n)$ дополнительной памяти.# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти# Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"# Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая выводит слово снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.# Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$x.# Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.# Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?# Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?# Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$. # Разработайте операцию decreaseKey для тонкой кучи. Докажите, что колмогоровская сложность не превышает амортизированное время выполнения есть $HO(x1) $ (используйте потенциал $2M + CT$ , где $HM$ - число вершин, у которых удалили ребенка)# Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$# Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.# Предложите алгоритм удаления из АВЛ-дерева.# Предложите алгоритм добавления в красно-черное дерево# Предложите алгоритм удаления из красно-черного дерева# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(x\log n)$ # Предложите алгоритм разделения АВЛ- энтропия случайного источника с распределением соответствующим частотам встречания символов дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$# В АВЛ-дереве находятся вершины с ключами от 1 до $Cn$. Какие ключи могут быть в корне?# В красно-черном дереве находятся вершины с ключами от 1 до $n$ . Какие ключи могут быть в корне?# Предложите реализацию АВЛ- константадерева, в которой в каждом узле хранится $O(1)$ бит# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не зависящая от слова может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?# Пусть заданы наборы ключей $(x_1, x_2, ..., x_n)$ и $(y_1, y_2, ..., y_n)$, где все $x$-ы и все $y$-и различны. Докажите, что существует единственное декартово дерево с набором ключей в вершинах $ (но зависящая от выбранного языка программированияx_i, y_i)$# В условиях предыдущей задачи пусть $x_1 < x_2 < .. < x_n$, покажите как построить декартово дерево за $O(n)$# Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?# Проведите анализ случай zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции# Проведите анализ случай zig-zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции# Статическая оптимальность сплей-дерева. Докажите, что для любого если к ключам $1, ..., n$, сложенным в сплей-дерево выполняется m запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $c k_i > 0$ найдется слово, то суммарное время работы не превышает $O(m H(p_1, p_2, .., p_n))$, где $p_i = k_i / m$, $H$ - шенноновская энтропия# Постройте пример сплей-дерева, содержащего не менее 6 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком# Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для которого одного из самых глубоких листьев становится бамбуком# Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $K1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(x\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос# Предложите реализацию insert в декартовом дереве.# Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.# Предложите реализацию remove в декартовом дереве.# Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.# Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее) < c # Докажите оценку $O(\log^* Hn)$ для СНМ, если вместо рангов используется число вершин в поддереве (xменьшее дерево подвешивается на большее)# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ребер# Пусть заданы полные системы событий в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $A = \{a_1Omega(n)$.# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.# Для каких $a$ определен $\log^*_a x$?# Докажите, a_nчто если для $a$ и $b$ определен $\}log^*_a x$ и $B \log^*_b x$, то $\log^*_a x = O(\{b_1log^*_b x)$.# Предложите решение задачи с помощью дерева отрезков (ДО). Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить $i$-й элемент. Указание: не используйте групповые операции с модификаторами поддеревьев.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить сумму отрезке.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти элемент с минимальным индексом, больший или равный заданного значения.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^3 n)$.Заявляйте эту задачу только, b_mесли не умеете решать быстрее.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\}log^2 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Определим условную энтропию Время на запрос $HO(A | B\log n)$ как .# Предложите решение задачи с помощью ДО и деревьев поиска. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й, изменить элемент# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$-параметры запроса, получить минимум на отрезке# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества# На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \limitslog n)$ предподготовки.# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ непересекающихся отрезков из выбранного множества# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \sum_log n)$.# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти площадь объединения прямоугольников за $O(n \log n)$.# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.# Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти точку среди заданных, покрытую максимальным числом прямоугольников, за $O((n+m) \log (n+m))$.# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти прямоугольник среди заданных, содержащий максимальное число заданных точек, за $O((n+m) \log (n+m))$.# Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{i = n-1} + s[1]t^{n-2}+ ... + s[n - 2]t + s[n-1]) \bmod 2^m k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$# Пусть для хеширования строк используется полиномиальный хеш: P$h(b_is) \sum_= (s[0]t^{j = n-1}+ s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$# Пусть для хеширования строк используется полиномиальный хеш: P$h(a_j | b_is) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \log Pbmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение# Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы# Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(a_j | b_ix)= a$ и $h(x)= b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что приведенная на лекции конструкция семейства $H= \{ (ax + b) \bmod p \bmod m \}$ обладает этим свойством.# Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(A | B1/m) + H$-универсальности# Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.# Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(B1) $.# Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.# Докажите, что $\sum\limits_{i= H0}^n h(B | Ai) + H= O(An)$.# Что можно сказать про Предложите обобщение дерева Фенвика на многомерный запрос# Пусть операция в дереве Фенвика некоммутативна. Предложите модификацию, которая позволит использовать дерево Фенвика, время на запрос обновления $HO(A | B\log^2 n)$ если .# Встречное дерево Фенвика. Пусть у операции в дереве Фенвика нет обратного. Будем хранить два дерева $a_if[i]$ и $b_jg[i]$ независимы для любых , где $f[i]$ - обычное дерево Фенвика, а $g[i]$ и - сумма элементов с $ja[i + 1]$?# Что можно сказать про до $Ha[i + 2^{h(A | Ai)}]$?. Предложите алгоритм выполнения операций изменения элемента и получения статистики на отрезке в получившемся дереве.# Предложите реализацию операции удаления ключа в дереве Ван Эмде Боаса.# Предложите модификацию дерева Ван Эмде Боаса, где и минимум и максимум хранятся отдельно, но не в детях.