Алгоритмы и структуры данных, семинар группы 158-2 — различия между версиями

Текущая версия на 14:19, 1 июня 2016

Текущие результаты могут быть найдены здесь.

Правила игры

В основном все общение будет происходить с семинаристом курса, однако к проверке работы также будет привлекаться и учебный ассистент. Если у студента есть некоторые разногласия с ассистентом, то он всегда может обратиться к семинаристу, чтобы разрешить конфликт.

Семинарист: Симагин Денис, simagin.mail@yandex.ru

Ассистент: Владимир Гончаров, dev.zelta@gmail.com

Старайтесь не опаздывать на семинары, иначе вы можете прослушать важные анонсы, которые обычно будут проходить в начале занятий. А также пропустите много полезного. Приходите, будет интересно!

Структура курса

В ходе курса студентам будут предложены пять домашних заданий, практическая контрольная работа, а в заключении итоговый экзамен. Также в течении семестра необходимо активно участвовать в семинарах, решая задачки и выполняя практические упражнения, предусмотренные для самостоятельной работы.

Домашние задания

Домашнее задание делится на две части. Теоретическая, сводится к решению задач. Решение необходимо отправлять в виде pdf на почту семинаристу, а также можно приносить на листочках на семинар, если это оговорено заранее. Практическая, предусматривает сдачу задачи в контест. Также вы должны прислать семинаристу pdf с обоснованием правильности работы алгоритма и оценкой сложности. При этом на семинаре вы должны защитить одну из задач.

Если я хочу прислать решение по 1-му домашнему заданию, а меня зовут Симагин Денис, то тема письма должна выглядеть так:

   H1 - Симагин Денис.

Семинары

Вся ваша деятельность на семинарах делится на две части. Работа на семинаре и решение упражнений, которые вам даны для самостоятельного рассмотрения дома. Вы получаете плюсики за каждое решеное упражнение, а также за активное участие в семинаре, обычно это разбор небольшой задачи у доски (не более одного плюсика за занятие).

Упражнения стоит присылать на почту семинаристу, при этом тема письма должна строго удовлетворять формату. К примеру, меня зовут Симагин Денис и я хочу отправить задачу с первого семинара, тогда заголовок письма должен иметь вид

   A01.21: Разворот списка - Симагин Денис.

Объединять несколько решений в одном письме нельзя, это лишь создаст путаницу в обсуждении. При нарушении правил семинарист не дает гарантий, что решение будет проверено.

Формула оценки

Оценка за семинары вычисляется следующим образом

   OСеминар = Сн·N/Nmax,

   N – количество набранных плюсов,
   Nmax – максимальное количество плюсов,
   Сн – нормирующий коэффициент (будет объявлен в конце семестра).

Оценка за домашние работы вычисляется как среднее за все 5 сданных работ. За работу в течении семестра студент получает накопленную оценку

   OНакопленная =  0.2·ОКонтрольная + 0.6·ОДомашние задания + 0.2·ОСеминары.

Итоговая оценка складывается из накопленной оценки и экзамена

   OИтоговая =  0.3·ОЭкзамена + 0.7·ОНакопленная.

Домашние задания

Задание H1

1. Первая часть (16 февраля, 9:00)
2. Вторая часть (16 февраля, 9:00)
3. Контест (20 февраля, 20:00), решение.

Распределение задач здесь.

Задание H2

1. Контест на динамику, дедлайн (2 марта, 20:00), решение.
2. Контест на графы, дедлайн (14 марта, 20:00).

Распределение задач можно найти здесь.

Задание H3

1. Контест на кратчайшии пути, дедлайн (3 апреля, 20:00), [решение].
2. Контест на хеширование, дедлайн (26 апреля, 20:00), [решение].

Распределение задач можно найти здесь.

Задание H4

1. Контест сборная солянка (22 мая, 23:59), [решение].

Распределение задач можно найти здесь.

Задание H5

1. Листочек с теорией на конечные автоматы и регулярные языки (4 июня, 23:59), [решение].

Распределение задач можно найти здесь.

Семинары

Семинар A05.10

Оперативно разбирали темы, необходимые для домашней работы.

1. Поговорили о жадном алгоритме декодирования префиксного кодирования. Для этого вам может потребоваться бор. Кстати, классическим примером префиксного кодирования является код Хаффмана.
2. Поговорили о системе непересекающихся множеств. На семинаре была дана только верхняя оценка работы.
3. Повторили двоичные кучи.

Семинар A04.26

Сегодня был только один человек на семинаре, да и то с большим опозданием.

Рассмотренные вопросы

1. Дерево отрезков.
2. Кратко о исключениях и как их бросать.
3. Когда и почему инвалидируются итераторы.
4. Что значит спецификатор const для методов функций.

максимальный по сумме подмассив (упражнение, 10 мая)

Дан массив целых чисел (положительных и отрицательных). Предложите структуру, позволяющую находить максимальный по сумме подмассив внутри указанной части исходного массива. Сложность O(log N), где N - размер массива.

Re: Адаптируйте дерво отрезков для этих целей.

Ближайший общий предок (упражнение, 10 мая)

Дано бинарное дерево поиска. Предложите структуру, которая за O(log N) действий позволяет найти ближайшего общего предка для двух узлов. N - количество узлов в дереве.

Re: Попробуйте предобработать дерево, построив дерево отрезков во время обхода (сложность O(n)).

Семинар A04.21

Продолжили разговор о деревьях поиска.

Рассмотренные вопросы

1. Сравнение деревьев бинарного поиска и хешей (краткий ответ можно найти здесь).
2. Обходы деревьев (почитать можно здесь).
3. Оценка сложности работы деревьев.

Ссылки для дополнительного чтения

1. АВЛ-дерево.
2. Расширяющееся дерево (описаны только в 2м издании Кормена).
3. B-дерево (хорошо описаны в Кормене).
4. Случайные деревья (тема раскрыта в Кормене).

Семинар A04.19

Поговорили о бинарных деревьях поиска, кратку справку можно получить здесь.

Какие операции надо знать

1. Вставка, удаление.
2. Поиск по ключу
3. Поиск минимального/максимального ключа.
4. Поиск предыдущего/последующего ключа.

Ссылки для чтения

1. Return value optimization.
2. Умные указатели: unique, shared и weak.

Семинар A04.14

Занятия не было.

Семинар A03.14

Занятия не было.

Программа для робота

Наш робот стоит в клетке A квадратного поля. На каких-то клетка стоят ящики и поэтому робот не может на них встать. Напишите для робота программу, которая строила бы оптимальный путь до каждой доступной клетки.

Re: Используйте поиск в ширину.

Компоненты связаности

Предложите алгоритм, который подсчитывает число компонент связаности. А как вывести номера вершин для каждой компоненты?

Re: Используйте поиск в глубину.

Задачка от Смбата

Есть некоторый граф и указаны две вершины A и B. Предложите алгоритм, который выводит все ребра, через которые проходит хотя бы один оптимальный путь из A в В. Граф не ориентированный.

Re: Используйте поиск в ширину.

Двудольный граф

Проверить, является ли предложенный граф двудольным.

Re: Используйте поиск в ширину.

Диаметр (упражнение, 15 марта, 9:00)

Предложите алгоритм, находящий диаметр неориентированного графа.

Предок (упражнение, 15 марта, 9:00)

Дано бинарное дерево поиска. Предложите алгоритм, который за O(1) позволяет ответить, является ли вершина A предком для вершины B.

Re: На предобработку дерева допускается использовать O(|E| + |V|).

Семинар A03.03

Хранение графов (Упражнения)

1. Граф хранится в виде списков смежности. Сколько нужно действий, чтобы узнать количество исходящих ребер из вершины? А входящих?
2. Что произойдет с матрицей смежности ориентированного графа, если обратить все ребра. Как обратить ребра, если используется список смежности? Какое количество операций требуется?
3. Покажите, что O(|V|) с помощью матрицы смежности можно обнаружить вершину, из которой не исходит ни одного ребра, но при этом есть ребра из все оставшихся вершин в нее.

Семинар A03.01

1. Поговорили про реализацию сложения в длинной арифметике.
2. Поговорили о ключевом слове explicit и преобразовании типов. Подробнее об этом здесь.
3. Поговорили о том, как графы хранятся в памяти, прочитать можно здесь.

Семинар A02.25

1. Провели защиту решений из контеста H1, примеры реализации можно посмотреть здесь.
2. Поговорили о типах динамики.

Семинар A02.18

Разобрали теоретическую часть H1.

Максимальная неунывающая подпоследовательность

Дан массив целых чисел. Помогите неунывающей студентке Ане найти длину максимальной неубывающей подпоследовательности. К примеру, для набора [1 2 3 1 4] это будет [1 2 3 4], а для [0 2 0 2 0 2] есть несколько вариантов [0 0 0 2], [0 0 2 2], [ 0 2 2 2]. Вам же нужно вывести только длину.

Задача о порядке перемножения матриц

Дана последовательность матриц, которую нужно перемножить, A · B · ... · C. Требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению.

Задача о монетках (Упражнение, 1 марта, 9:00)

Вам предлагается решить познакомиться с ресурсом hackerrank и решить следующую задачу.

Семинар A02.16

Разобрали теоретическую часть H1.

Семинар A02.11

Рассмотрели следующие темы:

1. Алгоритм нахождения k-й статистики за O(n) в среднем.
2. Алгоритм нахождения k-й статистики с гарантированной сложностью O(n).
3. Алгоритм нахождения двух ближайших точек на плоскости за O(n log n).

Медианы и квантили

В математической статистике часто необходимо вычислить медиану для случайной величины или квантиль. Для этого удобно применять k-статистики. В частности для n реализаций некоторой случайной величины для фиксированного p можно найти x, что P[X < x] = p, как значение [pn] статистики.

Треугольник с минимальным периметром

Среди заданного множества точек выбрать три различных точки так, чтобы сумма попарных расстояний между ними была наименьшей.

Re: Задача поиска пары ближайших точек может быть сведена к задаче о треугольнике с минимальным периметром. Подробное решение можно найти здесь.

Минимальная сумма

Вам задан набор из n векторов на плоскости. Для каждого вектора разрешается домножить любые его координаты на -1. Вам нужно найти два вектора из набора и определить, какие из их координат следует умножить на -1 таким образом, чтобы модуль суммы полученных векторов был минимально возможным. Более подробное условие можно найти здесь.

Re: Минимальная сумма для произвольных двух векторов (x1, y1) и (x2, y2) может быть получена следующим образом (|x1| - |x2|, |y1| - |y2|). А дальше задача сводится к поиска ближайших двух точек.

n-th element (упражнение, 25 февраля)

Реализуйте линейный алгоритм нахождения n-й статистики.

Re: Допускается реализация алгоритма работающего за O(n) в среднем. В стандартной библиотеке есть схожий алгоритм. Изучите следующий материал.

3 vs 7 (упражнение*, 25 февраля)

Можно ли в алгоритме, находящем, n-й элемент с гарантированной линейной сложность вместо 5-ок объектов использовать 3-ки? А 7-ки? Ответ обоснуйте.

Re: Для решения воспользуйтесь доказательством сложности алгоритма из книги Кормана.

Ближайшие точки (упражнение, 25 февраля)

Реализуйте алгоритм нахождения двух ближайших точек на плоскости.

Re: Изучите следующий материал.

Семинар A02.04

Рассмотрели следующие методы решения рекуррентных соотношений:

1. Индукция
2. Раскрытие суммы
3. Рекурсивное дерево
4. Основная теорема.

Binary search (упражнение, 11 февраля)

В качестве тренировки предлагаю вам для бинарного поиска проделать все то же самое, что мы делали на семинаре для merge sort:

1. Получить рекуррентную зависимость и применить основную теорему.
2. Доказать оценку по индукции
3. Раскрыть через сумму
4. Доказать через дерево рекурсии.

Семинар A02.02

1. Провели контрольную работу, разбор можно найти здесь.
2. Порешали задачи на рекуррентные зависимости.

Семинар A01.28

1. Поговорили о том, что значит оценки сложности в жизни.
2. Разобрали сортировку подсчетом и разрядную сортировку.
3. Начали осваивать рекуррентные соотношения.

Radix sort (упражнение, 4 февраля)

Реализуйте поразрядную сортировку для 64-битных чисел, один разряд -- это один байт (для этого вам придется реализовать сортировку подсчетом).

Re: Реализация только сортировки подсчетом стоит 1 балл.

Семинар A01.26

1. Немного поговорили о задаче внешней сортировки.
2. Разобрали упражнения на о-нотацию.
3. Посмотрели примеры использования сортировок.

Равные массивы

Дано два массива чисел размера n, определить, являются ли эти массивы одинаковыми с точностью до перестановки элементов.

Re: Отсортируем массивы, теперь для проверки достаточно пройтись параллельно по обоим массивам, проверяя, что соответствующие элементы совпадают. Сложность алгоритма n log n. Эта идея используется, к примеру, здесь.

Уникальные элементы

Дан массив чисел длины n, как проверить, что все ли элементы в массиве уникальны?

Re: Отсортируем массив, теперь для проверки достаточно пройтись по массиву, проверяя, равны ли соседние элементы. Сложность алгоритма n log n. Эта идея используется, к примеру, здесь.

Разбиение на пары

Дан массив чисел размера 2n, как определить, можно ли разбить массив чисел на пары, которые дают сумму 1997.

Re: Отсортируем массив, теперь достаточно проверить, что для всех k < n выполняется a[k] + a[2n - k - 1] = 1997. Сложность алгоримат n log n.

Площадь наложения

На числовой прямой окрасили n отрезков. Известны координаты левого и правого концов каждого отрезка (целые числа). Найти длину окрашенной части числовой прямой.

Re: Отсортируем концы отрезков (2n штука) по координатам, если координаты совпадают, то левый конец больше правого. Теперь за одни проход концов можно вычислить закрашенную площадь. Для этого достаточно завести счетчик, указывающий количество отрезков, накрывающих следующий сегмент, и поддерживать его состояние. Сложность алгоримат n log n.

Задачи на О-нотацию (упражнение, 2 февраля)

Листочек с упражнениями можно найти здесь, на семинаре (A01.28) можно будет задавать по нему вопросы.

Семинар A01.21

1. Закончили разбор сортировки in-place merge
2. Поговорили о quick sort, особое внимание уделили выбору опорного элемента.
3. Начали говорить о О-символике

В чем разница между O(f) и o(f)

Материал доступен здесь.

Quick sort (упражнение, 28 января)

Реализуйте сортировку qiuck sort.

Re: В качестве решения приведена комбинация quick sort и insertion sort. Замеры производительности можно посмотреть здесь.

Семинар A01.19

1. Insert sort
2. Merge sort
3. in-place merge sort

Insertion sort

Реализуйте сортировку вставками.

External sorting (упражнение, 26 января)

У студента Никиты есть компьютер, оперативная память которого может хранить M чисел и имеет небольшой буфер. На диске у этого компьютера хранится массив размером 100M чисел и имеется еще куча свободного места. Предложите Никите алгоритм, с помощью которого он мог бы отсортировать свой массив.

Re: Подумайте, какие известные сортировки вы можете применить.

Merge sort (упражнение, 28 января)

Реализуйте сортировку слиянием.

Re: Для зачета вы должны пройти все тесты в контесте. За задачу вы получите два плюсика, реализовав функцию merge и функцию merge_sort. Код семинаристу стоит присылать только после того, как пройдены все тесты. Сначала присылайте первую задача, а затем уже саму сортировку.

In-place merge sort (упражнение, 28 января)

Студентка Таня очень любит читать Хабр. В одном из постов она натолкнулся на описание алгоритма, который позволяет применять сортировку слиянием без использования дополнительной памяти. Помогите Тане оценить сложность работы алгоритма.

Re: Задача стоит 2 плюсика.

Семинар A01.14

1. Множественная и одиночная рекурсии.
2. Стек и куча.
3. Мемоизация.
4. Хвостовая рекурсия.
5. Особенности реализации рекурсий.
6. Принцип разделяй и властвуй.
7. Бинарный поиск.

01 строки

Предложить рекурсивный алгоритм, выводящий всевозможные строки длины n из 0 и 1 в лексикографическом порядке.

Re: В решении продемонстрированы все основные особенности реализации рекурсивных функций.

Бинарный поиск

Предложить рекурсивный алгоритм, производящий бинарный поиск элемента в отсортированном массиве.

Re: Метод олицетворят подход разделяй и властвуй. В качестве примера приведена рекурсивная реализация на шаблонах, хотя это не оптимальный подход.

Ханойская башня - 1

Предложить рекурсивную функцию, печатающую последовательность перемещений (в формате (x, y), где x и y — номера стержней, с которого и на который перемещается диск), являющуюся решением задачи о Ханойской башне.

Алгоритм Евклида (упражнение)

Реализовать рекурсивную версию алгоритма Евклида для нахождения наибольшего общего делителя.

Re: При правильном решении вы должны получить хвостовую рекурсию.

Ханойская башня - 2 (упражнение)

Реализовать рекурсивную функцию, получающую на вход число дисков Ханойской башни и выводящую состояние башень после каждого перемещения в оптимальном решении. Пример, n = 3, все диски на первом стержне:

1. [3, 2, 1]
2. []
3. []

Состояние после перемещения верхнего диска на 3 стержень:

1. [3, 2]
2. []
3. [1]

Re: Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью вектора.

Семинар A01.12

1. Знакомство с группой.
2. Рассмотрение примеров использования рекурсии.

Факториал

Предложить рекурсивный вариант вычисления факториала.

Re: Очевидно, что предложенная рекурсивная реализация факториала не является хвостовой рекурсией, однако существует итерационная версия алгоритма. Поэтому наличие хвостовой рекурсии является достаточным, но не обходимым условием наличия итерационного алгоритма с использованием константной памяти.

Фибоначчи

Предложить рекурсивный вариант вычисления чисел Фибоначчи.

Re: Показан пример сведения множественной рекурсии к одиночной.

Степень

Предложить рекурсивный алгоритм вычисления неотрицательной степени числа.

Разворот списка (упражнение)

Реализовать рекурсивную функцию reverse, которая обращает связи односвязанного списка в противоположную сторону. Таким образом последний элемент списка становится первым, предпоследний вторым, и т.д. Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1].

Re: Кстати, кроме рекурсивных функций принято еще выделять и рекурсивные структуры данных, к примеру списки и деревья.