Classic Algorithms that Shaped Modern Computing

Throughout history, ingenious computer algorithm designs have transformed computing technology. By exploiting standard operators in conventional computers, many efficient functions have been created, leading to the complexity and diversity of modern software and driving rapid advancement in the digital age.

Compression Technology

Huffman Coding

Huffman coding is widely used in lossless data compression. Proposed by David Huffman in 1951, it builds a binary tree based on character frequencies to generate the most efficient binary codes, forming the basis of many compression schemes such as DEFLATE (used in PKZIP) and multimedia codecs like JPEG and MP3.

Cryptography

Public‑Key Encryption

Public‑key encryption uses a pair of keys: a public key for encrypting data or verifying signatures, and a private key for decryption or signing. Although publicly described in 1997, the method was originally devised in 1973 by James H. Ellis, Clifford Cocks, and Malcolm Williamson at the UK’s GCHQ.

Search Algorithms

Dijkstra's Shortest‑Path Algorithm

Developed by Edsger Dijkstra in 1956, this graph algorithm finds the shortest path in a directed graph and can also construct a shortest‑path tree, serving as a foundation for many routing and path‑selection techniques.

Binary Search Algorithm

Binary search efficiently locates a key in a sorted array by repeatedly halving the search interval, a technique useful for dictionaries, phone books, and any ordered data set.

Sorting Algorithms

Quick Sort

Invented by Tony Hoare in 1960, quicksort was originally created to reorder words for translation purposes. It became famous as the default sorting routine in Unix and is exposed in the C standard library as the function qsort .

Mathematical Methods

Karatsuba Fast Multiplication

Proposed by Anatolii Karatsuba in 1962, this algorithm reduces the number of elementary multiplications needed for large integer multiplication, paving the way for faster methods such as Toom–Cook and Schönhage–Strassen.

Euclidean Algorithm (Greatest Common Divisor)

The Euclidean algorithm computes the greatest common divisor of two integers using repeated subtraction or modulo operations. Attributed to Euclid around 300 BC, it remains a cornerstone of many higher‑level algorithms.

Graphics Development

Bresenham's Line Algorithm

Created by Jack Bresenham in 1962 while at IBM, this integer‑only algorithm draws straight lines on raster displays using only addition, subtraction, and bit‑shifts. Its simplicity led to extensions for circles and remains integral to hardware graphics pipelines.

Fast Inverse Square‑Root Algorithm

This technique provides a rapid approximation of 1/√x, crucial for real‑time 3D rendering where millions of such calculations are required per second. Although often associated with John Carmack, earlier implementations existed at SGI and 3dfx, with Gary Tarolli’s version predating its popularization in 2002.

Click “ Read Original ” for the full source.