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

Примерный план семинаров

1. Основы проектирования и написание интерфейсов
2. Тестирование программ
3. Сортировки и гарантированный n log n для qsort
4. Метод ветвей и границ и общее понятие метрики качества
5. Быстрое преобразование Фурье
6. Динамическое программирование
7. Контекстно-свободные грамматики
8. Симплекс-метод
9. Потоки, динамические деревья, splay-деревья
10. Хеширование
11. Жадные алгоритмы
12. Вероятностные алгоритмы
13. Конечные автоматы
14. Компиляторы

Введение

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

1. Работать с системой контроля версий
2. Писать тесты к вашим программам

Очередность сдачи задач

1. Алгоритм, обоснование корректности, оценки времени и памяти на почту finisterra@yandex.ru
2. Сдача задачи в Яндекс.Контест
3. Правка интерфейса по результатам ревью
4. Правка кода по результатам ревью

Теория

Теорию необходимо отправлять в pdf, учитесь пользоваться ТеХом.

Яндекс.Контест

Контест доступен по адресу
https://official.contest.yandex.ru/contest/1005/

Репозиторий

Наш проект на code.google.com живет тут
https://code.google.com/p/1011-group-trunk/
Для работы с ним требуется аккаунт Google.

Посмотреть пароль к системе code.google.com можно на странице
https://code.google.com/hosting/settings

Репозиторий доступен по адресу
svn checkout https://1011-group-trunk.googlecode.com/svn/trunk/ 1011-group-trunk --username username --password password
Где вместо username надо подставить имя вашего аккаунта, а вместо password - пароль от системы code.google.com

Первое домашнее задание

Сроки проведения: с 26 января по 9 февраля.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1002/
Сдача задач состоит из двух этапов: решения задачи в системе и прохождения ревью.
Сдавать задачи надо в контест в системе Яндекс.Контест, а ревью проходится с помощью code.google.com.

Второе домашнее задание

Сроки проведения: с 17:00 24 февраля по 23:59 9 марта.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1085/
Вновь половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.
Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!

Всего решить надо три задачи: 1-2 (количество путей), 2-2 (maze) и 3 (segments).

Третье домашнее задание

Сроки проведения: с 23:00 19 апреля по 23:00 4 мая.
Сроки сдачи ревью: c 23:00 4 мая по 23:00 23 мая.
Ваш номер варианта - это номер в алфавите третьей буквы вашей фамилии, взятый по модулю два и увеличенный на 1. Например, у меня фамилия меЛьничук - 13-я буква, значит, у меня второй вариант.
Третью задачу необходимо снабдить доказательством корректности алгоритма. Коммитить его надо вместе с кодом в svn.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1196/enter/
Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.

Четвертое домашнее задание

Сроки проведения: с 21:00 26 мая по 21:00 9 июня.
Сроки сдачи ревью: с 21:00 9 июня по 21:00 23 июня (конец может поменяться из-за сессии и требований учебной части, так что проходите поскорее).
Обязательны первые три задачи. Первые 10 человек, решившие 4-ую задачу, могут не решать одну из первых трех.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1259/enter/
Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.

Пятое домашнее задание

Сроки проведения: с 00:00 5 июня по 00:00 25 июня.
Обязательны обе задачи.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1271/enter/
Ревью по этой работе не проводится, но я надеюсь, что читаемый код вам писать уже проще, чем олимпиадный.
Вместо ревью вам необходимо решить и сдать набор теоретических задач
https://yadi.sk/i/G3lLFT65h9pb8

Текущие результаты

	Фамилия	Имя	Отчество	ДЗ-1	ДЗ-2	ДЗ-3	ДЗ-4	ДЗ-5	Accum	Exam	Sum
1	Гущенко-Чеверда	Иван	Ильич	6/6	3/3	4/4	1/3
2	Деркач	Денис	Анатольевич	5/6	3/3	4/4	2/3
3	Исхаков	Тимур	Рашидович	6/6	3/3	3/4	2/3
4	Кузнецов	Георгий	Алексеевич	6/6	2/3	2/4 без ревью
5	Мельниченко	Пётр	Валерьевич	4/6 без ревью		2/4
6	Носков	Степан	Алексеевич	6/6 без ревью	3/3 без ревью	3/4 без ревью	1/3 без ревью
7	Пособин	Глеб	Игоревич	6/6	3/3	4/4	3/3
8	Пролеев	Лев	Николаевич	6/6	3/3	4/4	3/3
9	Рябушев	Антон	Федорович	6/6	3/3 без ревью	3/4 без ревью	1/3 без ревью
10	Сайранов	Айдар	Дамирович	6/6 без ревью	3/3 без ревью	4/4
11	Святокум	Полина	Олеговна	6/6	3/3	3/4	2/3 без ревью
12	Султанов	Арсен	Русланович	6/6 без ревью		1/4 без ревью	1/3
13	Трофимов	Иван	Андреевич	6/6 без ревью		3/4 без ревью	2/3 без ревью

Результаты контрольной

	Фамилия	Имя	Отчество	1	2	3	4	5
1	Гущенко-Чеверда	Иван	Ильич	+	+	+	+	+
2	Деркач	Денис	Анатольевич	-	+	+-	+	+
3	Исхаков	Тимур	Рашидович	+	-	+	+	+
4	Кузнецов	Георгий	Алексеевич	-	-	-	+	+-
5	Мельниченко	Пётр	Валерьевич	+	+	+	+	-
6	Носков	Степан	Алексеевич	-	+	+	+
7	Пособин	Глеб	Игоревич	+	+	+	+	+
8	Пролеев	Лев	Николаевич	+	+	+	+	+-
9	Рябушев	Антон	Федорович	-	+	+	+
10	Сайранов	Айдар	Дамирович	+	+	+	+	+
11	Святокум	Полина	Олеговна	+	+	+	+
12	Султанов	Арсен	Русланович
13	Трофимов	Иван	Андреевич	+	+-	+-	+	+

Если видите какие-то ошибки в заполнении таблицы, сообщайте, я мог что-то упустить.

Набор задач для подготовки к контрольной

https://yadi.sk/i/gVo0ymT4fduLJ

Текущие наработки по компилятору

https://yadi.sk/d/f-GdraEHgzcLD

Экзамен

Экзамен по курсу будет состоять из двух частей.

Первая часть - практическая и будет проходить на последнем семинаре по курсу.
Вам будет предложено решить одну задачу в системе Яндекс.Контест.
За эту часть экзамена вы получаете 2 из 10 баллов экзамена.
Тренировочный контест, настроенный так же, как и экзаменационный:
https://official.contest.yandex.ru/contest/1282/enter/
Контест практической части экзамена:
https://official.contest.yandex.ru/contest/1280/enter/

Вторая часть - теоретическая и будет проходить 29ого июня.
При подготовке можно пользоваться любыми бумажными материалами.
Электронными устройствами пользоваться запрещено.
Билет будет состоять из вопроса по теории и задачи.
Для получения максимальной оценки необходимо будет ответить на дополнительные вопросы.
За эту часть экзамена вы получаете 8 из 10 баллов экзамена.