Алгоритмы и структуры данных 1 2020/2021 Семинары 209-1

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Семинаристка: Катя Минеева

Занятия: Четверг 11:10 - 14:00, аудитория R608


Ассистент: Миша Виноградов

Часы приема задач:

Четверг 18:00

Суббота 16:00


Таблица с оценками

Форма обратной связи

Общая страница курса — 2 модуль

Общая страница курса — 4 модуль


Листки с задачами в 4 модуле


1 неделя. Поиск в глубину. Связность, компоненты связности, циклы, двудольность.

Оцениваемые задачи: 5, 6.

Дедлайн: четверг 22 апреля в 23:59.


2 неделя. Поиск в глубину продолжение: топсорт, мосты, точки сочленения. Поиск в ширину.

Оцениваемые задачи: 4, 6, 7.

Дедлайн: четверг 29 апреля в 23:59.


3 неделя. Дейкстра. Форд-Беллман, Флойд.

Оцениваемые задачи: 5, 8.

Дедлайн: четверг 29 апреля в 23:59.


4 неделя. Остовные деревья, DSU. Сбалансированные деревья поиска.

Оцениваемые задачи: нет.

Дедлайн: четверг 13 мая в 23:59.


5 неделя. Декартово дерево, LCA (наименьший общий предок).

Оцениваемые задачи: 1, 7.

Дедлайн: четверг 10 июня в 23:59.


6 неделя. -


7 неделя. Алгоритмы теории чисел. Комбинаторные объекты.

Оцениваемые задачи: покажите, что алгоритм Евклида работает за O(log(min(a, b))).

Дедлайн: четверг 10 июня в 23:59.

Оценка за семинары в 4 модуле


(UPD: для удобства прежние баллы за тесты и оцениваемые задачи были домножены на 4 — сейчас это 4 и 8 баллов соответственно)

Баллы за семинар можно получить двумя способами:

  1. Устная сдача оцениваемых задач ассистенту. Каждую неделю такие задачи будут выдаваться из семинарского листка. По умолчанию такие задачи стоят 8 баллов, если другое не оговорено отдельно. Дедлайн по ним до 23:59 четверга следующего за тем, когда были выданы задачи.

  2. Короткие тесты на семинарах. Это несколько несложных вопросов. Не на идею, а на какое-то базовое понимание материала. Полностью правильно написанный тест стоит 4 балла.

O {семинары} = min(10, <баллы в пунктах 1 и 2> / (0.6 * <максимальное число баллов в пункте 1>)

То есть на 10 нужно решить 60% оцениваемых задач или меньше, если есть баллы за тесты.


Листки с задачами во 2 модуле


1 неделя. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка слиянием.

Оцениваемые задачи: Задача 1 (пункты 4, 5, 6), Задача 2, Задача 3 (пункт 2), Задача 11.

Дедлайн: вс 8 ноября 23:59.


Неделя 2. Амортизационный анализ, квадратичные сортировки, двоичная куча, быстрая сортировка, порядковые статистики.

Оцениваемые задачи: 1 (см. комментарий в чате), 4 (сложность операций — логарифм), 9, 13с, 14.

Дедлайн: пн 16 ноября 23:59.


Неделя 3. Сортировка подсчётом. Цифровая сортировка. Двоичный поиск.

Оцениваемые задачи: 2, 4 (все числа от 0 до n, время работы линейное. в алгоритме верните ответ по модулю 10^10 — это нужно, чтобы не думать про длинную арифметику; если этот комментарий вас смущает, то игнорируйте его во время решения и обсудите с примнимающим), 11 (предподсчёт за линейное время), 13.

Дедлайн: пн 23 ноября 23:59.


Неделя 4. Биномиальные кучи, фиббоначиевы кучи.

Оцениваемые задачи: 3, 8, 9, 10.

Дедлайн: пн 30 ноября 23:59.


Неделя 5. Динамическое программирование.

Оцениваемые задачи: 2, 4, 7, 10, 13.

Дедлайн: пн 7 декабря 23:59.


Неделя 6

Оцениваемые задачи: Нет.


Неделя 7

Оцениваемые задачи: 7, 11, 12.

Дедлайн: пн 21 декабря 23:59.


Неделя 8. Дерево отрезков.

Оцениваемые задачи: 1. 4 — бонусная. За решение бонусной задачи дается +2 балла к сумме баллов за ДЗ, но в знаменателе (числе обязательных задач) она учитываться не будет.

Дедлайн: пн 21 декабря 23:59.


Оценка за семинары во 2 модуле


Внимание: в течение первых двух недель правила выставления семинарской оценки могут незначительно измениться.

Каждую неделю будет выдаваться листок с задачами. Часть из них будут разбираться на семинаре, несколько задач из каждого листка будут выделены для индвидуальной устной сдачи — назовем их оцениваемыми задачами. Сдавать задачи можно только устно семинаристке (на парах в выделенное под это время) или ассистенту (в приемные часы). Необходимые для сдачи задачи записи (выкладки / рисунки) просьба делать заранее. Подробно записывать решение не обязательно.

Дедлайн по оцениваемым задачам: 23:59 понедельника недели следующей за той, когда был выдан листок. То есть по оцениваемым задачам недели 2 дедлайн будет 16 ноября в 23:59. Реально дедлайн будет раньше, поскольку часы сдачи оцениваемых задач ограничиваются семинарами и приемными часами ассистента.

O {семинары} = 10 * <число сданных оцениваемых задач> / <общее число оцениваемых задач>

Округление арифметическое.