2017:2018 Autumn - Algocourse/info GitHub Wiki

Занятия проходят по субботам в аудитории В-115. Время: 12:00.

• Крайне рекомендуется на занятии иметь с собой ноутбук.

Занятие 12. 16 декабря 2017.

• Дополнение про динамику на битмасках. Перебор всех подмасок.
• Ахо-Корасик.

Задание:

• Тематический контест на e-olymp. Бор. Все задачи.
• Ахо-Корасик.
• Тренировочный контест.

Занятие 11. 9 декабря 2017.

• Динамика на битмасках.
• Задача коммивояжера.

Задание:

• Задачи с прошлого контеста на тему "Динамика по битмаскам".

Занятие 10. 2 декабря 2017.

• Бор (Trie).

Задание:

• Тематический контест на e-olymp. Бор. Задачи: A, C, D.

Занятие 9. 25 ноября 2017.

• Z-функция строки.
• Префикс функция строки.

Задание:

• Набор базовых задач на реализацию Префикс и Z функций.

Занятие 8. 18 ноября 2017.

• Бинарный поиск.
• Бинарный поиск по ответу.
• Бинарное возведение в степень числа/матрицы.
• Эффективное вычисление n-го числа Фибоначчи по модулю.
• Тернарный поиск.

Задание

• Бинарный поиск 1
• Бинарный поиск 2
• Бинарный поиск по ответу 1
• Реализовать вычисление последовательности Фибоначчи по модулю при помощи бинарного возведения матрицы в степень. Провести тесты, взяв в качестве базового решения подход на основе динамического программирования.
• Тернарный поиск.

Занятие 7. 11 ноября 2017.

• Бинарное дерево поиска.
• Динамическое программирование. Задача о рюкзаке.

Задание

• Задачи на тему "Бинарное дерево поиска".
• Задачи про рюкзак.

Занятие 6. 4 ноября 2017.

• Не будет проводиться в связи с праздником

Задание

• Тренировочный контест 2017-2018 №2.

Занятие 5. 27 октября 2017.

• Сортировки.
• Квадратичные сортировки. Сортировка вставками, пузырьком, выбором.
• Сортировка слиянием. Подсчёт количества инверсий.
• Быстрая сортировка.
• Сортировка подсчётом.
• Задача поиска ближайшего элемента слева (справа) меньше или равного текущего.

Задание:

• Контест на тему "Сортировки".

Занятие 4. 20 октября 2017.

• Список(List).
• Стек(Stack).
• Очередь(Queue).
• Очередь с поддержкой минимума.
• Бинарная куча.

Задание:

• Тренировочный контест 2017-2018 №1.
• Задачи на реализацию бинарной кучи.

Занятие 3. 13 октября 2017.

• Примеры двумерной динамики.
• Техника двух указателей.
• Поиск длины наибольшей общей подпоследовательности.

Задание:

• Контест на темы "Динамическое программирование" и "Два указателя".

Занятие 2. 29 сентября 2017.

• Основы асимптотического анализа. Примеры.
• Постановка задачи динамического программирования.
• Примеры одномерной динамики.
• Примеры задач, решаемых жадными алгоритмами.

Задание:

• Контест на темы "Динамическое программирование" и "Жадные алгоритмы".

Занятие 1. 22 сентября 2017.

• Вводная лекция.
• Структура курса.
• Полезные материалы.
• Ознакомление с С++.
• Пример решения задачи на языке С++.

Задание:

• Ознакомительный контест.