Обычные бинарные деревья поиска обладают отличным временем операций O(log N), но только если данные поступают в случайном порядке. Если загрузить в дерево уже отсортированный массив, оно выродится в длинную "макаронину", и время поиска деградирует до O(N). Строгие балансировщики (АВЛ-деревья или Красно-черные деревья) решают проблему, но их реализация требует сотен строк сложного кода с вращениями. Дискретная математика предлагает невероятно элегантную альтернативу — рандомизированное Декартово дерево (Treap).

При решении задач о поиске максимального потока в транспортных сетях классический алгоритм Форда-Фалкерсона имеет фатальный недостаток: его время работы зависит от величины самого потока. Если пропускные способности ребер иррациональны, алгоритм может вообще никогда не завершиться. Эту проблему блестяще решил советский математик Ефим Диниц в 1970 году, предложив алгоритм, работающий за строго полиномиальное время, не зависящее от значений пропускных способностей.

Две самые известные NP-трудные задачи в теории графов — это поиск Хроматического числа (минимального числа цветов для правильной раскраски вершин) и поиск Кликового числа (размера самой большой клики — полностью связанного подграфа). Очевидно, что хроматическое число не может быть меньше кликового (вершины клики обязаны иметь разные цвета). Но в общем случае хроматическое число может быть сколь угодно большим, даже если клик нет вообще. Однако существует элитный класс графов, для которых эти два числа всегда равны. Это Совершенные графы.