Алгоритмы и структуры данных. Подгруппы 102-1, 102-2, 107-2

Общая информация

Семинары ведет Умнов Алексей

Часы консультаций:

• Понедельник: 15:45 - 16:30
• Среда: 18:15 - 19:00

Место: ауд. 619.

Не забывайте писать тесты к задачам (как обсуждалось на семинарах) и указывать версию компилятора/интерпретатора.

Стиль кода

Код должен соответствовать стайлгайду, принятому на курсе Основы_и_методологии_программирования.

Также есть дополнительные правила:

• Запрещено использовать глобальные переменные.
• Весь содержательный (с точки зрения алгоритмов) код нужно выносить в отдельные функции. В функции main (или в глобальном пространстве имен для питона) можно только считывать и печатать данные, делать преобразования их формата и вызывать содержательные функции.

Тестирование программ

Для тестирования своих программ перед отправкой в контест можно пользоваться программой.

Как работать с программой и как писать хорошие тесты.

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

Правила ревью

Алгоритм сдачи задачи такой:

1. Сдайте задачу в контест.

2. Отправьте исходный код (в точности тот, что был в контесте) на ревью с помощью rb.cs.hse.ru.

В заголовке ревью (Summary) напишите "Дз<номер>.<буква/номер задачи> <подгруппа> <Фамилия Имя>", например "Дз1.A 123-1 Умнов Алексей". Ревьювером укажите "alexeyum". В поле Description можно написать что угодно.

Не забудьте нажать "Publish", чтобы отправить запрос на ревью.

3. Дождитесь ответа на ревью. Если ответа нет в течение 5 дней, то пишите об этом на alexeyum@gmail.com.

4. Если вы получили "Ship It", значит задача сдана. Если нет, то необходимо сделать все указанные в ревью исправления.

5. Сдайте исправленный код в контест, а потом загрузите его на ревью. Перейдите к шагу 3.

6. Когда задача сдана и вопросов больше нет, нужно закрыть ревью ("Close" в правом верхнем углу).

Для ревью открыли новый контест. Новые задачи туда сдавать нельзя.

Если вы ни разу не заходили на rb.cs.hse.ru, то нужно использовать логин из контеста и следующий пароль: "BEdp84laNx". После входа нужно сразу же поменять пароль на новый.

Задание 1

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

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду, принятому на курсе Основы_и_методологии_программирования.

За каждую задачу в задании можно получить до 10/6 баллов. Для этого нужно сдать решение в контест и пройти полное ревью. Если ревью пройдено частично, то за задачу будет начислен неполный балл.

Итоговая сумма будет округляться вверх.

Ревью нужно прислать не позже 19.02 и сделать все исправления в течение недели с первого ответа. Если у вас неверно работает задача F (после добавления новых тестов), то ее нужно исправить до 22.02.

Задание 2

Для допуска к этому заданию необходимо

• сдать одну задачу в контест и пройти ревью.
• на семинаре сдать задачу про сильную связность

Контест.

Если вы пишите программы на питоне, то может быть удобным воспользоваться функцией setrecursionlimit из модуля sys для установки максимально допустимой глубины рекурсии. По умолчанию она довольно маленькая для этих задач и может привести к ошибкам.

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

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

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду.

Ревью по этому домашнему заданию будет проходить по почте, без использования rb.cs.hse.ru. (Если вы уже прислали задачу на rb.cs.hse.ru, то ничего страшного, проверим через нее.)

При отправке задачи на ревью в теме письма пишите:

"АиСД - Дз<Номер дз>.<номер задачи> - <Подгруппа> <Фамилия> <Имя>".

Пример: "АиСД - Дз2.1 - 123-1 Умнов Алексей".

Для задачи на динамическое программирование пишите вместо номера задачи "ДП1" или "ДП2".

В письме укажите номер последней успешной посылки в контест и прикрепите файл с кодом этой посылки.

Письмо отправляйте на адрес вашего проверяющего. Распределение проверяющих.

За задание можно получить до 10 баллов, до 3 за задачи 1-* и 2-* и до 4 за задачу 4. Для получения полного балла по задаче нужно сдать задачу в контест и пройти ревью.

Задание 3

Контест.

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

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

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду.

При отправке задачи на ревью в теме письма пишите:

"АиСД - Дз Номер дз . номер задачи - Подгруппа Фамилия Имя".

Пример: "АиСД - Дз2.1 - 123-1 Умнов Алексей".

В письме укажите номер последней успешной посылки в контест и прикрепите файл с кодом этой посылки.

Письмо отправляйте на адрес вашего проверяющего. Распределение проверяющих.

За задание можно получить до 10 баллов, по 10/3 за каждую задачу (сумма округляется вверх). Для получения полного балла по задаче нужно сдать задачу в контест и пройти ревью.

Также для получения ненулевого балла за задачу 3 нужно сдать доказательство корректности алгоритма. Доказательство можно сдать устно на семинаре или прислать вместе с кодом на ревью в виде файла в формате .txt или .pdf.

Задание 4

Контест.

Срок ревью задания - начало сессии (около 13 июня).

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду.

При отправке задачи на ревью в теме письма пишите:

"АиСД - Дз Номер дз . номер задачи - Подгруппа Фамилия Имя".

Пример: "АиСД - Дз4.1 - 123-1 Умнов Алексей".

В письме укажите номер последней успешной посылки в контест и прикрепите файл с кодом этой посылки.

Письмо отправляйте на адрес вашего проверяющего. Распределение проверяющих.

За задание можно получить до 10 баллов, по 10/3 за каждую задачу из первых трех (сумма округляется вверх). Для получения полного балла по задаче нужно сдать задачу в контест и пройти ревью. За решение задачи 4 (в первой десятке) засчитывается любая задача на 100%.

Задание 5

Контест и задачи.

За каждую задачу можно получить до 2.5 баллов. Задачи на программирование необходимо сдать в контест и прислать на ревью. Будет проводится всего одна итерация ревью, то есть оценка будет выставляться сразу же в зависимости от того, насколько хорошо написан код. Решения теоретических задач необходимо сдать вашему проверяющему не позднее времени окончания контеста (уточнение: задачи можно сдавать до 25 июня включительно).

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду.

При отправке задачи на ревью в теме письма пишите:

"АиСД - Дз Номер дз - номер задачи - Подгруппа Фамилия Имя".

Пример: "АиСД - Дз5 - 1 - 123-1 Умнов Алексей".

В письме укажите номер последней успешной посылки в контест и прикрепите файл с кодом этой посылки.

Письмо отправляйте на адрес вашего проверяющего. Распределение проверяющих.

Семинары

Решения задач с семинаров

Код для задач по программированию можно присылать на адрес alexeyum@gmail.com.

Тему письма оформляйте по такому шаблону (иначе письмо может потеряться):

"АиСД - <Номер семинара>.<номер задачи> - <Подгруппа> <Фамилия> <Имя>".

Пример: "АиСД - 2.1 - 123-1 Умнов Алексей".

Семинар 0 (12.01). Ханойские башни.

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

Семинар 1 (14.01 и 15.01). Сортировка слиянием.

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

Семинар 2 (19.01). Двоичный поиск. O-символика.

Разбирались O-обозначения, были предложены задачи.

Семинар 3 (21.01 и 22.01). O-символика. Разные задачи

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

Семинар 4 (26.01). Рекуррентные соотношения

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

Семинар 5 (28.01 и 29.01).

Разбирались задачи с прошлых семинаров.

Семинар 6 (02.02)

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

Семинар 7 (04.02 и 05.02). Динамическое программирование.

Разбиралась задача о взвешенных интервалах и были предложены задачи.

Семинар 8 (09.02). Динамическое программирование 2.

Были предложены задачи.

Семинар 9 (11.02 и 12.02).

Было подробно разобрано тестирование программ и несколько старых задач.

Контест с заданиями для допуска (нужно решить хотя бы одну задачу).

Семинар 10 (16.02)

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

Семинар 11 (18.02 и 19.02)

Разбирался алгоритм поиска в ширину, алгоритмы проверки связности.

Новое задание для допуска к домашнему заданию: написать программу, выполняющую проверку, является ли данный ориентированный граф связным. Задачу нужно сдать на семинаре.

Задачи семинара: ссылка.

Семинар 12 (26.02 и 27.02)

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

Семинар 13 (02.03)

Разбирали алгоритм поиска компонент сильной связности в ориентированном графе и алгоритм Беллмана-Форда.

Семинар 14 (04.03 и 05.03)

Разбирали алгоритм Флойда-Уоршелла. Были предложены задачи.

Семинар 15 (07.03)

Жадные алгоритмы. Были предложены задачи.

Семинар 16 (11.03 и 12.03)

Разбирали 3 задачу из домашнего задания и алгоритм Дейкстры.

Семинар 17 (16.03)

Решали задачи на основе алгоритма Дейкстры. Задачи

Семинар 18 (18.03 и 19.03)

Разбирали амортизационный анализ, решали задачи.

Семинар 19 (30.03)

Разбирали двоичные и d-ичные кучи. Задачи.

Примерный вариант контрольной: задачи.

Семинар 20 (01.04 и 02.04)

Разбирали минимальные покрывающие деревья, алгоритмы Крускала и Прима. Задачи.

Семинар 21 (06.04)

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

Семинар 22 (08.04 и 09.04)

Разбирали структуру данных "Система непересекающихся множеств" и решали еще задачи на минимальные остовные деревья.

Семинар 23 (15.04 и 16.04)

Разбирали задачи с контрольной работы.

Семинар 24 (20.04)

Разбирали потоки в сетях, алгоритмы Форда-Фалкерсона и Эдмондса – Карпа. Задачи.

Семинар 25 (22.04 и 23.04)

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

Семинар 26 (27.04)

Разбирали задачу о максимальном паросочетании в двудольном графе. Задачи.

Семинар 27 (29.04 и 30.04)

Разбирали хеш-таблицы.

Семинар 28 (11.05)

Разбирали двоичные деревья поиска. Задачи

Семинар 30 (18.05)

Разбирали конечные автоматы и регулярные языки.

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

Семинар 31 (20.05 и 21.05)

Разбирали лемму о накачке и регулярные выражения. Задачи.

Семинар 32 (25.05)

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

Задачи. Напишите регулярные выражения для: 1) email-адресов, 2) дат, 3) IP-адресов.

Семинар 33 (27.05 и 28.05)

Решали задачи про регулярные языки. Задачи.

Семинар 34 (01.06)

Разбирали задачи из семейств P и NP и сведения. Решали задачи.

Семинары 35 и 36 (03.06, 04.06, 08.06)

Повторяли ранее пройденные темы. Задачи.

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