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

What is an Algorithm?

Explore the definition and purpose of algorithms, including an example to clarify precise instructions. Understand the historical development of the term algorithm from its roots in medieval mathematics and how it relates to computational problem solving in C++.

We'll cover the following...

Introduction to 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 the 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

C++
#include <iostream>
using namespace std;
void BottlesofBeer(int n)
{
	for (int i = n; i >= 1; i--)
	{
		cout << i << " bottles of beer on the wall, " << i << " bottles of beer," << endl;
		cout << "Take one down, pass it around, " << i - 1 << " bottles of beer on the wall." << endl;
		cout << endl;
	}
	cout << "No bottles of beer on the wall, no bottles of beer." << endl;
	cout << "Go to the store, buy some more, " << n << " bottles of beer on the wall." << endl;
}
int main()
{
	BottlesofBeer(99);	// Starting with 99 bottles
	return 0;
}

Explanation

  • Line 4: We define the BottlesofBeer function that takes an integer parameter n.

  • Line 6: We start a loop that will iterate from n down to 1, with i being the loop variable.

  • Lines 8–10: We print the lyrics for each verse for the current value of i, with a line break between each verse.

  • Lines 13–14: We print the last two lines of the song, indicating that no more bottles are left and suggesting to go buy more bottles.

Etymology of the word algorithm

The word algorithm doesn’t derive, as many 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’s 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 s⋅ifr\underset{\cdot}{s}ifr to represent a missing quantity—which had been developed in India several centuries earlier. The methods described in this 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 became the preferred platform for calculation in Europe in the 13th century. This wasn’t 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.