ICS 161, Winter 1996:
Design and Analysis of Algorithms

Algorithm Designers

• Manuel Blum is a professor at U.C. Berkeley. He was one of the inventors of the deterministic linear time selection algorithm. He won the Turing award, the ACM's highest honor, in 1995. His most recent research has been on methods for automatically checking the correctness of programs.

• O. Boruvka. Boruvka's algorithm is one of three classical minimum-spanning tree algorithms.

• Robert Stephen Boyer now works with J. S. Moore on automatic theorem proving programs at U. Texas, Austin. The Boyer-Moore string matching algorithm is described in Baase, but I didn't say much about it in lecture.

• N. Christofides. Christofides' heuristic approximates the minimum-length traveling salesman tour within a factor of 1.5.

• Edsger Wybe Dijkstra is Schlumberger Professor of Computer Science and Mathematics at U. Texas, Austin. He won the Turing award, the ACM's highest honor, in 1972. Dijkstra's algorithm finds shortest paths from a single source to all other vertices of a graph.

• Robert W. Floyd is a professor at Stanford. He never received a Ph.D., although his many accomplishments would easily have been enough to earn one. He won the Turing award, the ACM's highest honor, in 1978. He was one of the inventors of the deterministic linear time selection algorithm. He also made early improvements in quicksort and quickselect.

• Ronald Lewis Graham is a mathematician at Bell Labs and past president of the American Mathematics Society. In 1972 he published the Graham scan convex hull algorithm.

• Daniel S. Hirschberg is a professor here at UC Irvine. He invented a space-efficient version of the longest common subsequence dynamic programming algorithm.

• Charles Antony Richard Hoare is James Martin Professor of Computing at Oxford University. He won the Turing award, the ACM's highest honor, in 1980. Hoare invented quicksort.

• Donald Ervin Knuth is a professor (emeritus) at Stanford. He is most famous for inventing the TeX and Metafont typesetting systems, and for writing "The Art of Computer Programming", a multi-volume compendium on algorithms that is still worth reading (even though much of it was written in the 1960's). He won the Turing award, the ACM's highest honor, in 1974. Knuth was one of the inventors of the Knuth-Morris-Pratt string matching algorithm.

• Joseph B. Kruskal is a researcher at Bell Labs (now AT&T?). Kruskal's algorithm is one of three classical minimum-spanning tree algorithms.

• J. Strother Moore now works with R. S. Boyer on automatic theorem proving programs at U. Texas, Austin. The Boyer-Moore string matching algorithm is described in Baase, but I didn't say much about it in lecture.

• James H. Morris, Jr. was one of the inventors of the Knuth-Morris-Pratt string matching algorithm.

• John von Neumann was a mathematician of many talents; among other works, he invented linear programming, automata theory, and game theory. He also helped build one of the first electronic computers, ENIAC. In 1945, he discovered merge sort.

• Leonardo of Pisa. was also known as Fibonacci. He invented the Fibonacci numbers while studying the population dynamics of rabbits.

• Vaughan Ronald Pratt is a professor at Stanford. He was one of the inventors of the deterministic linear time selection algorithm and the Knuth-Morris-Pratt string matching algorithm.

• R. C. Prim. Prim's algorithm is one of three classical minimum-spanning tree algorithms.

• Ronald Linn Rivest is the Webster Professor of Electrical Engineering and Computer Science at MIT. He was one of the inventors of the deterministic linear time selection algorithm. He also made an early improvement in quickselect. He is more famous recently for his role in creating the "RSA" cryptography algorithm, together with Adi Shamir and Leonard M. Adelman.

• Robert Endre Tarjan is a professor at Princeton. He won the Turing award, the ACM's highest honor, in 1986. Tarjan invented the strongly connected components algorithm described in lecture. He was also one of the inventors of the deterministic linear time selection algorithm.

• John William Joseph Williams invented Heap sort.

ICS 161 -- Dept. Information & Computer Science -- UC Irvine
Last update: 02 May 2000, 20:17:40 PDT