Many people gave me helpful feedback on earlier versions of this tutorial. In particular, thousands of students at Princeton and Brown have suffered through preliminary drafts over the years. Special thanks are due to Trina Avery and Tom Freeman for their help in producing the first version; to Janet Incerpi for her creativity and ingenuity in persuading our early and primitive digital computerized typesetting hardware and software to produce the first version; to Marc Brown for his part in the algorithm visualization research that was the genesis of so many of the figures in the tutorial; to Dave Hanson and Andrew Appel for their willingness to answer all of my questions about coding languages; and to Kevin Wayne, for patiently answering my basic questions about networks. Kevin urged me to include the network simplex algorithm in this tutorial, but I was not persuaded that it would be possible to do so until I saw a presentation by Ulrich Lauther at Dagstuhl of the ideas on which the implementations in are based. I would also like to thank the many readers who have provided me with comments about various versions, including Guy Almes, Jon Bentley, Marc Brown, Jay Gischer, Allan Heydon, Kennedy Lemke, Udi Manber, Michael Quinn, Dana Richards, John Reif, M. Rosenfeld, Stephen Seidman, and William Ward. To produce this new version, I have had the pleasure of working with Peter Gordon and Helen Goldstein at Oracle, who have patiently shepherded this project as it has evolved. It has also been my pleasure to work with several other members of the professional staff at Oracle. The nature of this project made the tutorial a somewhat unusual challenge for many of them, and I much appreciate their forbearance. I have gained three new mentors while writing this tutorial and particularly want to express my appreciation to them. First, Steve Summit carefully checked early versions of the manuscript on a technical level and provided me with literally thousands of detailed comments, particularly on the programs. Steve clearly understood my goal of providing elegant, efficient, and effective implementations, and his comments not only helped me to provide a measure of consistency across the implementations, but also helped me to improve many of them substantially. Second, Lyn Dupré also provided me with thousands of detailed comments on the manuscript, which were invaluable in helping me not only to correct and avoid grammatical errors, but also—more important—to find a consistent and coherent writing style that helps bind together the daunting mass of technical material here. Third, Chris Van Wyk, in a long series of spirited electronic mail exchanges, patiently defended the basic precepts of object-oriented coding and helped me develop a style of coding that exhibits the algorithms with clarity and precision while still taking advantage of what object-oriented coding has to offer. The approach that we developed for the C++ version of this tutorial has substantially influenced the Java code here and will certainly influence future volumes in both languages (and C as well). I am extremely grateful for the opportunity to learn from Steve, Lyn, and Chris—their input was vital in the development of this tutorial. Much of what I have written here I have learned from the teaching and writings of Don Knuth, my advisor at Stanford. Although Don had no direct influence on this work, his presence may be felt in the tutorial, for it was he who put the study of algorithms on the scientific footing that makes a work such as this possible. My friend and colleague Philippe Flajolet, who has been a major force in the development of the analysis of algorithms as a mature research area, has had a similar influence on this work. I am deeply thankful for the support of Princeton University, Brown University, and the Institut National de Recherche en Informatique et Automatique (INRIA), where I did most of the work on the tutorial; and of the Institute for Defense Analyses and the Xerox Palo Alto Research Center, where I did some work on the tutorial while visiting. Many parts of the tutorial are dependent on research that has been generously supported by the National Science Foundation and the Office of Naval Research. Finally, I thank Bill Bowen, Aaron Lemonick, and Neil Rudenstine for their support in building an academic environment at Princeton in which I was able to prepare this tutorial, despite my numerous other responsibilities. Robert Sedgewick
Marly-le-Roi, France, 1983
Princeton, New Jersey, 1990, 1992
Jamestown, Rhode Island, 1997, 2001
Princeton, New Jersey, 1998, 2003