1. Сортировка: insertion sort, quick sort, heap sort и merge sort должны отскакивать от зубов. Bucket sort, counting sort, radix sort. Сортировка односвязного списка с помощью merge sort.
2. Двоичные деревья поиска: поиск, вставка, удаление, разные виды обходов, вращение. Сбалансированные деревья: red-black tree, splay tree, B-tree.
3. Двоичные кучи.
4. Хэш-таблицы: подходы к реализации, требования к хэш-функции. Преимущества и недостатки по сравнению со сбалансированными деревьями.
5. Динамическое программирование: сама концепция и типичные представители — расстояние между строками, нахождение подмассива с наибольше суммой и т. д.
6. Графы: BFS и DFS, нахождение MST, топологическая сортировка, определение связности и нахождение связных компонент, кратчайшие пути (Dijkstra, A*).
7. Жадные алгоритмы: сама концепция и типичные представители — Prim, Kruskal, EDF scheduling.
8. Tries.
9. Суффиксные массивы и их типичные применения.
10. Экзотические деревья: kd tree, interval tree, quad tree.
11. Пространственные алгоритмы: выпуклая оболочка, нахождение точки, ближайшей к заданной, поиск точек, попадающих в диапазон, поиск пересечений отрезков.
12. Комбинаторные алгоритмы: получение следующей перестановки, выбор всех подмножеств заданного размера.
13. Теория вероятностей: основы и типовые задачи. Вероятностные алгоритмы: случайная выборка (в том числе из потока), перемешивание.
14. Поиск подстроки в строке: KMP, Rabin-Karp, остальные по желанию.
15. NP-complete. Знать, что это. Знать классические задачи.
16. Многопоточность: deadlock и способы его обнаружения/предотвращения, livelock, starvation, примитивы синхронизации, классические задачи (читатели-писатели, производители-потребители, обедающие философы). Атомарные операции (compare-and-set) и их использование.
17. Backtracking: решение судоку, расстановка ферзей