Robert Sedgewick (computer scientist)

Robert Sedgewick
Sedgewick in 2020
Born	(1946-12-20) December 20, 1946 (age 78) Willimantic, Connecticut, United States
Alma mater	Brown University (B.S.; M.S.) Stanford University (Ph.D.)
Awards	ACM Fellow (1997), Flajolet Prize, Leroy P. Steele Prize, and Karlstrom Award
Scientific career
Fields	Computer science
Institutions	Princeton University Brown University (1975–85)
Thesis	Quicksort (1975)
Doctoral advisor	Donald Knuth

Robert Sedgewick (born December 20, 1946) is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University^[1] and was a member of the board of directors of Adobe Systems (1990–2016).^[2] He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA.^[3] His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing college curriculums in computer science.^[4]

Sedgewick was born on December 20, 1946, in Willimantic, Connecticut. During his childhood he lived in Storrs, Connecticut, where his parents Charles Hill Wallace Sedgewick and Rose Whelan Sedgewick were professors at the University of Connecticut.^[5]

In 1958, he moved with his parents to Wheaton, Maryland, a suburb of Washington, D.C., where he attended Wheaton High School, graduating in 1964.

Sedgewick earned his Bachelor of Science (1968) and Master of Science (1969) degrees in applied mathematics from Brown University, where he was a student of Andries van Dam. He went on to graduate work at Stanford University where he was an advisee of Donald E. Knuth, receiving his PhD in 1975.^[6] His thesis was entitled Quicksort and was named an outstanding dissertation in computer science.^[7]

Sedgewick returned to Brown to start his academic career as an assistant professor in 1975, with promotion to associate professor in 1980 and full professor in 1983. At Brown, he participated in the founding of the computer science department, in 1979.^[8]

In 1985, Sedgewick joined the faculty at Princeton University as founding chair of the Department of Computer Science^[9] where he later became the William O. Baker '39 Professor of Computer Science.^[10] The first-year courses in computer science that he developed at Princeton became quite popular.^[11] He also replaced live lectures with on-demand online videos.^[12]

Throughout his career, he has worked at research institutions outside of academia during summers and sabbatical leaves:

• The Communications Research Division of the Institute for Defense Analyses in Princeton, New Jersey, working on the CRAY-1 supercomputer.
• Xerox Palo Alto Research Center (PARC) with some of the early personal computers
• The Institut National de Recherche en Informatique et en Automatique (INRIA) in France, in collaboration with Philippe Flajolet.

Sedgewick developed red–black trees (with Leonidas J. Guibas),^[13] ternary search trees (with Jon Bentley),^[14] and pairing heaps (with R. E. Tarjan and Michael Fredman).^[15] He solved open problems left by Donald Knuth in the analysis of quicksort,^[16] shellsort,^[17] heapsort (with R. Schaffer),^[18] and Batcher's sort.^[19] With Philippe Flajolet, he developed the field of mathematics known as analytic combinatorics.

He has organized research meetings and conferences on data structures, algorithm science, and analytic combinatorics around the world, including Dagstuhl seminars on analysis of algorithms and data structures,.^[20] In particular, in 1993, together with Rainer Kemp, Philippe Flajolet and Helmut Prodinger, he initiated a series of workshops and conferences which was key to the development of a research community around the analysis of algorithms, and which evolved into the AofA—International Meeting on Combinatorial, Probabilistic, and Asymptotic Methods in the Analysis of Algorithms. Robert Sedgewick was also the main proponent and organizer of the first editions of the SIAM Meetings on Analytic Algorithmics and Combinatorics (ANALCO),^[21] a series of meetings annually held from 2004 to 2019, co-located with the Symposium on Discrete Algorithms (SODA).

Sedgewick is the author of twenty books, including Algorithms,^[22] originally published in 1983. His 2008 book with Philippe Flajolet, Analytic Combinatorics,^[23] was awarded the Leroy P. Steele Prize for mathematical exposition by the American Mathematical Society.^[24] More recently, he co-authored with Kevin Wayne the book Computer Science: An Interdisciplinary Approach.^[25]

Sedgewick has developed massive open online courses in his area.^[26][27][28] With Kevin Wayne, he developed a model that integrates the textbook, studio-produced online lectures, and online content.^[29][30] These have had over one million registrants.^[31] He advocates for expanding the reach of computer science,^[32][33][34] with essays published in the Wall Street Journal^[35] and Inside Higher Ed.^[36]

• Flajolet Lecture Prize. AofA—International Meeting on Combinatorial, Probabilistic, and Asymptotic Methods in the Analysis of Algorithms, 2016.^[37]
• Leroy P. Steele Prize for Mathematical Exposition. American Mathematical Society, 2019.^[38]
• Karl V. Karlstrom Outstanding Educator Award. Association for Computing Machinery, 2019.^[39]

• Computer Science: An Interdisciplinary Approach (with K. Wayne). Addison-Wesley, Reading, MA, 2016, 1131 pp. Associated online content: Booksite, curated lectures Part 1 and Part 2, and MOOCs Part 1 and Part 2.
• Algorithms, Fourth Edition (with K. Wayne). Addison-Wesley, Reading, MA, 2011, 955 pp. Earlier editions: 11 books, using 5 programming languages, translated into many foreign languages, 1983–2003. Associated online content: Booksite, curated lectures, and MOOCs Part 1 and Part 2.
• An Introduction to the Analysis of Algorithms, Second Edition (with P. Flajolet). Addison-Wesley, Reading, MA, 2013, 572 pp. First edition, 1996. Associated online content: Booksite, curated lectures, and MOOC.
• Analytic Combinatorics (with P. Flajolet). Cambridge University Press, 2009, 824pp. Associated online content: Booksite, curated lectures, and MOOC.

According to his personal website, Sedgewick lives in Princeton, New Jersey and spends summers in Jamestown, Rhode Island with his wife Linda (née Migneault), married in 1971. They have four children.^[40]

• Sedgewick, Robert (1980). Quicksort. Garland Publishing, Inc. ISBN 0-8240-4417-7.
• Sedgewick, Robert (1983). Algorithms (1st ed.). Addison-Wesley. ISBN 0-201-06672-6.
• Sedgewick, Robert (1988). Algorithms (2nd ed.). Reading, MA: Addison-Wesley. ISBN 978-0201066739.
• Sedgewick, Robert (1990). Algorithms in C. Reading, MA: Addison-Wesley. ISBN 978-0201514254.
• Sedgewick, Robert (1992). Algorithms in C++. Reading, MA: Addison-Wesley. ISBN 978-0201510591.
• Sedgewick, Robert (1993). Algorithms in Modula-3. Reading, MA: Addison-Wesley. ISBN 978-0201533514.
• Flajolet, Philippe; Sedgewick, Robert (1995). An Introduction to the Analysis of Algorithms. Addison-Wesley. ISBN 978-0-201-40009-0.
• Sedgewick, Robert (1998). Algorithms, 3rd Edition, in C, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching. Reading, MA: Addison-Wesley. ISBN 978-0201314526.
• Sedgewick, Robert (1998). Algorithms, 3rd Edition, in C++, Parts 1–4: Fundamentals, Data Structures, Sorting, and Searching. Reading, MA: Addison-Wesley. ISBN 978-0201350883.
• Sedgewick, Robert (2001). Algorithms, 3rd Edition, in C, Part 5: Graph Algorithms. Reading, MA: Addison-Wesley. ISBN 978-020131663-6.
• Sedgewick, Robert (2002). Algorithms, 3rd Edition, in C++, Part 5: Graph Algorithms. Reading, MA: Addison-Wesley. ISBN 978-0201361186.
• Sedgewick, Robert (2002). Algorithms, 3rd Edition, in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, and Searching. Reading, MA: Addison-Wesley. ISBN 978-0201361209.
• Sedgewick, Robert (2003). Algorithms, 3rd edition, in Java, Part 5: Graph Algorithms. Reading, MA: Addison-Wesley. ISBN 978-0201361216.
• Sedgewick, Robert; Wayne, Kevin (2007). An Introduction to Programming in Java: An Interdisciplinary Approach. Addison-Wesley. ISBN 978-0-321-49805-2.
• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 978-0-521-89806-5.
• Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
• Sedgewick, Robert; Wayne, Kevin (2015). An Introduction to Programming in Python: An Interdisciplinary Approach. Addison-Wesley. ISBN 978-0134076430.
• Sedgewick, Robert; Wayne, Kevin (2015). Algorithms: 24-part Lecture Series. Addison-Wesley Professional. ISBN 978-0134384528.
• Sedgewick, Robert; Wayne, Kevin (2016). Computer Science: An Interdisciplinary Approach. Addison-Wesley. ISBN 978-0134076423.

• Robert Sedgewick's home page
• People of the ACM
• Google Scholar
• Video interview with Robert Sedgewick for Princeton Startup TV (04.06.2012)