Алгоритмы и структуры данных (Русскоязычные иностранцы)

Общие сведения

• Семестр: 3/5 (второй/третий курсы)
• Формат: очный
• Форма контроля: дифференцированный зачет + экзамен

Важные ссылки

Чат курса - там можно задавать вопросы по курсу, задачам, изредка флудить

Канал курса - там будут все важные объявления (домашние задания, оргвопросы, etc.)

Папка с теоретическими заданиями

Ведомость курса

Форма для регистрации на курс

Требования

• Физтех-почта (домен phystech.edu)
• Аккаунт на Я.Контесте (можно на физтех-почту)
• Аккаунт на гитлабе

Обязательно заполнить форму регистрации на курс до 1 ноября! В противном случае считается, что курс вы сдавать не планируете или вы согласны на добровольную пересдачу по обоим предметам.

План курса

1. Базовые алгоритмы
 - Бинарный поиск: классический, вещественный, по ответу
 - Префиксные суммы. Обобщение на произвольную ассоциативную и обратимую операцию
 - Основы теории чисел:
   * Модульная арифметика
   * Решето Эратосфена
   * Поиск обратного по модулю: с использованием функции Эйлера, с использованием расширенного алгоритма Евклида
 - Амортизационный анализ: метод монеток, метод потенциалов
 - Линейные контейнеры
   * Динамически расширяющийся буффер
   * Списки: односвязный, двусвязный
   * Адаптеры: стек, очередь, дек
   * Очередь с минимумом
2. Сортировки
 - Сортировка слиянием (MergeSort). Подсчет числа инверсий
 - Бинарная пирамида (Binary heap). Пирамидальная сортировка (HeapSort)
 - Быстрая сортировка (QuickSort)
 - Поиск k-й порядковой статистики
3. Деревья поиска
 - Наивное дерево поиска. Поддержка lower_bound, k-й порядковой статистики
 - AVL-дерево
 - Декартово дерево
 - Splay дерево
4. Хеш-таблицы
 - Метод цепочек
 - Универсальное семейство хеш-функций
5. Динамическое программирование (ДП)
 - Постановка задачи ДП
 - Задачи НВП (наибольшая возрастающая подпоследовательность), НОП (наибольшая общая подпоследовательность)
 - ДП по подотрезкам: подсчет числа подпоследовательностей палиндромов, задача о перемножении матриц
6. Структуры для работы с непрерывными данными
 - Постановка задач static/dynamic offline/online RMQ/RSQ
 - Дерево отрезков с групповыми операциями
 - Дерево Фенвика. Обобщение на многомерный случай
7. Вычислительная геометрия на плоскости
 - Взаимное расположение геометрических примитивов: точек, прямых, отрезков, окружностей
 - Работа с многоугольниками: подсчет площади, принадлежность точки
 - Выпуклая оболочка. Алгоритмы Джарвис, Грехема
 - Построение огибающих
 - Динамическая выпуклая оболочка, случай только с добавлением
 - Сумма Минковского. Построение для двух выпуклых многоугольников
 - Две ближайшие точки на плоскости
 - Две самые удаленные точки на плоскости

Оценивание

За курс ставятся сразу две оценки: дифференцированный зачет за "Практикум по алгоритмам и структурам данных", экзамен по дисциплине "Алгоритмы и структуры данных".

Оценивание дифференцированного зачета

Оценка состоит из следующих компонент:

1. Баллы за контесты (далее A): до 7 баллов

Пусть X - число набранных баллов студентом, S - число набранных идеальным студентом баллов. Тогда баллы за контесты определяются как A = round(X / S, 2) * 7

2. Баллы за теоретические задания (далее B): до 3 баллов

Пусть X - число набранных баллов студентом, S - число набранных идеальным студентом баллов. Тогда баллы за контесты определяются как B = round(X / S, 2) * 3

3. Бонус от преподавательского состава (далее B): до 1 балла. Ставится семинаристом или лектором с шагом 0.1

Последняя компонента. Пусть F - число задач, в решениях которых студент был уличен в плагиате.

Итоговая оценка: clamp(round(A + B + C - F), 2, 10), однако если F > 2, то итоговая оценка неуд(2).

Оценивание экзамена

Программа и правила проведения экзамена

Команда курса

Лектор курса Кулапин Артур

Семинаристы:

Филатенков Артур - семинарист Б05-251

Смолин Александр - семинарист Б05-252

Долта Артем - семинарист Б05-253

Козловский Владислав - семинарист Б05-(153-155)