2018:2019 Autumn - Algocourse/info GitHub Wiki

Занятия проходят по субботам в аудитории В-416. Время: 16:15.

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

Занятие 12. 15 декабря 2018.

• Геометрия. Общие определения.
• Построение выпуклой оболочки.

Занятие 11. 8 декабря 2018.

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

Задание:

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

Занятие 10. 1 декабря 2018.

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

Задание:

• Задачи с прошлого контеста на тему "Динамика по битмаскам".
• Задачи на рюкзак.
• Тренировочный контест.

Занятие 9. 24 ноября 2018.

• Бор (Trie).

Задание:

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

Занятие 8. 17 ноября 2018.

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

Задание:

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

Занятие 7. 10 ноября 2018.

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

Задание

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

Занятие 6. 2 ноября 2018.

• Разбор некоторых задач из тренировочного контеста.
• Бинарное дерево поиска.
• Бинарная куча.

Задание

• Тренировочный контест.
• Задачи на тему "Бинарное дерево поиска".
• Задачи на реализацию бинарной кучи.

Занятие 5. 26 октября 2018.

• Сортировки.
• Квадратичные сортировки. Сортировка вставками, пузырьком, выбором.
• Сортировка слиянием. Подсчёт количества инверсий.
• Быстрая сортировка.
• Сортировка подсчётом.
• nth-элемент
• Подсчёт количества инверсий

Задание

• Тренировочный контест.

Занятие 4. 19 октября 2018.

• Жадные алгоритмы. Разбор на примере задач.
• Список(List).
• Стек(Stack).
• Очередь(Queue).
• Очередь с поддержкой минимума.

Задание

• Контест на тему "Жадные алгоритмы".

Занятие 3. 12 октября 2018.

• Примеры одномерной и двумерной динамики.
• Разбор на задач из задания предыдущего занятия.
• Техника двух указателей.

Задание

• Контест на тему "Два указателя".

Занятие 2. 5 октября 2018.

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

Задание

• Контест на тему Динамическое программирование.

Занятие 1. 21 сентября 2018.

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

Задание

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