Turing Award Winners

Turing award for (2006) :

“In recognition of her pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution.”[1]

Contribution in Analysis of Algorithm:

“As a pioneer in compiler organization and optimization algorithms, she has made seminal contribution to the science. Her work on inter procedural analysis and automatic parallelization continue to be on the leading edge of compiler research. She has successfully reduced this science to practice through the transfer of this technology to products such as the STRETCH HARVEST Compiler, the COBOL Compiler, and the Parallel FORTRAN Product.”[2]

References:

[1] http://en.wikipedia.org/wiki/Frances_E._Allen
[2] http://www-03.ibm.com/ibm/history/witexhibit/wit_hall_allen.html

Turing award for (1995) :

“In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking.”[1]

Contribution in Analysis of Algorithm:

“The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan”[3]

References:

[1] http://en.wikipedia.org/wiki/Turing_Award

[2] http://awards.acm.org/citation.cfm?id=4659082&srt=alpha&alpha=B&aw=140&ao=AMTURING

[3] Introduction to Algorithms - Second Edition
Cormen, Leiserson, Rivest, and Stein- page 195.

Turing award for (1986) :

“fundamental achievements in the design and analysis of algorithms and data structures.”[2]

Contribution in Analysis of Algorithm:

“Some of his well-known algorithms:

• Tarjan’s off-line least common ancestors algorithm -used to compute the lowest common ancestors for pairs of nodes in a tree.
• Tarjan’s strongly connected components algorithm -used to compute the strongly connected components of a graph.
• The Hopcroft-Tarjan planarity algorithm was the first linear-time algorithm for planarity-testing.
• Important data structures such as the Fibonacci heap.
• The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan”[1]

Related links:

http://www.cs.princeton.edu/~ret/

http://projects.csail.mit.edu/jacm/Authors/tarjanrobertendre.html

References:

[1] http://en.wikipedia.org/wiki/Robert_Tarjan

[2] http://en.wikipedia.org/wiki/Turing_Award

Turing award for (1985):

“contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness.”[1]

Contribution in Analysis of Algorithm:

Introduced the standard methodology for proving problems to be NP-complete.

Related links:

http://www.cs.berkeley.edu/~karp/

References:

[1] http://en.wikipedia.org/wiki/Turing_Award

[2] http://en.wikipedia.org/wiki/Richard_M._Karp

Turing award for (2002) :

“For their ingenious contribution for making public-key cryptography useful in practice.”[1]

Contribution in Analysis of Algorithm:

The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan

Related links:

http://people.csail.mit.edu/rivest/

http://www.pbase.com/ralf/adi_shamir

http://www.usc.edu/dept/molecular-science/fm-adleman.htm

References:

[1] http://en.wikipedia.org/wiki/Turing_Award

Turing award for (1982) :

His discovery of the greatest open quesiton - “whether complexity classes P and NP are equivalent.”[1]

Contribution in Analysis of Algorithm:

Proof of boolean satisfiability is NP-complete.

Related links:

http://www.nserc.gc.ca/news/2006/p060214_cook.htm

References:

[1] http://en.wikipedia.org/wiki/Stephen_A._Cook

Turing award for (1974) :

“Major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the “art of computer programming” through his well-known books in a continuous series by this title.”[3]

Contribution in Analysis of Algorithm:

“Knuth has been called the “father” of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.”[2]

Related links:

http://www-cs-faculty.stanford.edu/~knuth/index.html

References:

[1] http://awards.acm.org/citation.cfm?id=7143252&srt=all&aw=140&ao=AMTURING

[2]  http://en.wikipedia.org/wiki/Donald_Knuth

[3] http://en.wikipedia.org/wiki/Turing_Award

Turing award for (1972) :

“Fundamental contributions in the area of programming languages.”[1]

Contribution in Analysis of Algorithm:

Dijkstra’s algorithm to find shortest path in a graph.

References

[1] http://en.wikipedia.org/wiki/Edsger_W._Dijkstra

Turing award for (1978) :

“having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms”[1]

Contribution in Analysis of Algorithm:

Floyd’s algorithm to find all shortest path in a graph.

The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan

Related Links:

http://sigact.acm.org/floyd/

References

[1] http://en.wikipedia.org/wiki/Turing_Award

[2] http://en.wikipedia.org/wiki/Robert_Floyd