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

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

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

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

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

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

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

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

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

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

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

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

Стиль кода

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

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

• Запрещено использовать глобальные переменные.
• Весь содержательный (с точки зрения алгоритмов) код нужно выносить в отдельные функции. В функции 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 баллов. Для этого нужно сдать решение в контест и пройти полное ревью. Если ревью пройдено частично, то за задачу будет начислен неполный балл.

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

Занятия

Семинар 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).

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

Инструкция к использованию:

Создайте папку с тестами для вашей программы. Каждый тест - это пара файлов X.in со входными данными и X.out с правильным ответом (X - название теста). После этого запустите программу со следующими аргументами:

$ check.py <программа и аргументы> -d <папка с тестами>

Например:

$ check.py python myprog/main.py -d myprog/tests/

Дополнительную информацию можно получить, вызвав программу с аргументом -h:

$ check.py -h

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

Семинар 10 (16.02)

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

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

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

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

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