Фундаментальные алгоритмы

После того, как я жестко облажался с самопальной сортировкой, причем облажался дважды: первый раз, когда думал, что порву по скорости STL'ный std::sort(), а второй - когда не понял, что все эти "ухищрения", как я думал, по ускорению QuickSort'а, реализованные в STL'е Visual Studio, есть ни что иное, как просто давно придуманный IntroSort.

В общем, я взял в руки:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка.



и начал освежать (а местами просто узнавать с нуля) когда-то читанное в студенчестве.

Втянулся.

Заказал вторую книгу:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах



Последние несколько лет я всегда делал основной упор на новые языки, операционные системы, организацию процесса разработки, работу над качеством и т.д. Получилось, что база как-то слегка подкосилась.

Вобщем, если вы все еще можете не думая сказать, например, чем лучше хеш-таблица по сравнению со сбалансированным (например, красно-черным) деревом, почему именно Splay-дерево удобно для реализации кеша, написать по памяти пирамидальную сортировку или привести пример NP-задачи, которая не является полной, то может фундамент все еще крепок.