• The Quicksort AlgorithmThe very useful quicksort algorithm was invented by computer scientist, C.A.R. (Tony) Hoare, in 1960, while he was a visiting student at Moscow State University, working on Russian-to-English translation software. Hoare invented quicksort as a way to make the computer translation more efficient. The algorithm is now widely used, since it sorts efficiently in order O(n log n).[1] The fast Fourier transform (FFT) algorithm was invented by James Cooley and John Tukey in 1965 while Cooley was at the IBM Thomas J. Watson Research Center and Tukey was sharing his time between Bell Labs and Princeton University. Cooley and Tukey worked at separate times with John von Neumann at the Institute for Advanced Study, Princeton, New Jersey, where Tukey coined the word, "bit."

• The Fast Fourier Transform

• Lempel-Ziv Compression

• Reed–Solomon Error Correction

A drawing of an Abraxas Marginata (Lomaspilis marginata) butterfly, via Wikimedia Commons.An important part of the FFT algorithm is the "butterfly," a diagram that shows how to construct the transform from its parts. |

An excerpt from the paper of Carl Friedrich Gauss describing trigonometric transforms relevant to the Fourier transform. (Via Université du Sud-Toulon-Var). |

Reed-Solomon error correction as applied to a laser-transmitted image of the Mona Lisa. The left image shows the raw data, and the right image shows the corrected data. The image was transmitted over a range of nearly a quarter of a million miles from the Earth to Moon orbit. (NASA Goddard image by Xiaoli Sun.) |

"Because LRO is already set up to receive laser signals through the LOLA instrument, we had a unique opportunity to demonstrate one-way laser communication with a distant satellite."[7]The Mona Lisa image was contained in a 152x200 pixel array of 12 bit grayscale data. The data were sent using pulse-position modulation in which the gray value was determined by the position of the laser pulse in a time frame. The data rate was a modest 300 bits per second, but laser communication has a potential for a higher data rate than radio.[7-8,10] The Reed-Solomon coding was used to correct for transmission errors from turbulence in Earth's atmosphere.[7] Why the Mona Lisa? NASA claims it's because the Mona Lisa is an "iconic" image; and also, because people can recognize when it's been altered.[8] Another reason might be because it's in the public domain in the United States (and at the Moon?). Now that the concept of perpetual copyright has been established, it would have been impossible for NASA to have sent an image of Mickey Mouse without securing special permission.[11]

- C. A. R. Hoare, "Quicksort," Computer Journal, vol. 5, no. 1 (1962), pp. 10-16. PDF file, here.
- J.W. Cooley and J.W. Tukey, "An algorithm for the machine calculation of complex Fourier," Math. Comput., vol. 19 (1965), pp. 297-301. PDF file, here.
- Carl Friedrich Gauss, "Theoria interpolationis methodo nova tractata", Werke, Band 3, Königliche Gesellschaft der Wissenschaften, Göttingen, 1866),pp. 265-327 (5.9 MB PDF File).
- James W. Cooley and John W.Tukey, "On the Origin and Publication of the FFT Paper," Citation Classics, Current Contents, vol. 33, nos. 51-52 (December 20-27, 1993), pp. 8-9.
- J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. 23, no. 3 (May, 1977), pp. 337-343.
- Xiaoli Sun, David R. Skillman, Evan D. Hoffman, Dandan Mao, Jan F. McGarry, Leva McIntire, Ronald S. Zellar, Frederic M. Davidson, Wai H. Fong, Michael A. Krainak, Gregory A. Neumann, Maria T. Zuber and David E. Smith, "Free space laser communication experiments from Earth to the Lunar Reconnaissance Orbiter in lunar orbit," Optics Express, vol. 21, no. 2, (2013), pp. 1865-1871.
- Nancy Neal-Jones and Elizabeth Zubritsky, "NASA Beams Mona Lisa to Lunar Reconnaissance Orbiter at the Moon," NASA Goddard Press release No. 13-003, January 17, 2013
- Matthew Shaer, "Mona Lisa rides laser beams all the way to the moon: NASA," Christian Science Monitor, January 18, 2013.
- Alex Knapp, "NASA Uses Lasers To Send The Mona Lisa To The Moon," Forbes, January 18, 2013.
- Megan Garber, "We Just Sent the Mona Lisa to the Moon ... With Lasers," The Atlantic, January 17, 2013.
- Disney forced the removal of murals featuring their cartoon figures from the walls of three Florida day care centers, as discussed in this Snopes.com article.