Sartaj Sahni
Encyclopedia
Prof. Sartaj Kumar Sahni is an Indian computer scientist
, now based in the USA, and is one of the pioneers in the field of data structure
s. He is a distinguished professor in the Department of Computer and Information Science and Engineering at the University of Florida
.
from the Indian Institute of Technology Kanpur
. Following this, he did his graduate studies at Cornell University
, earning a Ph.D. in 1973 under the supervision of Ellis Horowitz.
, interconnection networks, design automation, and medical algorithms.
With his advisor Ellis Horowitz, Sahni wrote two widely-used textbooks, Fundamentals of Algorithms and Fundamentals of Data Structures. He has also written highly-cited research papers on the NP-complete
ness of approximately solving
certain optimization problems, on open shop scheduling
, on parallel algorithm
s for matrix multiplication
and their application in graph theory
, and on improved exponential time exact algorithms for the subset sum problem, among his many other research results.
's Taylor L. Booth Education Award and in 2003 he was awarded the IEEE Computer Society McDowell Award
. Sahni was also awarded the 2003 Karl V. Karlstrom Outstanding Educator Award of the Association for Computing Machinery
.
Prof. Sahni is a member of the European Academy of Sciences
. He was elected as a Fellow
of the Institute of Electrical and Electronics Engineers
in 1988, and of the Association for Computing Machinery
in 1996; he is also a fellow of the American Association for the Advancement of Science
. He is a Distinguished Alumnus of the Indian Institute of Technology, Kanpur.
Sahni was given the Honorary Professor Award of Asia University (Taiwan)
in 2009.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, now based in the USA, and is one of the pioneers in the field of data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s. He is a distinguished professor in the Department of Computer and Information Science and Engineering at the University of Florida
University of Florida
The University of Florida is an American public land-grant, sea-grant, and space-grant research university located on a campus in Gainesville, Florida. The university traces its historical origins to 1853, and has operated continuously on its present Gainesville campus since September 1906...
.
Biography
Sahni received his B.Tech. in electrical engineeringElectrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
from the Indian Institute of Technology Kanpur
Indian Institute of Technology Kanpur
The Indian Institute of Technology Kanpur is a Central deemed University located in Uttar Pradesh, about 15 km north-west of the city of Kanpur in the Kalyanpur suburb....
. Following this, he did his graduate studies at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
, earning a Ph.D. in 1973 under the supervision of Ellis Horowitz.
Research and publications
Sahni has published over two hundred and eighty research papers and written 15 textbooks. His research publications are on the design and analysis of efficient algorithms, data structures, parallel computingParallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, interconnection networks, design automation, and medical algorithms.
With his advisor Ellis Horowitz, Sahni wrote two widely-used textbooks, Fundamentals of Algorithms and Fundamentals of Data Structures. He has also written highly-cited research papers on the NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
ness of approximately solving
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
certain optimization problems, on open shop scheduling
Open Shop Scheduling
The open shop scheduling problem is a scheduling problem where, given n jobs and m workstations, each job has to visit a workstation at least once. The order in which this happens is not relevant .- NP-hardness :The OSSP can be solved in polynomial time for two machines...
, on parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s for matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
and their application in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, and on improved exponential time exact algorithms for the subset sum problem, among his many other research results.
Awards and honors
In 1997, Sahni was awarded the IEEE Computer SocietyIEEE Computer Society
The IEEE Computer Society is a professional society of IEEE. Its purpose and scope is “to advance the theory, practice, and application of computer and information processing science and technology” and the “professional standing of its members.” The CS is the largest of 38 technical societies...
's Taylor L. Booth Education Award and in 2003 he was awarded the IEEE Computer Society McDowell Award
McDowell Award
The W. Wallace McDowell Award is awarded by the IEEE Computer Society for outstanding recent theoretical, design, educational, practical, or other similar innovative contributions that fall within the scope of Computer Society interest...
. Sahni was also awarded the 2003 Karl V. Karlstrom Outstanding Educator Award of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
.
Prof. Sahni is a member of the European Academy of Sciences
European Academy of Sciences
The European Academy of Sciences has as mission to promote excellence in science and technology and their essential roles in fostering social and economic development and progress. It is registered in and operates under rules and regulations of Belgium. The European Academy of Sciences is an...
. He was elected as a Fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Institute of Electrical and Electronics Engineers
Institute of Electrical and Electronics Engineers
The Institute of Electrical and Electronics Engineers is a non-profit professional association headquartered in New York City that is dedicated to advancing technological innovation and excellence...
in 1988, and of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
in 1996; he is also a fellow of the American Association for the Advancement of Science
American Association for the Advancement of Science
The American Association for the Advancement of Science is an international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific responsibility, and supporting scientific education and science outreach for the...
. He is a Distinguished Alumnus of the Indian Institute of Technology, Kanpur.
Sahni was given the Honorary Professor Award of Asia University (Taiwan)
Asia University (Taiwan)
Asia University is a private university located in Taichung, Taiwan. It is recognized in Taiwan for its research and teaching in Health Science, Computer Science, Creative Design, Management, and Humanities & Social Sciences....
in 2009.