Версия 01:20, 20 января 2015

Общие лекторы

Лектор #1 - Куликов Александр

Лектор #2 - Копелиович Сергей

Физики

Практика - Фондаратов Валентин, Служаев Евгений (evgentu@gmail.com)

Домашние задачи по практике. Группа Служаева

• 16 Cентября Линейные алгоритмы
• 23 Cентября Сортировки и бинарный поиск + дз
• 30 Cентября Сортировки и кучи + дз
• 7 Октября Динамическое программирование + дз
• 21 Октября Домашнее задание по динамическому программированию
• 28 Октября Домашнее задание по динамическому программированию
• 18 Ноября Домашнее задание по dfs
• 2 Декабря Домашнее задание по кратчайшим путям в графах

Результаты

MIT

Практика - Копелиович Сергей (burunduk30@gmail.com), Опарин Всеволод

Деление на группы: <link>

Материалы курса в dropbox

Результаты сдачи практики

Отчетность по курсу

• Одна глава электронного конспекта в TeX. Дедлайн 2 недели.

• Общий теорэкзамен: базовые и продвинутые лекции.

• Допуск к экзамену: зачет по практической части курса.

• Практическая часть: каждую неделю получаете контест и теорзадачи. Нужно сдать хотя бы 100% группа Копелиовича, текущие результаты

• Реализация и тестирование одного из описанных алгоритмов. С codereview, c промежуточным дедлайном 2 недели и окончательным дедлайном 1 месяц. Выдача ДЗ персональная, старт синхронный.

Формат сдачи ДЗ

Дедлайны теорзадач: мягкий в вс. 01:00, далее стоимость уменьшается в 2 раза, жесткий в вс. 23:59.

Дедлайн контеста: в вс. в 23:59 (через 11 суток после начала).

Задачи контеста сдавать в систему.

Теорзадачи отсылать по email преподавателю группы. Тема письма должна содержать подстроку [AU].

Результаты и условия контестов

• 01 Сентября отбор условия

• 08 Сентября дз #2 условия

• 15 Сентября дз #3 условия

• 22 Сентября дз #4 условия

• 29 Сентября дз #5 условия

• 6 Октября дз #6 условия Бинпоиск и точки-экстремалы

• 13 Октября дз #7 условия Динамика

• 20 Октября дз #8 условия Больше динамики!

• 27 Октября дз #9 условия Динамика по подмножествам

• 10 ноября дз #10 условия Графы и DFS

• 17 ноября дз #11 условия DFS, DP, trees

• 24 ноября дз #12 условия Кратчайшие пути

• 1 декабря дз #13 условия MST и DSU

• 8 декабря дз #14 условия деревья

Персональные домашние задания

Таблица распределения персональных ДЗ по алгоритмам:

https://docs.google.com/spreadsheets/d/1V9HVo-wmDeF5w3gNBHCYjTFWzumBMsnmZR1d5h5ddRI/edit#gid=0

С персональным домашним заданием не должно быть проблем с теорией, с пониманием, как и что писать, нужно сесть и написать. Если есть пробелы в теории, вопросы по заданию, обращайтесь к Сергею Копелиовичу. До 15-го декабря 01:00 (ночь с вс на пн) нужно прислать первую версию. До 22-го декабря 01:00 (ночь с вс на пн) прислать готовую с вашей точки зрения версию, к которой я придерусь. Придирки нужно будет исправить до Нового Года. Для тех, кто делает учебные задачи выложен пример: http://acm.math.spbu.ru/~sk1/problems/sample.7z

Коммитить готовое ДЗ сюда: http://mit.spbau.ru/svn/algo14b/логин

Чтобы ДЗ проверили, нужно написать на почту Burunduk30@gmail.com письмо с просьбой проверить, в теме письма на забудьте подстроку [AU].

P.S. Пример использования svn:

• svn co http://mit.spbau.ru/svn/algo14b/kravchenko.jurij (создали себе копию)
• svn add <файлы> <папки> (добавили файлы у себя локально)
• svn ci -m "comment to this commit" (добавили изменения на сервер)
• После коммита можно писать на Burunduk30@gmail.com сообщения "проверьте меня"

Домашние задания по практике. Группа Копелиовича

• 02 Сентября Асимптотика Асимптотика

• 09 Cентября Суммы и циклы for, время работы

• 16 Cентября Линейные алгоритмы

• 23 Cентября Сортировки и кучи

• 30 Cентября Статистики и кучи

• 7 Октября Бинарный поиск и поиск экстремальных точек

• 14 Октября Динамика (ДЗ) Условие практики (было на паре)

• 21 Октября Динамика++

• 28 Октября Динамика по подмножествам

• 4 ноября -- день народного единства

• 11 ноября Графы: DFS

• 18 ноября DFS и динамика

• 25 ноября Кратчайшие пути

• 2 декабря MST и DSU

• 9 декабря MST и DSU

• 16 декабря Разные задачи

Домашние задания по практике. Группа Опарина

• Материалы и домашнее задание в одном файле (Копия в Dropbox-е)

• Результаты

Лекции: конспект и экзамен

Вопросы к экзамену:

Конспекты лекций, сделанные силами студентов:

• 2014-09-02-Intro.pdf  : общие слова, разбор вступительного теста
• 2014-09-09-DataStrucutre.pdf  : стек, дек, очередь, вектор с удвоением и без амортизации, хеш-таблица на списках, частичные суммы, бинарный поиск, аллокация памяти
• 2014-09-17-conspect.pdf  : нижняя оценка на сортировку, разбор выражений со стеком, преобразование операци: merge <-> add; get,build -> add; find -> delete, хеш-таблица с открытой адресацией
• 2014-09-23-Sorts-2.pdf  : квадратичные сортировки, radix sort, bucket sort, Kirkpatrick's sort, adaptive heap sort, историческая справка
• 2014-09-30-Heaps.pdf  : интерфейс "куча", k-heap, leftist heap, skew heap, merge O(logn) + build O(n) -> add O(1), bootstrapping [add O(1) + merge O(logn) -> merge O(1)]
• 2014-10-07-Heaps-And-Merge.pdf  : inplace stable merge, minmax heap, нижняя оценка на построение бинарной кучи, pairing heap
• 2014-10-14-Heaps.pdf  : доказательство оценки O(sqrt(n)) в pairing heap, биномиальные деревья и кучи, реклама кучи Фибоначчи
• 2014-10-21-DP.pdf  : задачи на диниамку: погрузка грузов на корабль за O(n^2) времени и O(n) памяти, кратчайший путь на гриде при перемещении по трём направлениям, наибольший по площади красный многоугольник
• 2014-10-21-Fib.pdf  : куча Фибоначчи -- полное описание и доказательство
• 2014-10-28-DP.pdf  : динамика по подмножествам: операции с множествами, старший/младший/число бит, vertex coloring за O(3^n), гамильтонов путь/цикл за O(2^n*n), set cover за O(2^m), is_independent за O(2^n)
• 2014-11-11-DFS.pdf  : мосты, точки сочленения, компоненты вершинной двусвязности, рёберной двусвязности, эйлеров путь/цикл
• 2014-11-18-graphs.pdf  : цикл Де Брюина, задача про ориентацию графа, два указателя: профессор с яйцами; обобщение метода с временем работы sqrt(n) на запрос; задача про точки на прямой (одна, две, k)
• 2014-11-25-bfs-upgraded.pdf  : поиск в ширину, алгоритм Dial-а, кратчайший путь за O(m + nsqrt(k)), O((m+n)logk), radix heap, реализация dijkstra за O(m + nlogk), двухуровневая radix heap
• 2014-12-02-DP-proof-SK.pdf  : доказательство корректности решения за O(n^2) для поиска k точек на прямой (часть от Серёжи Копелиовича)
• 2014-12-02-DP-proof-olga.pdf  : доказательство корректности решения за O(n^2) для поиска k точек на прямой (часть от Оли Черниковой)
• 2014-12-02-FB-and-DP-proof.pdf  : доказательство корректности решения за O(n^2) для поиска k точек на прямой, кратчайшие пути: историческая справка, Форд-Беллман, оптимизации к Форд-Беллман, поиск отрицательного цикла
• 2014-12-09-Goldberg.pdf  : алгоритм Гольдберга поиска кратчайшего пути за O(EsqrtVlogN)
• 2014-12-16-Karp.pdf  : поиск цикла минимального среднего веса: решение бинарным поиском, алгоритм Карпа за O(VE) с доказательством
• 2014-12-16-Yen-AStar.pdf  : алгоритм Йена поиска k-го кратчайшего пути, алгоритм $A^{*}$, оценка скорости работы в графах с неравенством треугольника