Линейные структуры данных.
3 недели
Краткая программа курса
Введение в алгоритмы и структуры данных
Определение асимптотики, оценка времени работы программы, оценка затраченной памяти
Односвязные и двусвязные списки, работа с ними
Реализация игрушечного менеджера памяти при помощи LRU и LFU кэша
Рекурсия и комбинаторика.
1 неделя
Рекурсивные переборы, переборы всех комбинаторных объектов
Перестановки, разбиение на слагаемые, строки Фибоначчи
Перебор битовых масок
Упорядочивание данных во внешней памяти и поиск по ним. Программа для решения кроссвордов судоку
Сортировки и поиск.
2 недели
Сортировки, использование встроенной функции sort в языках
Алгоритм бинарного поиска. Бинарный поиск по ответу
Сортировка больших файлов с данными, потенциально не помещающихся в оперативную память
Хеширование.
3 недели
Принцип хеширования. Парадокс дней рождения. Известные алгоритмы хеширования.
Полиномиальное хеширование
Алгоритмы на строках
Хеш-таблица, встроенная реализация, собственная реализация
Генератор magnet-ссылок для файлов и папок
Графы.
2 недели
Графы. Представление графов и алгоритм DFS
Графы. Задача о поиске кратчайшего пути в графе, алгоритм BFS
Алгоритм Дейкстры
Travel planner — постройка кратчайшего маршрута для путешествия
Деревья.
5 недель
Графы. Представление деревьев. Алгоритмы на деревьях
Кучи
Бинарное дерево поиска, работа с ним
Красно-черное дерево, AVL-дерево
Деревья Хаффмана
Реализация алгоритма Liquid Resize
Карьерный блок.
2 недели
Фишки прохождения технических собеседований в крупные IT-компании
Mock-интервью «Собеседование в Amazon»
Динамическое программирование.
3 недели
Задачи динамического программирования. Базовые применения. Префиксные суммы
Задачи динамического программирования. Сложные задачи. Задача о рюкзаке
Конечные автоматы. Регулярные выражения