David "Dave" Musser is a professor emeritus of computer science at the Rensselaer Polytechnic Institute in Troy, New York, United States.
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate, store, and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems.
Rensselaer Polytechnic Institute, or RPI, is a private research university and space-grant institution in Troy, New York, with additional campuses in Hartford and Groton, Connecticut.
Troy is a city in the U.S. state of New York and the seat of Rensselaer County. The city is located on the western edge of Rensselaer County and on the eastern bank of the Hudson River. Troy has close ties to the nearby cities of Albany and Schenectady, forming a region popularly called the Capital District. The city is one of the three major centers for the Albany Metropolitan Statistical Area (MSA), which has a population of 1,170,483. At the 2010 census, the population of Troy was 50,129. Troy's motto is Ilium fuit. Troja est, which means "Ilium was, Troy is".
Contents
He is known for his work in generic programming, particularly as applied to C++, and his collaboration with Alexander Stepanov. Their work together includes coining the term "generic programming" in Musser & Stepanov (1989), and led to the creation of the C++ Standard Template Library (STL).
Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by ML in 1973, permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication. Such software entities are known as generics in Python, Ada, C#, Delphi, Eiffel, F#, Java, Rust, Swift, TypeScript and Visual Basic .NET. They are known as parametric polymorphism in ML, Scala, Haskell and Julia; templates in C++ and D; and parameterized types in the influential 1994 book Design Patterns.
C++ is a general-purpose programming language that was developed by Bjarne Stroustrup as an extension of the C language, or "C with Classes". It has imperative, object-oriented and generic programming features, while also providing facilities for low-level memory manipulation. It is almost always implemented as a compiled language, and many vendors provide C++ compilers, including the Free Software Foundation, Microsoft, Intel, and IBM, so it is available on many platforms.
Alexander Alexandrovich Stepanov, born November 16, 1950 in Moscow, is a Russian computer programmer, best known as an advocate of generic programming and as the primary designer and implementer of the C++ Standard Template Library, which he started to develop around 1992 while employed at HP Labs. He had earlier been working for Bell Labs close to Andrew Koenig and tried to convince Bjarne Stroustrup to introduce something like Ada generics in C++. He is credited with the notion of concept.
In Musser (1997), he developed the sorting algorithm called introsort (also known as introspective sort), and the related selection algorithm called introselect, to provide algorithms that are both efficient and have optimal worst-case performance, for use in the STL. [1]
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms which require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions:
- The output is in nondecreasing order ;
- The output is a permutation of the input.
Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since both algorithms it uses are comparison sorts, it is also a comparison sort.
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection.
In 2007 he retired from Rensselaer.
