Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The New Golden Age of Algorithms and Data Structures

Published

Author(s)

Paul E. Black

Abstract

Before 1976 Communications of the ACM printed (and numbered!) new algorithms every issue. Quicksort was invented in 1960, Boyer-Moore string search in 1977, and combsort in 1980. I haven't seen a new, general sorting algorithm in over a decade. The latest "general" data structure is the skip list, which was invented in 1990. Have all the basic, general algorithms and data structures been invented? We don't think so. With isochronous computing, heterogeneous multiprocessors, energy aware computing, wear-leveling (flash), cache and other anisotropic memory, distributed computing, streaming environments, functional languages, etc. there is a great need for research into new fundamental algorithms and data structures. As examples, we take the bulk of the time to present four which are novel and useful: reservoir sampling, majority on a stream, B-heap, and compacting and array in O(log n) time.

Keywords

algorithms, data structures

Citation

Black, P. (2012), The New Golden Age of Algorithms and Data Structures (Accessed December 10, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created October 29, 2012, Updated February 19, 2017