Знание базовых алгоритмов и структур данных важно не только для написания производительного кода, но и для написания хорошего кода в принципе. Реализация классических алгоритмов и решение алгоритмических задач приучает писать код, соблюдая инварианты: такой код легче писать, читать и тестировать. Это одни из весомых причин, по которым компании требуют знания алгоритмов и проводят интервью с лайвкодингом.
В рамках этого курса мы изучим базовые алгоритмы и структуры данных, научимся решать классические теоретические задачи, которые (и им подобные) могут встретиться на интервью, а также решать задачи на программирование в тестирующей системе Codeforces. Всё это вместе позволит учащимся курса изучить алгоритмы, подготовиться к техническому интервью с лайвкодингом и в том числе подготовиться к секции по алгоритмам на вступительных экзаменах в ШАД.
Курс покрывает базовую теорию, в ходе обучения придётся решать значительное число теоретических задач и задач на программирование. Нужно быть готовыми к усердной работе. Вы сможете сдавать задачи на программирование почти на любом языке (см. список языков, [поддерживаемых Codeforces](
https://codeforces.com/blog/entry/79)). На занятиях код будет писаться на Python (поскольку он близок к псевдокоду) и на C++, где необходимо показать особенности указателей и возможности работы со структурами данных стандартной библиотеки (STL). Если вы ранее не программировали (не были знакомы ни с одним языком программирования), то курс может оказаться непомерно сложным: на обучение базовому программированию требуется отдельное время и усилие, поэтому порогом входа на курс является владение каким-то языком программирования; важно не бояться отладки и быть готовыми тратить на неё время.
1 модульЗнакомство с тестирующей системой Codeforces. Сложность алгоритмов. Простейшие алгоритмы с инвариантами.
2 модульПродолжение работы с инвариантами, «два указателя». Рекурсия и итерация: как исполняются рекурсивные алгоритмы.
3 модульАлгоритмы «разделяй и властвуй».
4 модульСортировки и опирающиеся на них задачи.
5 модульСтруктуры данных на (динамических) массивах.
6 модульСтруктуры данных на указателях.
7 модульАммортизационный анализ.
8 модульСтруктуры данных для запросов на отрезках. Модификация Декартова дерева. Дерево отрезков. Дерево Фенвика.
9 модульГрафы I. Поиск в ширину, алгоритмы Беллмана-Форда и Дейкстры.
10 модульГрафы II. Остовные деревья. Алгоритмы Крускала и Прима.
11 модульГрафы III. Поиск в глубину и его приложения (поиск компонент сильной связности, топологическая сортировка).
12 модульОт кратчайших путей к динамическому программированию.
13 модульДинамическое программирование II.
14 модульНижние оценки. Нижние оценки на поиск максимума и сортировки сравнениями.