Sartaj Sahni

Sartaj Sahni Kumar ( born July 22, 1949 in Poona ) is an Indian- American computer scientist who is concerned with algorithms and data structures.

Sahni studied electrical engineering at the Indian Institute of Technology Kanpur (Bachelor 1970) and at Cornell University where in 1972 he took his master's degree in computer science and received his doctorate in 1973 Ellis Horowitz ( On the knapsack and other computational related problems ). In 1973 he was Assistant Professor, Associate Professor in 1977 and 1980, Professor at the University of Minnesota. Since 1990 he is professor at the University of Florida, where he was Chairman from 2001 to 2011 the computer science faculty.

Sahni dealt among other things with parallel algorithms for matrix multiplication, for example, scheduling, interconnection networks of computers and network algorithms, image processing, automated design of electronic circuits, computer-aided geometry ( Computational Geometry ), medical algorithms, especially in radiation therapy. He was a pioneer in the study of heavy - NP (NP- hard) problems and examined such issues with optimization problems, for example, in network flows, game theory and CAD and certain approximation problems. He found general methods for finding polynomzeitlicher approximation algorithms for a large class of NP- difficult problems. He was the first to subexponential algorithm for an NP- hard problem.

He is co-editor of the Journal of Parallel and Distributed Computing and editor of the International Journal of Foundations of Computer Science. He is with his teacher Ellis Horowitz author of two popular textbooks on algorithms and data structures, and received for his teaching the IEEE Taylor L. Booth Education Award.

In 2003 he received the W. Wallace McDowell Award for contributions to the theory of NP Hard and NP - complete problems. In 1988 he became a Fellow of the IEEE, the Association for Computing Machinery and the American Association for the Advancement of Science. He is a member of the European Academy of Sciences. In 2001 he received the Distinguished Alumnus Award from the Indian Institute of Technology.


  • With Ellis Horowitz Fundamentals of Computer Algorithms, Computer Science Press, Maryland 1978, new edition with Sanguthevar Rajasekaran, Freeman, 1998, 2nd edition Silicon Press 2008 (there is also a C output ), German edition algorithms. Design and Analysis, Springer 1981
  • With Horowitz Fundamentals of Data Structures, Computer Science Press 1976 Advanced Edition with Susan Anderson - Freed, Freeman 1983, 2nd edition Silicon Press ( there are also issues for C , Pascal and Turbo Pascal ) German edition: Fundamentals of Data Structures in C, Redline 1998