Hinc incipit algorismus. Haec algorismus ars praesens dicitur in qua
talibus indorum fruimur bis quinque �guris �. �. 8. �. 6. �. �. �. �. �.
— Friar Alexander de Villa Dei, Carmen de Algorismo (c. ����)You are right to demand that an artist engage his work consciously,
but you confuse two different things:
solving the problem and correctly posing the question.
— Anton Chekhov, in a letter to A. S. Suvorin (October ��, �888)
The more we reduce ourselves to machines in the lower things,
the more force we shall set free to use in the higher.
— Anna C. Brackett, The Technique of Rest (�8��)And here I am at �:�� a.m. writing about technique, in spite of a strong convictionthat the moment a man begins to talk about technique that’s proof that he is freshout of ideas.
— Raymond Chandler, letter to Erle Stanley Gardner (May �, ����)Good men don’t need rules.
Today is not the day to �nd out why I have so many,— The Doctor [Matt Smith], “A Good Man Goes to War”, Doctor Who (����)�
Introduction
�.�

What is an algorithm?

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

For i

O B
(n):
n down to 1
Sing “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.”

The word “algorithm” does not derive, as algorithmophobic classicists might
guess, from the Greek roots arithmos (), meaning “number”, and algos��. I�����������

(), meaning “pain”. Rather, it is a corruption of the name of the th century
Persian scholar Muh.ammad ibn Mūsā al-Khwārizmı̄. Al-Khwārizmı̄ is perhaps
best known as the writer of the treatise Al-Kitāb al-mukhtas.ar fı̄hı̄sāb al- abr
wa’l-muqābala, from which the modern word algebra derives. In a different
treatise, al-Khwārizmı̄ described the modern decimal system for writing andmanipulating 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 orcounting 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-Khwārizmı̄’s works were alreadyknown 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 hisbookLiber 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 th century—not because written decimal figures were easier tolearn 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 th 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“Mohammad, father of Adbdulla, son of Moses, the Kwārizmian”. Kwārizm is an ancient
city, now called Khiva, in the Khorezm Province of Uzbekistan.
“The Compendious Book on Calculation by Completion and Balancing”
While it is tempting to translate the title Liber Abaci as “The Book of the Abacus”, a moreaccurate translation is “The Book of Calculation”. Both before and after Fibonacci, the Italianword abaco was used to describe anything related to numerical calculation—devices, methods,
schools, books, and so on—much in the same way that “computer science” is used today in
English, or as the Chinese phrase for “operations research” translates literally as “the study ofusing counting rods”.
+ Reckoning with digits! +The word calculate derives from the Latin word calculus, meaning “small rock”, referring to
the stones on a counting table, or as Chaucer called them, augrym stones. In, Herodotus
wrote in his Histories that “The Greeks write and calculate (, literally ‘reckon
with pebbles’) from left to right; the Egyptians do the opposite. Yet they say that their way ofwriting is toward the right, and the Greek way toward the left.” (Herodotus is strangely silent on
which end of the egg the Egyptians ate first.)
Some medieval sources claim that the Greek prefix “algo-” means “art” or “introduction”.
Others claim that algorithms were invented by a Greek philosopher, or a king of India, or perhaps
a king of Spain, named “Algus” or “Algor” or “Argus”. A few, possibly including Dante Alighieri,
even identified the inventor with the mythological Greek shipbuilder and eponymous argonaut.
It’s unclear whether any of these risible claims were intended to be historically accurate, or
merely mnemonic.

��.�. Multiplication

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.

�.�

Multiplication

Although they have been a topic of formal academic study for only a few decades,
algorithms have been with us since the dawn of civilization. Descriptions ofstep-by-step arithmetic computation are among the earliest examples of written
human language, long predating the expositions by Fibonacci and al-Khwārizmı̄,or even the place-value notation they popularized.

Lattice Multiplication
The most familiar method for multiplying large numbers, at least for American
students, is the lattice algorithm. This algorithm was popularized by Fibonacci
in Liber Abaci, who learned it from Arabic sources including al-Khwārizmı̄, whoin turn learned it from Indian sources including Brahmagupta’s th-century
treatise Brāhmasphut.asiddhānta, who may have learned it from Chinese sources.
The oldest surviving descriptions of the algorithm appear in The Mathematical
Classic of Sunzi, written in China between the rd and th centuries, and in
Eutocius of Ascalon’s commentaries on Archimedes’ Measurement of the Circle,
written around, but there is evidence that the algorithm was known muchearlier. Eutocius credits the method to a lost treatise of Apollonius of Perga,
who lived around, entitled Okytokion (). The Sumerians
recorded multiplication tables on clay tablets as early as, suggestingthat they may have used the lattice algorithm.
The lattice algorithm assumes that the input numbers are represented as
explicit strings of digits; I’ll assume here that we’re working in base ten, but thealgorithm generalizes immediately to any other base. To simplify notation, theLiterally “medicine that promotes quick and easy childbirth”! Pappus of Alexandria reproduced several excerpts of Okytokion about
years before Eutocius, but his description of thelattice multiplication algorithm (if he gave one) is also lost.
There is ample evidence that ancient Sumerians calculated accurately with extremely
large numbers using their base- place-value numerical system, but I am not aware of any
surviving record of the actual methods they used. In addition to standard multiplication
and reciprocal tables, tables listing the squares of integers from 1 to 59 have been found,leading some math historians to conjecture that Babylonians multiplied using an identity likex y = ((x + y)2 x 2 y 2 )/2. But this trick only works when x + y < 60; history is silent on how
the Babylonians might have computed x 2 when x 60.
but at the risk of inflaming the historical enmity between Greece and Egypt, or Lilliput and
Blefuscu, or Macs and PCs, or people who think zero is a natural number and people who are
wrong

�

�. I�����������

input consists of a pair of arrays X [0 .. m 1] and Y [0 .. n 1], representing thenumbers
m
n 1
X1
X
i
x=
X [i] · 10 and y =Y [ j] · 10 j ,
i=0

j=0

and similarly, the output consists of a single array Z[0 .. m + n
the productm+nX1
z=x·y=
Z[k] · 10k .

1], representing

k=0

The algorithm uses addition and single-digit multiplication as primitive operations. Addition can be performed using a simple for-loop. In practice, single-digit
multiplication is performed using a lookup table, either carved into clay tablets,
painted on strips of wood or bamboo, written on paper, stored in read-only
memory, or memorized by the computator. The entire lattice algorithm can besummarized by the formula
x·y =

m
n 1
X1 X
i=0 j=0

X [i] · Y [ j] · 10i+ j .

Different variants of the lattice algorithm evaluate the partial products X [i] ·Y [ j] · 10i+ j in different orders and use different strategies for computing theirsum. For example, in Liber Abaco, Fibonacci describes a variant that considers
the mn partial products in increasing order of significance, as shown in modern
pseudocode below.
FM(X [0 .. m 1], Y [0 .. nhold 0for k
0 to n + m 1
for all i and j such that i + j = khold hold + X [i] · Y [ j]Z[k] hold mod 10
hold bhold/10c
return Z[0 .. m + n 1]

1]):

Fibonacci’s algorithm is often executed by storing all the partial products in a
two-dimensional table (often called a “tableau” or “grate” or “lattice”) and thensumming along the diagonals with appropriate carries, as shown on the right inFigure . . American elementary-school students are taught to multiply one
factor (the “multiplicand”) by each digit in the other factor (the “multiplier”),
writing down all the multiplicand-by-digit products before adding them up, asshown on the left in Figure . . This was also the method described by Eutocius,although he fittingly considered the multiplier digits from left to right, as shown��.�. Multiplicationin Figure . . Both of these variants (and several others) are described andillustrated side by side in the anonymous
textbook L’Arte dell’Abbaco, also
known as the Treviso Arithmetic, the first printed mathematics book in the West.

Figure �.�. Computing ��� ⇥ ��� = �����6 using “long" multiplication (with error-checking by castingout nines) and “lattice" multiplication, from L’Arte dell’Abbaco (���8). (See Image Credits at the end of
the book.)�Figure �.�. Eutocius’s 6th-century calculation of ���� 8� ⇥ ���� 8� = ����8�� 6�
, in his commentary on
Archimedes’ Measurement of the Circle, transcribed (left) and translated into modern notation (right) by
Johan Heiberg (�8��). (See Image Credits at the end of the book.)

All of these variants of the lattice algorithm—and other similar variants
described by Sunzi, al-Khwārizmı̄, Fibonacci, L’Arte dell’Abbaco, and many othersources—compute the product of any m-digit number and any n-digit numberin O(mn) time; the running time of every variant is dominated by the numberof single-digit multiplications.

Duplation and Mediation
The lattice algorithm is not the oldest multiplication algorithm for which wehave direct recorded evidence. An even older and arguably simpler algorithm,
which does not rely on place-value notation, is sometimes called Russian peasantmultiplication, Ethiopian peasant multiplication, or just peasant multiplication.A��. I�����������

variant of this algorithm was copied into the Rhind papyrus by the Egyptian
scribe Ahmes around, from a document he claimed was (then) about
years old. This algorithm was still taught in elementary schools in Eastern
Europe in the late th century; it was also commonly used by early digitalcomputers that did not implement integer multiplication directly in hardware.
The peasant multiplication algorithm reduces the difficult task of multiplying
arbitrary numbers to a sequence of four simpler operations: ( ) determining
parity (even or odd), ( ) addition, ( ) duplation (doubling a number), and ( )mediation (halving a number, rounding down).
PM(x, y):
prod 0while x > 0
if x is odd
prod prod + y
x
bx/2c
y
y+y
return prod

x

y

123
61
30
15
7
3
1

+ 456
+ 912
1824
+ 3648+ 7296+ 14592+ 29184

=
=

prod
0
456
1368

=
=
=
=

5016
12312
26904
56088

Figure �.�. Multiplication by duplation and mediation

The correctness of this algorithm follows by induction from the following
recursive identity, which holds for all non-negative integers x and y:
8><0x · y = bx/2c · ( y + y)>:bx/2c · ( y + y) + y

if x = 0
if x is even
if x is odd

Arguably, this recurrence is the peasant multiplication algorithm. Don’t let theiterative pseudocode fool you; the algorithm is fundamentally recursive!
As stated, PMperforms O(log x) parity, addition, and mediation operations, but we can improve this bound to O(log min{x, y}) by swapping
the two arguments when x > y. Assuming the numbers are represented using any reasonable place-value notation (like binary, decimal, Babylonian
hexagesimal, Egyptian duodecimal, Roman numeral, Chinese counting rods,
bead positions on an abacus, and so on), each operation requires at mostO(log(x y)) = O(log max{x, y}) single-digit operations, so the overall running
time of the algorithm is O(log min{x, y} · log max{x, y}) = O(log x · log y).
The version of this algorithm actually used in ancient Egypt does not use mediation orparity, but it does use comparisons. To avoid halving, the algorithm pre-computes two tables
by repeated doubling: one containing all the powers of 2 not exceeding x, the other containing
the same powers of 2 multiplied by y. The powers of 2 that sum to x are then found by greedy
subtraction, and the corresponding entries in the other table are added together to form theproduct.

6

�.�. Multiplication

In other words, this algorithm requires O(mn) time to multiply an m-digit
number by an n-digit number; up to constant factors, this is the same running
time as the lattice algorithm. This algorithm requires (a constant factor!) more
paperwork to execute by hand than the lattice algorithm, but the necessary
primitive operations are arguably easier for humans to perform. In fact, the twoalgorithms are equivalent when numbers are represented in binary.

Compass and Straightedge
Classical Greek geometers identified numbers (or more accurately, magnitudes)with line segments of the appropriate length, which they manipulated using two
simple mechanical tools—the compass and the straightedge—versions of which
had already been in common use by surveyors, architects, and other artisans for
centuries. Using only these two tools, these scholars reduced several complex
geometric constructions to the following primitive operations, starting with one
or more identified reference points.
• Draw the unique line passing through two distinct identified points.
• Draw the unique circle centered at one identified point and passing throughanother.
• Identify the intersection point (if any) of two lines.
• Identify the intersection points (if any) of a line and a circle.
• Identify the intersection points (if any) of two circles.
In practice, Greek geometry students almost certainly drew their constructions
on an abax (), a table covered in dust or sand. Centuries earlier, Egyptian
surveyors carried out many of the same constructions using ropes to determine
straight lines and circles on the ground. However, Euclid and other Greek
geometers presented compass and straightedge constructions as precise mathematical abstractions—points are ideal points; lines are ideal lines; and circles
are ideal circles.
Figure . shows an algorithm, described in Euclid’s Elements about
years ago, for multiplying or dividing two magnitudes. The input consists offour distinct points A, B, C, and D, and the goal is to construct a point Z suchthat |AZ| = |AC||AD|/|AB|. In particular, if we define |AB| to be our unit oflength, then the algorithm computes the product of |AC| and |AD|.
Notice that Euclid first defines a new primitive operation R
Aby(as modern programmers would phrase it) writing a subroutine. The correctness
The written numerals through were known in Europe at least two centuries before
Fibonacci’s Liber Abaci as “gobar numerals”, from the Arabic word ghubār meaning dust, ultimately
referring to the Indian practice of performing arithmetic on tables covered with sand. The Greek
wordis the origin of the Latin abacus, which also originally referred to a sand table.
Remember what “geometry” means? Democritus would later refer to these Egyptian
surveyors, somewhat derisively, as arpedonaptai (), meaning “rope-fasteners”.

��. I�����������

hhConstruct the line perpendicular to ` passing through P .ii
RA(`, P):
Choose a point A 2 `
A, B
I
(C
(P, A), `)
C, D
I
(C
(A, B), C(B, A))
return L(C, D)
hhConstruct a point Z such that |AZ| = |AC||AD|/|AB|.ii
M
O D(A, B, C, D):↵ R
A(L(A, C), A)E
I(C(A, B), ↵)F
I(C(A, D), ↵)R
A(L(E, C), F )RA( , F)
return I( ,L(A, C))

Z

C
D
B
β
A

E

F

α
γ

Figure �.�. Multiplication by compass and straightedge.

of the algorithm follows from the observation that triangles A C E and A Z F
are similar. The second and third lines of the main algorithm are ambiguous,
because ↵ intersects any circle centered at A at two distinct points, but thealgorithm is actually correct no matter which intersection points are chosen
for E and F .
Euclid’s algorithm reduces the problem of multiplying two magnitudes(lengths) to a series of primitive compass-and-straightedge operations. These
operations are difficult to implement precisely on a modern digital computer, but
Euclid’s algorithm wasn’t designed for a digital computer. It was designed for the
Platonic Ideal Geometer, wielding the Platonic Ideal Compass and the Platonic
Ideal Straightedge, who could execute each operation perfectly in constant timeby definition. In this model of computation, M
O Druns in O(1)
time!

�.�

Congressional Apportionment

Here is another real-world example of an algorithm of significant politicalimportance. Article I, Section of the United States Constitution requires that
Representatives and direct Taxes shall be apportioned among the several
States which may be included within this Union, according to their respective
Numbers. . . . The Number of Representatives shall not exceed one for every
thirty Thousand, but each State shall have at Least one Representative. . . .

Because there are only a finite number of seats in the House of Representatives,
exact proportional representation requires either shared or fractional representatives, neither of which are legal. As a result, over the next several decades,
many different apportionment algorithms were proposed and used to roundthe ideal fractional solution fairly. The algorithm actually used today, called8�.�. Congressional Apportionment

the Huntington-Hill method or the method of equal proportions, was firstsuggested by Census Bureau statistician Joseph Hill in, refined by Harvard
mathematician Edward Huntington in, adopted into Federal law ( U.S.C.
§ a) in, and survived a Supreme Court challenge in.
The Huntington-Hill method allocates representatives to states one at atime. First, in a preprocessing stage, each state is allocated one representative.
Then in each iteration of the main loop, the next representative is assigned
to the statep with the highest priority. The priority of each state is defined
to be P/ r(r + 1), where P is the state’s population and r is the number ofrepresentatives already allocated to that state.
The algorithm is described in pseudocode in Figure . . The input consists ofan array Pop[1 .. n] storing the populations of the n states and an integer R equal
to the total number of representatives; the algorithm assumes R n. (Currently,
in the United States, n = 50 and R = 435.) The output array Rep[1 .. n] records
the number of representatives allocated to each state.
A

PQ

N

C

P

(Pop[1 .. n], R):Q

hhGive every state its �rst representativeii
for s
1 to nRep[s] 1
p
I
PQ, s, Pop[i]/ 2
hhAllocate the remaining n R representativesii
for i
1 to n R
sE
M (PQ)
Rep[s] Rep[s] + p
1priority Pop[s]Rep[s] (Rep[s] + 1)
I
(PQ, s, priority)
return Rep[1 .. n]Figure �.�. The Huntington-Hill apportionment algorithm

This implementation of Huntington-Hill uses a priority queue that supports
the operations N P
Q,I, and E
M . (The actual
law doesn’t say anything about priority queues, of course.) The output of thealgorithm, and therefore its correctness, does not depend at all on how thisOverruling an earlier ruling by a federal district court, the Supreme Court unanimously
held that any apportionment method adopted in good faith by Congress is constitutional (UnitedStates Department of Commerce v. Montana). The current congressional apportionment algorithm
is described in gruesome detail at the U.S. Census Department web site http://www.census.gov/
topics/public-sector/congressional-apportionment.html. A good history of the apportionment
problem can be found at http://www.thirty-thousand.org/pages/Apportionment.htm. A reportby the Congressional Research Service describing various apportionment methods is available at
http://www.fas.org/sgp/crs/misc/R
.pdf.

�

�. I�����������

priority queue is implemented. The Census Bureau uses a sorted array, stored
in a single column of an Excel spreadsheet, which is recalculated from scratchat every iteration. You (should have) learned a more efficient implementation
in your undergraduate data structures class.
Similar apportionment algorithms are used in multi-party parliamentaryelections around the world, where the number of seats allocated to each party
is supposed to be proportional to the number of votes that party receives. The
two most common are the D’Hondt method and the Webster–Sainte-Laguë
method, which respectively use priorities P/(r + 1) and P/(2r + 1) in place ofthe square-root expression in Huntington-Hill. The Huntington-Hill method isessentially unique to the United States House of Representatives, thanks in partto the constitutional requirement that each state must be allocated at least one
representative.

�.�

A Bad Example

As a prototypical example of a sequence of instructions that is not actually analgorithm, consider "Martin’s algorithm”:
B AM
A N
P T
( ):
Get a million dollars.
If the tax man comes to your door and says, “You have never paid taxes!”
Say “I forgot.”

Pretty simple, except for that first step; it’s a doozy! A group of billionaire CEOs,
Silicon Valley venture capitalists, or New York City real-estate hustlers might
consider this an algorithm, because for them the first step is both unambiguous
and trivial, but for the rest of us poor slobs, Martin’s procedure is too vague tobe considered an actual algorithm. On the other hand, this is a perfect example
of a reduction—it reduces the problem of being a millionaire and never paying
taxes to the “easier” problem of acquiring a million dollars. We’ll see reductions
over and over again in this book. As hundreds of businessmen and politicians
have demonstrated, if you know how to solve the easier problem, a reduction
tells you how to solve the harder one.
developed by Thomas Jefferson in, used for U.S. Congressional apportionment fromto, rediscovered by Belgian mathematician Victor D’Hondt in, and refined by Swiss
physicist Eduard Hagenbach-Bischoff in.
developed by Daniel Webster in, used for U.S. Congressional apportionment fromto, rediscovered by French mathematician André Sainte-Laguë in, and rediscoveredagain by German physicist Hans Schepers in.
Steve Martin, “You Can Be A Millionaire”, Saturday Night Live, January ,. Alsoappears on Comedy Is Not Pretty, Warner Bros. Records,.
Something something secure quantum blockchain deep-learning something.

���.�. Describing Algorithms

Martin’s algorithm, like some of our previous examples, is not the kindof algorithm that computer scientists are used to thinking about, because itis phrased in terms of operations that are difficult for computers to perform.
This book focuses (almost!) exclusively on algorithms that can be reasonably
implemented on a standard digital computer. Each step in these algorithms
is either directly supported by common programming languages (such asarithmetic, assignments, loops, or recursion) or something that you’ve alreadylearned how to do (like sorting, binary search, tree traversal, or singing “nBottles of Beer on the Wall”).

�.�

Describing Algorithms

The skills required to effectively design and analyze algorithms are entangledwith the skills required to effectively describe algorithms. At least in my classes,
a complete description of any algorithm has four components:• What: A precise specification of the problem that the algorithm solves.
• How: A precise description of the algorithm itself.
• Why: A proof that the algorithm solves the problem it is supposed to solve.
• How fast: An analysis of the running time of the algorithm.
It is not necessary (or even advisable) to develop these four components in thisparticular order. Problem specifications, algorithm descriptions, correctness
proofs, and time analyses usually evolve simultaneously, with the developmentof each component informing the development of the others. For example,
we may need to tweak the problem description to support a faster algorithm,
or modify the algorithm to handle a tricky case in the proof of correctness.
Nevertheless, presenting these components separately is usually clearest for thereader.
As with any writing, it’s important to aim your descriptions at the rightaudience; I recommend writing for a competent but skeptical programmer who
is not as clever as you are. Think of yourself six months ago. As you develop any
new algorithm, you will naturally build up lots of intuition about the problem
and about how your algorithm solves it, and your informal reasoning will be
guided by that intuition. But anyone reading your algorithm later, or the code
you derive from it, won’t share your intuition or experience. Neither will yourcompiler. Neither will you six months from now. All they will have is yourwritten description.
Even if you never have to explain your algorithms to anyone else, it’s still
important to develop them with an audience in mind. Trying to communicate
clearly forces you to think more clearly. In particular, writing for a novice
audience, who will interpret your words exactly as written, forces you to work���. I�����������

through fine details, no matter how “obvious” or “intuitive” your high-level ideas
may seem at the moment. Similarly, writing for a skeptical audience forces you
to develop robust arguments for correctness and efficiency, instead of trusting
your intuition or your intelligence.
I cannot emphasize this point enough: Your primary job as an algorithm
designer is teaching other people how and why your algorithms work. If
you can’t communicate your ideas to other human beings, they may as well
not exist. Producing correct and efficient executable code is an importantbut secondary goal. Convincing yourself, your professors, your (prospective)
employers, your colleagues, or your students that you are smart is at best a
distant third.

Specifying the Problem
Before we can even start developing a new algorithm, we have to agree on what
problem our algorithm is supposed to solve. Similarly, before we can even startdescribing an algorithm, we have to describe the problem that the algorithm issupposed to solve.
Algorithmic problems are often presented using standard English, in termsof real-world objects. It’s up to us, the algorithm designers, to restate these
problems in terms of formal, abstract, mathematical objects—numbers, arrays,
lists, graphs, trees, and so on—that we can reason about formally. We must also
determine if the problem statement carries any hidden assumptions, and state
those assumptions explicitly. (For example, in the song “n Bottles of Beer on theWall”, n is always a non-negative integer. )We may need to refine our specification as we develop the algorithm. For
example, our algorithm may require a particular input representation, or
produce a particular output representation, that was left unspecified in theoriginal informal problem description. Or our algorithm might actually solve amore general problem than we were originally asked to solve. (This is a common
feature of recursive algorithms.)
The specification should include just enough detail that someone else could
use our algorithm as a black box, without knowing how or why the algorithm
actually works. In particular, we must describe the type and meaning of each
input parameter, and exactly how the eventual output depends on the input
parameters. On the other hand, our specification should deliberately hide any
details that are not necessary to use the algorithm as a black box. Let that which
does not matter truly slide.
In particular, I assume that you are a skeptical novice!
pI’ve never heard anyone sing “ 2 Bottles of Beer on the Wall.” Occasionally I have heard set
theorists singing “@0 bottles of beer on the wall”, but for some reason they always gave up before
the song was over.

���.�. Describing Algorithms

For example, the lattice and duplation-and-mediation algorithms both solve
the same problem: Given two non-negative integers x and y, each represented
as an array of digits, compute the product x · y, also represented as an array ofdigits. To someone using these algorithms, the choice of algorithm is completely
irrelevant. On the other hand, the Greek straightedge-and-compass algorithm
solves a different problem, because the input and output values are represented
by line segments instead of arrays of digits.

Describing the Algorithm
Computer programs are concrete representations of algorithms, but algorithms
are not programs. Rather, algorithms are abstract mechanical proceduresthat can be implemented in any programming language that supports theunderlying primitive operations. The idiosyncratic syntactic details of yourfavorite programming language are utterly irrelevant; focusing on these will
only distract you (and your readers) from what’s really going on. A goodalgorithm description is closer to what we should write in the comments of areal program than the code itself. Code is a poor medium for storytelling.
On the other hand, a plain English prose description is usually not a good idea
either. Algorithms have lots of idiomatic structure—especially conditionals, loops,
function calls, and recursion—that are far too easily hidden by unstructured
prose. Colloquial English is full of ambiguities and shades of meaning, butalgorithms must be described as unambiguously as possible. Prose is a poor
medium for precision.
In my opinion, the clearest way to present an algorithm is using a combinationof pseudocode and structured English. Pseudocode uses the structure of formal
programming languages and mathematics to break algorithms into primitive
steps; the primitive steps themselves can be written using mathematical notation,
pure English, or an appropriate mixture of the two, whatever is clearest. Wellwritten pseudocode reveals the internal structure of the algorithm but hides
irrelevant implementation details, making the algorithm easier to understand,analyze, debug, and implement.
This is, of course, a matter of religious conviction. Armchair linguists argue incessantly over
the Sapir-Whorf hypothesis, which states (more or less) that people think only in the categories
imposed by their languages. According to an extreme formulation of this principle, some concepts
in one language simply cannot be understood by speakers of other languages, not just because oftechnological advancement—How would you translate “jump the shark” or “Fortnite streamer”
into Aramaic?—but because of inherent structural differences between languages and cultures.
For a more skeptical view, see Steven Pinker’s The Language Instinct. There is admittedly somestrength to this idea when applied to different programming paradigms. (What’s the Y combinator,
again? How do templates work? What’s an Abstract Factory?) Fortunately, those differences are
too subtle to have any impact on the material in this book. For a compelling counterexample, see
Chris Okasaki’s monograph Functional Data Structures and its more recent descendants.

���. I�����������Whenever we describe an algorithm, our description should include every
detail necessary to fully specify the algorithm, prove its correctness, and analyze
its running time. At the same time, it should exclude any details that are notnecessary to fully specify the algorithm, prove its correctness, and analyze its
running time. (Slide.) At a more practical level, our description should allow
a competent but skeptical programmer who has not read this book to quickly
and correctly implement the algorithm in their favorite programming language,
without understanding why it works.
I don’t want to bore you with the rules I follow for writing pseudocode, but
I must caution against one especially pernicious habit. Never describe repeated
operations informally, as in “Do [this] first, then do [that] second, and so on.” or“Repeat this process until [something]”. As anyone who has taken one of thosefrustrating “What comes next in this sequence?” tests already knows, describing
the first few steps of an algorithm says little or nothing about what happensin later steps. If your algorithm has a loop, write it as a loop, and explicitly
describe what happens in an arbitrary iteration. Similarly, if your algorithm isrecursive, write it recursively, and explicitly describe the case boundaries andwhat happens in each case.

�.6

Analyzing Algorithms

It’s not enough just to write down an algorithm and say “Behold!” We must also
convince our audience (and ourselves!) that the algorithm actually does what
it’s supposed to do, and that it does so efficiently.

Correctness
In some application settings, it is acceptable for programs to behave correctly
most of the time, on all “reasonable” inputs. Not in this book; we requirealgorithms that are always correct, for all possible inputs. Moreover, we must
prove that our algorithms are correct; trusting our instincts, or trying a few test
cases, isn’t good enough. Sometimes correctness is truly obvious, especiallyfor algorithms you’ve seen in earlier courses. On the other hand, “obvious”
is all too often a synonym for “wrong”. Most of the algorithms we discuss inthis course require real work to prove correct. In particular, correctness proofs
usually involve induction. We like induction. Induction is our friend.
Of course, before we can formally prove that our algorithm does what it’ssupposed to do, we have to formally describe what it’s supposed to do!

If induction is not your friend, you will have a hard time with this book.

���.6. Analyzing Algorithms

Running TimeThe most common way of ranking different algorithms for the same problem isby how quickly they run. Ideally, we want the fastest possible algorithm for any
particular problem. In many application settings, it is acceptable for programs
to run efficiently most of the time, on all “reasonable” inputs. Not in this book;
we require algorithms that always run efficiently, even in the worst case.
But how do we measure running time? As a specific example, how long does
it take to sing the song B
O B(n)? This is obviously a function of the
input value n, but it also depends on how quickly you can sing. Some singers
might take ten seconds to sing a verse; others might take twenty. Technology
widens the possibilities even further. Dictating the song over a telegraph using
Morse code might take a full minute per verse. Downloading an mp over
the Web might take a tenth of a second per verse. Duplicating the mp in acomputer’s main memory might take only a few microseconds per verse.
What’s important here is how the singing time changes as n grows. Singing
B
O B(2n) requires about twice much time as singing B
O B(n), no matter what technology is being used. This is reflected in theasymptotic singing time ⇥(n).
We can measure time by counting how many times the algorithm executes acertain instruction or reaches a certain milestone in the “code”. For example,
we might notice that the word “beer” is sung three times in every verse ofB
O B, so the number of times you sing “beer” is a good indicationof the total singing time. For this question, we can give an exact answer:
BO B(n) mentions beer exactly 3n + 3 times.
Incidentally, there are lots of songs with quadratic singing time. This one isprobably familiar to most English-speakers:
ND O C(gifts[2 .. n]):for i
1 to nSing “On the i th day of Christmas, my true love gave to me”
for j
i down to 2
Sing “ j gifts[ j],”if i > 1
Sing “and”
Sing “a partridge in a pear tree.”

The input to ND O C
is a list of n 1 gifts, represented here as
an array. It’s quite easy to show that P
the singing time is ⇥(n2 ); in particular,nthe singer mentions the name of a gift i=1 i = n(n + 1)/2 times (counting thepartridge in the pear tree). It’s also easy toPsee thatduring the first n days ofn Pi
Christmas, my true love gave to me exactly i=1 j=1 j = n(n + 1)(n + 2)/6 =⇥(n3 ) gifts.

���. I�����������

Other quadratic-time songs include “Old MacDonald Had a Farm”, “ThereWas an Old Lady Who Swallowed a Fly”, “Hole in the Bottom of the Sea”, “GreenGrow the Rushes O”, “The Rattlin’ Bog”, “The Court Of King Caractacus”,“TheBarley-Mow”, “If I Were Not Upon the Stage”, “Star Trekkin’ ”,“Ist das nicht
ein Schnitzelbank?”, “Il Pulcino Pio”, “Minkurinn í hænsnakofanum”, “Echad
Mi Yodea”, and “”. For more examples, consult your favorite
preschooler.
A(lapart[1 .. n]):Chantez « Alouette, gentille alouette, alouette, je te plumerai. »pour tout i de 1 à nChantez « Je te plumerai lapart[i]. Je te plumerai lapart[i]. »pour tout j de i à 1 hhà reboursii
Chantez « Et lapart[ j] ! Et lapart[ j] ! »Chantez « Alouette! Alouette! Aaaaaa. . . »Chantez « . . . alouette, gentille allouette, alouette, je te plumerai. »A few songs have even more bizarre singing times. A fairly modern example
is “The TELNET Song” by Guy Steele, which actually takes ⇥(2n ) time to sing
the first n verses; Steele recommended n = 4. Finally, there are some songs thatnever end.
Except for “The TELNET Song”, all of these songs are most naturally
expressed as a small set of nested loops, so their running singing times can becomputed using nested summations. The running time of a recursive algorithm ismore easily expressed as a recurrence. For example, the peasant multiplication
algorithm can be expressed recursively as follows:
8><0x · y = bx/2c · ( y + y)>:bx/2c · ( y + y) + y

if x = 0
if x is even
if x is odd

Let T (x, y) denote the number of parity, addition, and mediation operations
required to compute x · y. This function satisfies the recursive inequality
T (x, y)  T (bx/2c, 2 y) + 2 with base case T (0, y) = 0. Techniques describedin the next chapter imply the upper bound T (x, y) = O(log x).
Sometimes the running time of an algorithm depends on a particular
implementation of some underlying data structure of subroutine. For example,
the Huntington-Hill apportionment algorithm A
Cruns inO(N + RI + (R n)E) time, where N denotes the running time of N P
Q, I denotes the running time of I
, and E denotes the running timeJa, das ist Otto von Schnitzelpusskrankengescheitmeyer!
They just go on and on, my friend.

�6

Exercisesof E
M . Under the reasonable assumption that R 2n (on average,
each state gets at least two representatives), we can simplify this bound toO(N + R(I + E)). The precise running time depends on the implementationof the underlying priority queue. The Census Bureau implements the priority
queue as an unsorted array, which gives us N = I = ⇥(1) and E = ⇥(n), so the
Census Bureau’s implementation of A
Cruns in O(Rn) time.
However, if we implement the priority queue as a binary heap or a heap-ordered
array, we have N = ⇥(1) and I = E = O(log n), so the overall algorithm runs inO(R log n) time.
Finally, sometimes we are interested in computational resources other thantime, such as space, number of coin flips, number of cache or page faults, numberof inter-process messages, or the number of gifts my true love gave to me. These
resources can be analyzed using the same techniques used to analyze running
time. For example, lattice multiplication of two n-digit numbers requires O(n2 )space if we write down all the partial products before adding them, but only
O(n) space if we add them on the fly.

Exercises. Describe and analyze an efficient algorithm that determines, given a legal
arrangement of standard pieces on a standard chess board, which player will
win at chess from the given starting position if both players play perfectly.
[Hint: There is a trivial one-line solution!]™

. (a) Identify (or write) a song that requires ⇥(n3 ) time to sing the first nverses.
(b) Identify (or write) a song that requires ⇥(n log n) time to sing the firstn verses.
(c) Identify (or write) a song that requires some other weird amount oftime to sing the first n verses.
. Careful readers might complain that our analysis of songs like “n Bottles ofBeer on the Wall” or “The n Days of Christmas” is overly simplistic, because
larger numbers take longer to sing than shorter numbers. More generally,
because there are only so many words of a given length, larger sets of words
necessarily contain longer words. We can more accurately estimate singing
time by counting the number of syllables sung, rather than the number ofwords.
(a) How long does it take to sing the integer n?
Ja, das ist das Subatomarteilchenbeschleunigungsnaturmäßigkeitsuntersuchungsmaschine!

���. I�����������(b) How long does it take to sing “n Bottles of Beer on the Wall”?
(c) How long does it take to sing “The n Days of Christmas”?
As usual, express your answers in the form O( f (n)) for some function f .
. The cumulative drinking song “The Barley Mow” has been sung throughout
the British Isles for centuries. The song has many variants; Figure .
contains pseudolyrics for one version traditionally sung in Devon and
Cornwall, where vessel[i] is the name of a vessel that holds 2i ounces of
beer.
B

M

(n):

“Here’s a health to the barley-mow, my brave boys,”“Here’s a health to the barley-mow!”“We’ll drink it out of the jolly brown bowl,”“Here’s a health to the barley-mow!”“Here’s a health to the barley-mow, my brave boys,”“Here’s a health to the barley-mow!”for i

1 to n“We’ll drink it out of the vessel[i], boys,”“Here’s a health to the barley-mow!”for j

i downto 1“The vessel[ j],”“And the jolly brown bowl!”“Here’s a health to the barley-mow!”“Here’s a health to the barley-mow, my brave boys,”“Here’s a health to the barley-mow!”
Figure �.6. “The Barley Mow”.

(a) Suppose each name vessel[i] is a single word, and you can sing fourwords a second. How long would it take you to sing B
M (n)?
(Give a tight asymptotic bound.)(b) If you want to sing this song for arbitrarily large values of n, you’ll haveto make up your own vessel names. To avoid repetition, these names
must become progressively longer as n increases. Suppose vessel[n] has
In practice, the song uses some subset of the following vessels; nipperkin, quarter-gill,half-a-gill, gill, quarter-pint, half-a-pint, pint, quart, pottle, gallon, half-anker, anker, firkin,half-barrel/kilderkin, barrel, hogshead, pipe/butt, tun, well, river, and ocean. With a few
exceptions (especially at the end), every vessel in this list has twice the volume of its predecessor.
Irish and Scottish versions of the song have slightly different lyrics, and they usually switch topeople (barmaid, landlord, drayer, and so on) after “gallon”.
An early version of the song entitled “Give us once a drink” appears in the play Jack Drum’s
Entertainment (or the Comedie of Pasquill and Katherine) written by John Marston around.
(“Giue vs once a drinke for and the black bole. Sing gentle Butler bally moy!”) There is somedisagreement whether Marston wrote the “high Dutch Song” specifically for the play, whether“bally moy” is a mondegreen for “barley mow” or vice versa, or whether it’s actually the same
song at all. These discussions are best had over n bottles of beer.

�8

Exercises⇥(log n) syllables, and you can sing six syllables per second. Now how
long would it take you to sing B
M (n)? (Give a tight asymptotic
bound.)(c) Suppose each time you mention the name of a vessel, you actually drink
the corresponding amount of beer: one ounce for the jolly brown bowl,
and 2i ounces for each vessel[i]. Assuming for purposes of this problem
that you are at least years old, exactly how many ounces of beer would
you drink if you sang B
M (n)? (Give an exact answer, not justan asymptotic bound.). Recall that the input to the Huntington-Hill algorithm A
C
is an array Pop[1 .. n], where Pop[i] is the population of the ith state, and an
integer R, the total number of representatives to be allotted. The output is
an array Rep[1 .. n], where Rep[i] is the number of representatives allottedto the ith state by the algorithm.
The Huntington-Hill algorithm is sometimes described in a way thatavoids the use of priority queues entirely. The top-level algorithm “guesses”
a positive real number D, called the divisor, and then runs the following
subroutine to compute an apportionment. The variable q is the ideal quotaof representatives allocated to a state for the given divisor D; the actual
number of representatives allocated is always either dqe or bqc.
(Pop[1 .. n], R, D):0
1 to nq
Pop[i]/D
if q · q < dqe · bqc
Rep[i] bqc
else
Rep[i] dqe
reps reps + Rep[i]return reps

HHG
reps
for i

There are three possibilities for the final return value reps. If reps < R,
we did not allocate enough representatives, which (at least intuitively)means our divisor D was too small. If reps > R, we allocated too many
representatives, which (at least intuitively) means our divisor D was toolarge. Finally, if reps = R, we can return the array Rep[1 .. n] as the final
apportionment. In practice, we can compute a valid apportionment (withreps = R) by calling HHG
with a small number of integer divisors close
to the standard divisor D = P/R.
Pn
In the following problems, let P = i=1 Pop[i] denote the total population of all n states, and assume that n  R  P.
���. I�����������

(a) Show that calling HHG
with the standard divisor D = P/R does notnecessarily yield a valid apportionment.
(b) Prove that if HHG
returns the same value of reps for two different
divisors D and D0 , it also computes the same allocation Rep[1 .. n] forboth of those divisors.
(c) Prove that if HHG
returns the correct value R, it computes the same
allocation Rep[1 .. n] as our earlier algorithm A
C.
(d) Prove that a “correct” divisor D does not necessarily exist! That is,
describe inputs Pop[1 .. n] and R, where n  R  P, such that for every
real number D > 0, the number of representatives allocated by HHG
is not equal to R. [Hint: What happens if we change < to  in the
fourth line of HHG?]

��