Алгоритмы и структуры данных семинары 154-2 156-2 — различия между версиями

Версия 18:16, 25 апреля 2016

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

Все домашки сдаются на ревью в AnyTask (anytask.org), для получения доступа нужно ввести инвайт в соответствии с группой:

Инвайт на AnyTask для 154-2: b002kz4 (действителен до 25 мая)

Инвайт на AnyTask для 156-2: MXyU2zi (действителен до 25 мая)

Все оценки и варианты заданий можно найти тут.

Семинары

Семинар 1

Тренировались в рекурсии на примере Ханойских башен. Задачи, нужно решить все, кроме 4.

Семинар 2

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

Задачи:

• Доказать корректность работы сортировки пузырьком.
• Написать двоичный поиск с тестами как в примере выше. При этом функция должна быть реализована максимально абстрактно на шаблонах. После написания тестов и полной отладки задачу нужно сдать сюда. А потом еще и сдать задачу устно.

Семинар 3

Обсуждали разные сортировки (вставками, слиянием, быструю). Их нужно сдать в контест.

Семинар 4

Обсуждали асимптотики и O-символику. Начали решать листок.

Cеминары 5-6

Дорешивали старые задачи.

Семинары 7-8

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

Начали решать листок по рекуррентам.

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

Семинары 9-10

Дорешивали старые задачи.

Семинары 11-12

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

Семинары 13-14

Обсуждали редакционное расстояние. Его нужно запрограммировать здесь.

Обсуждали обход в ширину и в глубину на графах. Решали контест на обход в глубину и контест на обход в ширину.

Семинары 15-16

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

Семинары 17-20

Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. Начали решать контест на кратчайшие пути.

Также доступно несколько контестов по старым темам для тренировки: контест подсчет количества путей и контест на стратегию "разделяй и властвуй".

Семинары 21-22

Обсуждали хеширование.

Писали контрольную работу. Задачи, которые вы не решили на контрольной можно будет сдать на следующем семинаре (на нем же будет разбор).

Семинары 23-24

Разбирали контрольную работу. Обсуждали красно-черные деревья.

Семинары 25-26

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

Если вы не писали к/р 2 или написали ее на 5 баллов или ниже, можете ее пересдать на консультациях с ассистентом. Условия. За каждую задачу ставится 1.5 балла.

Семинары 27-28

Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию.