ICS 161, Winter 1996:
Design and Analysis of Algorithms
Algorithm Designers
This file lists names and (sometimes) home pages of algorithm
designers whose algorithms were discussed in the lectures.
-
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: