Edward Reingold

Education

B.S. Mathematics, Illinois Institute of Technology, 1967
M.S. Computer Science, Cornell University, 1969
Ph.D. Computer Science, Cornell University, 1971

Professional Affiliations & Memberships

Association for Computing Machinery

Society for Industrial and Applied Mathematics

American Mathematical Society

Mathematical Association of America

Awards

Fellow of the ACM, 1996

Everitt Teaching Award, College of Engineering, University of Illinois at Urbana-Champaign, 2000

Number 3103 on the list of “10000 Most Cited Authors in Computer Science” as of August, 2006 (CiteSeer)

Distinguished Educator Award, Department of Computer Science, University of Illinois, 2016

Publications

1. “On the Time Required to Detect Cycles and Connectivity in Graphs” (with R. C. Holt) Math. Systems Theory

6 (1972), 103–106.

2. “On the Optimality of Some Set Algorithms,” J. ACM 19 (1972), 649–659.

3. “Infix to Prefix Translation: The Insufficiency of a Pushdown Stack,” SIAMJ. on Computing 1 (1972), 350–353.

4. “A Nonrecursive List Moving Algorithm,” Communications of the ACM 16 (1973), 305–307.

5. “Binary Search Trees of Bounded Balance” (with J. Nievergelt), SIAM J. on Computing 2 (1973), 33–43.

6. “Backtrack Programming Techniques” (with J. R. Bitner), Communications of the ACM 18 (1975), 651–656.

7. “Tiling with Incomparable Rectangles” (with A. C.-C. Yao and B. Sands), J. Recreational Math. 8 (1976),

112–119.

8. “Efficient Generation of the Binary Reflected Gray Code and Its Applications” (with J. R. Bitner and G. Ehrlich),

Communications of the ACM 19 (1976), 517–521.

9. “Understanding the Complexity of Interpolation Search” (with Y. Perl), Info. Proc. Let. 6 (1977), 219–222.

10. “A Note on 3-2 Trees,” Fibonacci Quart. 17 (1979), 151–157.

11. “Tidier Drawings of Trees” (with J. S. Tilford), IEEE Trans. Software Engineering 7 (1981), 223–228.

12. “A Comment on the Evaluation of Polish Postfix Expressions,” The Computer Journal 24 (1981), 288.

13. “On a Greedy Heuristic for Complete Matching” (with R. E. Tarjan), SIAMJ. on Computing 10 (1981), 676–681.

14. “A Naturally Occurring Function Continuous Only at Irrationals” (with A. Bagchi), Amer. Math. Monthly 89

(1982), 411–417.

15. “Aspects of Insertion in Random Trees” (with A. Bagchi), Computing 29 (1982), 11–29.

16. “Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching” (with K. J. Supowit), SIAM J. on

Computing 12 (1983), 118–143.

17. “The Traveling Salesman Problem and Minimum Matching in the Unit Square” (with K. J. Supowit and D. A.

Plaisted), SIAM J. on Computing 12 (1983), 144–156.

18. “Probabilistic Analysis of Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching” (with

K. J. Supowit), Networks 13 (1983), 49–66.

19. “The Complexity of Drawing Trees Nicely” (with K. J. Supowit), Acta Informatica 18 (1983), 377–392.

20. “A Hierarchy-Driven  Amalgamation of Standard and Macro Cells” (with K. J. Supowit), IEEE Trans. Computer-

Aided Design of Integrated Circuits and Systems 3 (1984), 3–11.

21. “Recurrence Relations Based on Minimization and Maximization” (with S. Kapoor), J. Math. Anal. and Appl.

109 (1985), 591–604.

22. “Optimum Lopsided Binary Trees” (with S. Kapoor), J. ACM 36 (1989), 573–590.

23. “Solution of a Divide-and-Conquer Maximin Recurrence” (with Z. Li), SIAMJ. on Computing 18 (1989), 1188–

1200.

24. “Calendrical Calculations” (with N. Dershowitz), Software—Practice and Experience 20 (1990), 899–928.

25. “Probabilistic Analysis of a Grouping Algorithm” (with D. F. Wong), Algorithmica 6 (1991), 192–207.

26. “Stochastic Rearrangement Rules for Self-Organizing Data Structures” (with S. Kapoor), Algorithmica 6 (1991),

278–291.

27. “More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case” (with X. Shen), SIAM J.

on Computing 20 (1991), 156–183.

28. “More Nearly Optimal Algorithms for Unbounded Searching, Part II: The Transfinite Case” (with X. Shen),

SIAM J. on Computing 20 (1991), 184–208.

29. “Graph Drawing by Force-Directed Placement,” (with T. M. J. Fruchterman), Software—Practice and Experience

21 (1991), 1129–1164. One of the most cited articles in computer science published in 1991 (as per

CiteSeer).

30. “Scheduling on a Hypercube” (with X. Shen), Info. Proc. Let. 40 (1991), 323–328.

31. “ ‘Lion and Man’: Upper and Lower Bounds” (with L. Alonso and A. S. Goldstein), ORSA J. Comput. 4 (1992),

447–452.

32. “Calendrical Calculations, Part II: Three Historical Calendars” (with S. M. Clamen and N. Dershowitz),

Software—Practice and Experience 23 (1993), 383–404.

33. “A Fibonacci Version of Kraft’s Inequality with an Application to Discrete Unimodal Search” (with A. S. Goldstein),

SIAM J. on Computing 22 (1993), 751–777.

34. “Determining the Majority” (with L. Alonso and R. Schott), Info. Proc. Let. 47 (1993), 253–255.

35. “Efficient Management of Dynamic Tables” (with A. Fraenkel and P. Saxena), Info. Proc. Let. 50 (1994),

25–30.

36. “Complexity of a Pursuit Problem” (with A. S. Goldstein), Theoretical Comp. Sci. 143 (1995), 93–112.

37. “Multidimensional Divide-and-Conquer Maximin Recurrences” (with L. Alonso and R. Schott), SIAM J. on

Discrete Math. 8 (1995), 428–447.

38. “Generalized Kraft’s Inequality and Discrete k-Modal Search” (with A. Mathur), SIAM J. on Computing 25

(1996), 420–447.

39. “Basic Techniques for Design and Analysis of Algorithms,” ACM Computing Surveys 28 (1996), 19–21.

40. “The Average-Case Complexity of Determining the Majority” (with L. Alonso and R. Schott), SIAM J. on

Computing 26 (1997), 1–14.

41. “K-M-P String Matching Revisited” (with K. J. Urban and D. Gries), Info. Proc. Let. 64 (1997), 217–223.

42. “Optimal Index Assignment for Multichannel Communication” (with T. Y. Berger-Wolf), IEEE Trans. on Information

Theory 48 (2002), 2656–2668.

43. “The Worst-Case Chip Problem” (with L. Alonso, P. Chassaing, and R. Schott), Info. Proc. Let. 89 (2004),

303–308.

44. “Line Drawing, Leap Years, and Euclid,” (with M. A. Harris), ACM Computing Surveys 36 (2004), 68–80.

45. “Quicksort with Unreliable Comparisons: A Probabilistic Analysis” (with L. Alonso, P. Chassaing, F. Gillet, S.

Janson, and R. Schott), Combinatorics, Probability and Computing 13 (2004), 419–449.

46. “Average-case Analysis of the Chip Problem” (with L. Alonso, P. Chassaing, and R. Schott), International

Journal of Mathematics and Computer Science 1 (2006), 37–61.

47. “Determining Plurality” (with L. Alonso), ACM Transactions on Algorithms 4 (2008), 26-1–26-19.

48. “Average-Case Lower Bounds for the Plurality Problem,” (with L. Alonso), ACM Transactions on Algorithms 4

(2008), 27-1–27-17.

49. “Average-Case Analysis of Some Plurality Algorithms” (with L. Alonso), ACM Transactions on Algorithms 5

(2009), 17-1–17-36.

50. “Bounds for Cops and Robber Pursuit” (with L. Alonso), Computational Geometry: Theory and Applications

43 (2010), 749–766.

51. “Improved Bounds for Cops-and-Robber Pursuit” (with L. Alonso), Computational Geometry: Theory and

Applications 44 (2011), 365–369.

52. “Analysis of Boyer and Moore’s MJRTY Algorithm (with L. Alonso), Info. Proc. Let. 113 (2013), 495–497.

Books

1. Computer Approaches to Mathematical Problems (with J. Nievergelt and J. C. Farrar), Prentice-Hall, 1974.

Translated into Japanese, Russian, Polish, and Hungarian. Out of print 1987.

2. Combinatorial Algorithms: Theory and Practice (with J. Nievergelt and N. Deo), Prentice-Hall, 1977. Translated

into Russian and Polish. Out of print 1997.

3. Data Structures (with W. J. Hansen), Little, Brown, and Co., 1983. Out of print 1995.

4. Data Structures in Pascal (with W. J. Hansen), Little, Brown and Co., 1986. Out of print 1997.

5. PascAlgorithms (with R. N. Reingold), Scott, Foresman/Little, Brown and Co., 1988. Out of print 1993.

6. Programming with class: A C++ Introduction to Computer Science (with S. N. Kamin), McGraw-Hill Book

Co., 1996. Out of print 2001.

7. Calendrical Calculations (with N. Dershowitz), Cambridge University Press, 1997. Second (Millennium) edition,

2001; 2002 Choice Outstanding Academic Title Award Winner. Third edition, 2008. Fourth edition, 2018.

8. An Introduction to Computer Science Using Java (with S. N. Kamin and M. D. Mikunas), McGraw-Hill Book

Co., 1998. Second edition, 2002.

9. Calendrical Tabulations 1900–2200 (with N. Dershowitz), Cambridge University Press, 2002. Out of print

2013.