Great Algorithms that Revolutionized Computing

The page groups several computer algorithms by area and explains what each one does in practice. It presents them as inventions that changed how computers handle compression, secure communication, search, sorting, arithmetic, and graphics.

Reading notes

#

• Huffman coding is described as a lossless compression method based on a frequency-sorted binary tree, used in DEFLATE and in codecs such as JPEG and MP3.
• Public-key cryptography uses two keys, with one key encrypting or verifying signatures and the other decrypting or creating signatures, so users can communicate securely over a public channel.
• Dijkstra’s algorithm solves the single-source shortest path problem for graphs and is widely used in routing and other graph routines.
• Binary search finds a keyword in an array sorted by key value, as in dictionaries and telephone books.
• Quick sort was developed by Tony Hoare and later became the default library sort function in Unix, where it also gave its name to qsort.
• The Karatsuba algorithm speeds up multiplication by reducing the number of digits involved, and the text mentions Toom-Cook and Schönhage-Strassen as faster generalizations for larger numbers.
• The Euclidean algorithm computes the highest common factor of two positive integers using subtraction and comparison, and is presented as an old algorithm already associated with Euclid’s Elements.
• Bresenham’s line algorithm draws lines on a computer screen using integer addition, subtraction, and bit shifting, and later extensions added functions such as drawing circles.
• Fast inverse square root gives a quick way to calculate the reciprocal of a square root and is used in 3D graphics for lighting and reflection calculations.