Search⌘ K
AI Features
Home
Courses
Mastering Algorithms for Problem Solving in Java

What is an Algorithm?

Explore the definition and characteristics of an algorithm, including a practical example and its historical background. Understand how algorithms are precise, unambiguous instructions designed to solve specific problems, and discover the origins of the term from early mathematical practices.

We'll cover the following...

Algorithm

An algorithm is an explicit, precise, unambiguous, mechanically-executable sequence of elementary instructions, usually intended to accomplish a specific purpose. For example, here is an algorithm for singing that annoying song “99 Bottles of Beer on the Wall” for arbitrary values of 99:

Algorithm

BottlesofBeer(n)‾    For i←n down to 1Sing “i bottles of beer on the wall, i bottles of beer,”Sing “Take one down, pass it around, i−1 bottles of beer on the wall.”Sing “No bottles of beer on the wall, no bottles of beer,”Sing “Go to the store, buy some more, n bottles of beer on the wall.”\underline{Bottles of Beer(n)} \\ \space\space\space\space For\space i ←n\space down\space to\space 1\\ \hspace{1cm} Sing\space “i\space bottles\space of\space beer\space on\space the\space wall,\space i\space bottles\space of\space beer,” \\ \hspace{1cm} Sing\space “Take\space one\space down,\space pass\space it\space around,\space i − 1\space bottles\space of\space beer\space on\space the\space wall.” \\ \hspace{0.35cm} Sing\space “No\space bottles\space of\space beer\space on\space the\space wall,\space no\space bottles\space of\space beer,” \\ \hspace{0.35cm} Sing\space “Go\space to\space the\space store,\space buy\space some\space more,\space n\space bottles\space of\space beer\space on\space the\space wall.”

Implementation

Java
public class BottlesOfBeer {
    public static void main(String[] args) {
        bottlesOfBeer(99);
    }
    
    public static void bottlesOfBeer(int n) {
        for (int i = n; i >= 1; i--) {
            System.out.println(i + " bottles of beer on the wall, " + i + " bottles of beer,");
            System.out.println("Take one down, pass it around, " + (i-1) + " bottles of beer on the wall.\n");
        }
        
        System.out.println("No bottles of beer on the wall, no bottles of beer.");
        System.out.println("Go to the store, buy some more, " + n + " bottles of beer on the wall.");
    }
}

Explanation

  • Line 1: This line starts the definition of a new class called BottlesOfBeer. The class will contain the main method that runs the program.
  • Line 3: This line calls the bottlesOfBeer method with an argument of 99.
  • Line 7: This line begins a for loop that iterates from n down to 1. The int i = n statement initializes a loop variable called i to the value of n. The loop will continue as long as i is greater than or equal to 1. The i-- statement decrements i by 1 after each iteration.
  • Lines 8–9: These lines print the lyrics of the song.

Etymology of the word “algorithm”

The word “algorithm” does not derive, as algorithmophobic classicists might guess, from the Greek roots arithmos (αˊϱιθμoˊς\acute{\alpha} \varrho \iota \theta \mu \acute{o}\varsigma), meaning “number,” and algos (αˊ,λγoς\overset{,}{\acute{\alpha}} \lambda \gamma o\varsigma), meaning “pain.” Rather, it is a corruption of the name of the 9th-century Persian scholar Muhammad ibn Musa al-Khwarizmi. Al-Khwarizmi is perhaps best known as the writer of the treatise Al-Kitab al-mukhtasar fıhısab al-ğabr wa’l-muqabala, from which the modern word algebra derives. In a different treatise, al-Khwarizmi described the modern decimal system for writing and manipulating numbers—in particular, the use of a small circle or sifr to represent a missing quantity—which had been developed in India several centuries earlier. The methods described in this latter treatise, using either written figures or counting stones, became known in English as algorism or augrym, and its figures became known in English as ciphers.

Although both place-value notation and al-Khwarizmi’s works were already known by some European scholars, the Hindu-Arabic numeric system was popularized in Europe by the medieval Italian mathematician and tradesman Leonardo of Pisa, better known as Fibonacci. Thanks in part to his 1202 book Liber Abaci, written figures began to replace the counting table (then known as an abacus) and finger arithmetic as the preferred platform for calculation in Europe in the 13th century—not because written decimal figures were easier to learn or use, but because they provided an audit trail. Ciphers became common in Western Europe only with the advent of movable type and truly ubiquitous only after cheap paper became plentiful in the early 19th century.

Eventually, the word algorism evolved into the modern algorithm via folk etymology from the Greek arithmos (and perhaps the previously mentioned algos). Thus, until very recently, the word algorithm referred exclusively to mechanical techniques for place-value arithmetic using Arabic numerals. People trained in the fast and reliable execution of these procedures were called algorists or computators, or, more simply, computers.