Robert Sedgewick

Primary professional activities

• William O. Baker Professor, Department of Computer Science, Princeton University
• Author of several books published by Addison-Wesley
• Research in analysis of algorithms
• Director, Adobe Systems

Recent books

• Algorithms in Java, Part 5 (Graph Algorithms) (code, errata)
• Algorithms in Java, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) (code, errata)
• Algorithms in C++, Part 5 (Graph Algorithms) (code, errata)
• Algorithms in C, Part 5 (Graph Algorithms) (code, errata)
• Algorithms in C++, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) (code, errata)
• Algorithms in C, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) (code, errata)
• An Introduction to the Analysis of Algorithms, with Philippe Flajolet (errata)
• Algorithms in C++ (second edition)

Works in progress

• Analytic Combinatorics, with Philippe Flajolet
• Algorithms, Third Edition, Parts 6-8
• An Introduction to Computer Science , with Kevin Wayne
• "Left-Leaning Red-Black Trees" , September, 2008.

• Left-Leaning Red-Black Trees, Workshop on Analysis of Algorithms, Maresias, Brazil, April, 2008.
• Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.
• The Role of the Science and Mathematics in Software Development, Purdue University, West Lafayette, IN, November, 2007.
• The Role of the Scientific Method in Software Development, Adobe Systems, San Jose, CA, April, 2007.
• Creating "Algorithms", Adobe Systems, San Jose, CA, December, 2002; Tufts University, Medford, MA, May, 2003.
• Finding Paths In Graphs, Adobe Systems India, January, 2007; based on earlier talks at 2005 International Conference on the Analysis of Algorithms, Barcelona, June, 2005, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2004, and Ottawa-Carleton Discrete Math Day, April, 2004.
• Creating "Algorithms", Adobe Systems, San Jose, CA, December, 2002; Tufts University, Medford, MA, May, 2003.
• Permutation generation methods, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2002.
• Quicksort is optimal, Knuthfest, Stanford University, January, 2002.
• New research on the theory and practice of sorting (math supplement) Universite du Quebec a Montreal, April 27, 2001; New York Academy of Sciences, February 8, 2000; Ecole Polytechnique, Paris, France, May 25, 1999.
• Visualizing the analysis of algorithms, Fourth International Workshop on the Analysis of Algorithms, Princeton University, July 20, 1998.
• Online knowledge and the incandescent future of the university, Assembly of the Class of 2001, Princeton University, September 7, 1997.
• Open problems in the analysis of sorting and searching algorithms, Workshop on the probabilistic analysis of algorithms, Princeton, May, 1997.
• Sorting and searching strings, Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.
• Analysis of shellsort and related algorithms, Fourth European Symposium on Algorithms, Barcelona, September, 1996.

Princeton course development

• General Computer Science, 1992-
• Algorithms and Data Structures, 1986-, slides

Other professional activities

• Director, DIMACS Special Year on Massive Data Sets
• Area Editor for Journal of the ACM, Journal of Algorithms, and Algorithmica
• President's Advisory Committee on Architecture, Princeton University

Past professional appointments

• Founding Chair, Department of Computer Science, Princeton University (1985-94)
• Professor at Brown University, Providence, RI (1975-85)
• Visiting staff at Xerox PARC, Palo Alto, CA (1978, 1979)
• Visiting staff at INRIA, Rocquencourt, France (1982-83, 1990)
• Visiting staff at IDA, Princeton New Jersey (1978, 1979, 1983, 1990, 1994, 1997)
• Computer Science GRE Committee, Educational Testing Service (1986-1996)

Selected papers

• "Mellin transforms and asymptotics: finite differences and Rice's integrals" (with P. Flajolet) Theoretical Computer Science A 144, 1995.
• "The analysis of Heapsort" (with R. Schaffer), J. of Algorithms 13, 1993.
• "Deterministic skip lists" (with I. Munro and T. Papadakis), Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1992.
• "Tight lower bounds for Shellsort" (with M. Weiss), J. of Algorithms 11, 1990.
• "Pairing heaps: a new form of self-adjusting heap," (with M. Fredman, D. Sleator, and R. E. Tarjan) Algorithmica 1, 1, 1986.
• "Digital search tree analysis revisited" (with P. Flajolet), SIAM J. Computing 15, 2, 1986.
• "Shortest paths in euclidean graphs" (with J. Vitter), Algorithmica 1, 1, 1986.
• "A new upper bound for Shellsort," Journal of Algorithms 7, 1986.
• "Improved Upper Bounds for Shellsort" (with J. Incerpi), J. Computer and System Sciences 31, 2, 1985.
• "A system for algorithm animation" (with M. Brown) Computer Graphics 18, 3, 1984.
• Technical reports and old papers

General description of research goals

Developing general mechanisms relating algorithms, data structures, generating functions and analytic functions such that asymptotic results useful in predicting performance of the algorithms can be derived automatically and economically.

Investigating the way in which visual representations can provide an understanding of how algorithms gain efficiency, including dynamic graphical simulations of algorithms in operation and high-quality static representations suitable for use in publications.

Robert Sedgewick