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

Палиндром — это строка, которая читается одинаково слева направо и справа налево ("А РОЗА УПАЛА НА ЛАПУ АЗОРА"). Задача поиска самой длинной палиндромной подстроки внутри гигантского текста часто встречается в биоинформатике (поиск симметричных последовательностей в молекулах ДНК) и криптоанализе. Простой перебор всех возможных центров и расширение от них дает сложность O(N^2). В 1975 году Гленн Манакер (Glenn Manacher) создал невероятно элегантный алгоритм, решающий эту задачу за строго линейное время O(N).

Регулярные выражения (Regex) — невероятно мощный инструмент для парсинга текста. Разработчики используют их для проверки email-адресов, номеров кредитных карт и телефонных кодов. Однако у них есть фундаментальный математический изъян: конечные автоматы, стоящие за регулярными выражениями, "не умеют считать". Как строго доказать, что какую-то строку невозможно распарсить с помощью Regex? Для этого в дискретной математике создана Лемма о разрастании (Pumping Lemma).