Алгоритмы и структуры данных 2 2020/2021

Лектор: Антон Полднев

Расписание лекций:
вторник 09:30 – 10:50
суббота 11:10 – 12:30

Канал для объявлений:
https://t.me/aisd2_20

Консультации:
hse@poldnev.ru

Ассистенты:

Лекции

1. 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. Лекция, презентация
2. 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. Лекция, презентация
3. 8 сентября. Префикс- и z-функция. Лекция, презентация
4. 12 сентября. Алгоритм Ахо — Корасик Лекция, презентация .
5. 15 сентября. Паросочетания. Алгоритм Куна Лекция, презентация .
6. 19 сентября. Потоки. Алгоритм Форда — Фалкерсона.
7. 22 сентября. Параллельность в C++.
8. 26 сентября. Контрольная работа по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
9. 29 сентября. Параллельные алгоритмы.
10. 3 октября. P и NP.
11. 6 октября. P и NP.
12. 10 октября. Эвристики в рекурсивном переборе.
13. 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch.
14. 17 октября. Подготовка к экзамену.

Домашние задания

Штрафов за неверные посылки нет, учитывается лишь количество успешно сданных задач

1. Задачи на отрезках. 05.09 12:30 — 19.09 23:59
2. Задачи на строках. 12.09 12:30 — 26.09 23:59
3. Паросочетания и потоки. 19.09 12:30 — 03.10 23:59

Оценки

Итоговая оценка: 0,25×ДЗ + 0,1×С + 0,25×КР + 0,4×Э, где:

• ДЗ — домашние задания (контесты)
  
• С — работа на семинаре
  
• КР — контрольная в середине модуля (контест)
  
• Э — экзамен (контест и теория)

Возможность получить автомат

Если в конце модуля выполнены следующие условия:

• (0,25×ДЗ + 0,1×С + 0,25×КР)/0,6 получается 8 и выше
• Оценка за работу на семинаре не ниже 5

то можно получить автомат: О_итог = O (0,25×ДЗ + 0,1×С + 0,25×КР)/0,6