Insights and Algorithms
Cristopher Moore, Stephan Mertens · 2011
Abstract There are many forms of mathematical insights, but only a few major strategies can be used to construct polynomial-time algorithms. These include divide and conquer, dynamic programming, greedy algorithms, duality, and reductions. This chapter explores these strategies and considers how a problem can be broken into subproblems that are small enough, and few enough, to solve quickly. It presents examples that demonstrate how to sort a pack of cards, align genomes, find short paths, hear the music of the spheres, route the flow of traffic, typeset beautiful books, build efficient networks, or run a dating service. The chapter begins with a classic example of recursion: the Towers of Hanoi, introduced by the mathematician Edouard Lucas. It then looks at several important problems where a divide-and-conquer strategy works and explains how so many other problems can be expressed in terms of reachability and shortest path.