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 conviction that the moment a man begins to talk about technique thats proof that he is fresh out of ideas.
Raymond Chandler, letter to Erle Stanley Gardner May ,
Good men dont 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, mechanicallyexecutable sequence of elementary instructions, usually intended to accomplish a specific purpose. For example, here is an algorithm for singing that annoying songBottles of Beer on the Wall, for arbitrary values of :
BOBn: For i n down to 1
Sing i bottles of beer on the wall, i bottles of beer,
Sing Take one down, pass it around, i1 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 PersianscholarMuh.ammadibnMu sa alKhwa rizm . AlKhwa rizm isperhaps best known as the writer of the treatise AlKita b almukhta.sar f h sa b alabr walmuqa bala, from which the modern word algebra derives. In a dierent treatise, alKhwa rizmdescribed the modern decimal system for writing and manipulating numbersin particular, the use of a small circle or .sifr to represent a missing quantitywhich 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 placevalue notation and alKhwa rizm s works were already known by some European scholars, the HinduArabic numeric system was popularized in Europe by the medieval Italian mathematician and tradesman Leonardo of Pisa, better known as Fibonacci. Thanks in part to hisbook 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 th centurynot 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 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 more accurate translation is The Book of Calculation. Both before and after Fibonacci, the Italian word abaco was used to describe anything related to numerical calculationdevices, methods, schools, books, and so onmuch 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 of using 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 of writing 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. Its unclear whether any of these risible claims were intended to be historically accurate, or merely mnemonic.
to mechanical techniques for placevalue 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 of stepbystep arithmetic computation are among the earliest examples of written human language, long predating the expositions by Fibonacci and alKhwa rizm , or even the placevalue 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 alKhwa rizm , who in turn learned it from Indian sources including Brahmaguptas thcentury treatise Bra hmasphu.tasiddha 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 Ascalons commentaries on Archimedes Measurement of the Circle, written around , but there is evidence that the algorithm was known much earlier. Eutocius credits the method to a lost treatise of Apollonius of Perga, wholivedaround,entitledOkytokion. TheSumerians recorded multiplication tables on clay tablets as early as , suggesting that they may have used the lattice algorithm.
The lattice algorithm assumes that the input numbers are represented as explicit strings of digits; Ill assume here that were working in base ten, but the algorithm generalizes immediately to any other base. To simplify notation, the
Literally medicine that promotes quick and easy childbirth! Pappus of Alexandria repro duced several excerpts of Okytokion aboutyears before Eutocius, but his description of the lattice 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 placevalue 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 like x yxy2x2y22. But this trick only works when xy60; history is silent on how the Babylonians might have computed x2 when x60.
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
.. Multiplication
. I
input consists of a pair of arrays X 0 .. m1 and Y 0 .. n1, representing the
numbers
and similarly, the output consists of a single array Z 0 .. mn1, representing
the product
mXn1 k zxy Zk10 .
k0
m1 i n1 j XX
xXi10
i0 j0
and yYj10 ,
The algorithm uses addition and singledigit multiplication as primitive opera tions. Addition can be performed using a simple forloop. In practice, singledigit multiplication is performed using a lookup table, either carved into clay tablets, painted on strips of wood or bamboo, written on paper, stored in readonly memory, or memorized by the computator. The entire lattice algorithm can be summarized by the formula
m1 n1XX
xyXiYj10 i0 j0
ij
.
Dierent variants of the lattice algorithm evaluate the partial products X iYj10i j in dierent orders and use dierent strategies for computing their sum. 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.
FMX 0 .. m1, Y 0 .. n1: hold 0
for k 0 to nm1
foralliand jsuchthatijk
hold holdXiYj Zk hold mod 10
hold bhold10c return Z0..mn1
Fibonaccis algorithm is often executed by storing all the partial products in a twodimensional table often called a tableau or grate or lattice and then summing along the diagonals with appropriate carries, as shown on the right in Figure .. American elementaryschool students are taught to multiply one factor the multiplicand by each digit in the other factor the multiplier, writing down all the multiplicandbydigit products before adding them up, as shown 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
Figure .. Eutociuss 6thcentury calculation of 8, in his commentary on 8 8 6
.. Multiplication
in Figure .. Both of these variants and several others are described and illustrated side by side in the anonymoustextbook LArte dellAbbaco, also known as the Treviso Arithmetic, the first printed mathematics book in the West.
Figure .. Computing 6 using long multiplication with errorchecking by casting out nines and lattice multiplication, from LArte dellAbbaco 8. See Image Credits at the end of the book.
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 algorithmand other similar variants described by Sunzi, alKhwa rizm , Fibonacci, LArte dellAbbaco, and many other sourcescompute the product of any mdigit number and any ndigit number in Omn time; the running time of every variant is dominated by the number of singledigit multiplications.
Duplation and Mediation
The lattice algorithm is not the oldest multiplication algorithm for which we have direct recorded evidence. An even older and arguably simpler algorithm, which does not rely on placevalue notation, is sometimes called Russian peasant multiplication, 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 yearsold. ThisalgorithmwasstilltaughtinelementaryschoolsinEastern Europe in the late th century; it was also commonly used by early digital computers that did not implement integer multiplication directly in hardware.
The peasant multiplication algorithm reduces the dicult task of multiplying arbitrary numbers to a sequence of four simpler operations:determining parity even or odd,addition,duplation doubling a number, andmediation halving a number, rounding down.
PMx, y: prod 0
while x0
if x is odd
prod prody x bx2c
y yy return prod
x
123
61
30
15
7
3
1
y
456 912 182436487296 1459229184
prod
04561368
5016123122690456088
Figure .. Multiplication by duplation and mediation
The correctness of this algorithm follows by induction from the following
recursive identity, which holds for all nonnegative integers x and y:
80 if x0
xy:b x 2c yyif x is even
bx2cyyy ifxisodd
Arguably, this recurrence is the peasant multiplication algorithm. Dont let the iterative pseudocode fool you; the algorithm is fundamentally recursive!
As stated, PM performs Olog x parity, addition, and media tion operations, but we can improve this bound to Ologminx, y by swapping the two arguments when xy. Assuming the numbers are represented us ing any reasonable placevalue 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 most Ologx yOlogmaxx, y singledigit operations, so the overall running time of the algorithm is Olog min x , y log max x , y Olog xlog y .
The version of this algorithm actually used in ancient Egypt does not use mediation or parity, but it does use comparisons. To avoid halving, the algorithm precomputes 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 the product.
6
In other words, this algorithm requires Omn time to multiply an mdigit number by an ndigit 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 two algorithms 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 toolsthe compass and the straightedgeversions 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 through
another.
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 onanabax,atablecoveredindustorsand. Centuriesearlier,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 mathe matical abstractionspoints are ideal points; lines are ideal lines; and circles are ideal circles.
Figure . shows an algorithm, described in Euclids Elements aboutyears ago, for multiplying or dividing two magnitudes. The input consists of four distinct points A, B, C, and D, and the goal is to construct a point Z such that AZACADAB. In particular, if we define AB to be our unit of length, then the algorithm computes the product of AC and AD.
Notice that Euclid first defines a new primitive operation RA by as modern programmers would phrase it writing a subroutine. The correctness
The written numeralsthroughwere known in Europe at least two centuries before Fibonaccis 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 ropefasteners.
.. Multiplication
. I
hhConstruct the line perpendicular topassing through P.ii RA, P:
Choose a point A 2
A, B ICP, A,
C,D ICA,B,CB,A return LC , D
hhConstruct a point Z such that AZACADAB.ii MODA,B,C,D:
RALA, C , A
E ICA, B,
F ICA, D,
RALE,C,F
RA , F
return I, LA, C
of the algorithm follows from the observation that triangles ACE and AZF are similar. The second and third lines of the main algorithm are ambiguous, becauseintersects any circle centered at A at two distinct points, but the algorithm is actually correct no matter which intersection points are chosen for E and F.
Euclids algorithm reduces the problem of multiplying two magnitudes lengths to a series of primitive compassandstraightedge operations. These operations are dicult to implement precisely on a modern digital computer, but Euclids algorithm wasnt 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 time by definition. In this model of computation, MOD runs in O1 time!
. Congressional Apportionment
Here is another realworld example of an algorithm of significant political importance. Article I, Sectionof 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 represen tatives, neither of which are legal. As a result, over the next several decades, many dierent apportionment algorithms were proposed and used to round the ideal fractional solution fairly. The algorithm actually used today, called
AEF Figure .. Multiplication by compass and straightedge.
Z
C
D
B
8
the HuntingtonHill method or the method of equal proportions, was first suggested by Census Bureau statistician Joseph Hill in , refined by Harvard mathematician Edward Huntington in , adopted into Federal lawU.S.C. a in , and survived a Supreme Court challenge in .
The HuntingtonHill method allocates representatives to states one at a time. 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 stpate with the highest priority. The priority of each state is defined to be P rr1, where P is the states population and r is the number of representatives already allocated to that state.
The algorithm is described in pseudocode in Figure .. The input consists of an array Pop1 .. n storing the populations of the n states and an integer R equal to the total number of representatives; the algorithm assumes Rn. Currently, in the United States, n50 and R435. The output array Rep1 .. n records the number of representatives allocated to each state.
.. Congressional Apportionment
ACPop1 .. n, R: PQ NPQ
hhGive every state its rst representativeii for s 1 to n
Reps1 pI PQ, s, Popi 2
hhAllocate the remaining nR representativesii for i 1 to nR
s EMPQ
Reps Reps1
priority PopspRepsReps1 IPQ, s, priority
return Rep1 .. n
Figure .. The HuntingtonHill apportionment algorithm
This implementation of HuntingtonHill uses a priority queue that supports the operations NPQ, I, and EM. The actual law doesnt say anything about priority queues, of course. The output of the algorithm, and therefore its correctness, does not depend at all on how this
Overruling 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 United States 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 topicspublicsectorcongressionalapportionment.html. A good history of the apportionment problem can be found at http:www.thirtythousand.orgpagesApportionment.htm. A report by the Congressional Research Service describing various apportionment methods is available at http:www.fas.orgsgpcrsmiscR.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 scratch at every iteration. You should have learned a more ecient implementation in your undergraduate data structures class.
Similar apportionment algorithms are used in multiparty parliamentary elections 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 DHondt method and the WebsterSainteLague method, which respectively use priorities Pr1 and P2r1 in place of the squareroot expression in HuntingtonHill. The HuntingtonHill method is essentially unique to the United States House of Representatives, thanks in part to 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 an algorithm, consider Martins algorithm:
Pretty simple, except for that first step; its a doozy! A group of billionaire CEOs, Silicon Valley venture capitalists, or New York City realestate 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, Martins procedure is too vague to be considered an actual algorithm. On the other hand, this is a perfect example of a reductionit reduces the problem of being a millionaire and never paying taxes to the easier problem of acquiring a million dollars. Well 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 Jeerson in , used for U.S. Congressional apportionment fromto , rediscovered by Belgian mathematician Victor DHondt in , and refined by Swiss physicist Eduard HagenbachBischo in .
developed by Daniel Webster in , used for U.S. Congressional apportionment fromto , rediscovered by French mathematician Andre SainteLague in , and rediscovered again by German physicist Hans Schepers in .
Steve Martin, You Can Be A Millionaire, Saturday Night Live, January , . Also appears on Comedy Is Not Pretty, Warner Bros. Records, .
BAMANPT :
Get a million dollars.
If the tax man comes to your door and says, You have never paid taxes!
Say I forgot.
Something something secure quantum blockchain deeplearning something.
Martins algorithm, like some of our previous examples, is not the kind of algorithm that computer scientists are used to thinking about, because it is phrased in terms of operations that are dicult 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 as arithmetic, assignments, loops, or recursion or something that youve already learned how to do like sorting, binary search, tree traversal, or singing n Bottles of Beer on the Wall.
. Describing Algorithms
The skills required to eectively design and analyze algorithms are entangled with the skills required to eectively 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 this particular order. Problem specifications, algorithm descriptions, correctness proofs, and time analyses usually evolve simultaneously, with the development of 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 the reader.
As with any writing, its important to aim your descriptions at the right audience; 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, wont share your intuition or experience. Neither will your compiler. Neither will you six months from now. All they will have is your written description.
Even if you never have to explain your algorithms to anyone else, its 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
.. Describing Algorithms
. I
through fine details, no matter how obvious or intuitive your highlevel ideas may seem at the moment. Similarly, writing for a skeptical audience forces you to develop robust arguments for correctness and eciency, 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 cant communicate your ideas to other human beings, they may as well not exist. Producing correct and ecient executable code is an important but 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 start describing an algorithm, we have to describe the problem that the algorithm is supposed to solve.
Algorithmic problems are often presented using standard English, in terms of realworld objects. Its up to us, the algorithm designers, to restate these problems in terms of formal, abstract, mathematical objectsnumbers, arrays, lists, graphs, trees, and so onthat 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 the Wall, n is always a nonnegative 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 the original informal problem description. Or our algorithm might actually solve a more 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!
Ive never heard anyone sing p2 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.
For example, the lattice and duplationandmediation algorithms both solve the same problem: Given two nonnegative integers x and y, each represented as an array of digits, compute the product xy, also represented as an array of digits. To someone using these algorithms, the choice of algorithm is completely irrelevant. On the other hand, the Greek straightedgeandcompass algorithm solves a dierent 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 procedures that can be implemented in any programming language that supports the underlying primitive operations. The idiosyncratic syntactic details of your favorite programming language are utterly irrelevant; focusing on these will only distract you and your readers from whats really going on. A good algorithm description is closer to what we should write in the comments of a real 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 structureespecially conditionals, loops, function calls, and recursionthat are far too easily hidden by unstructured prose. Colloquial English is full of ambiguities and shades of meaning, but algorithms 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 combination of 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. Well written 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 SapirWhorf 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 of technological advancementHow would you translate jump the shark or Fortnite streamer into Aramaic?but because of inherent structural dierences between languages and cultures. For a more skeptical view, see Steven Pinkers The Language Instinct. There is admittedly some strength to this idea when applied to dierent programming paradigms. Whats the Y combinator, again? How do templates work? Whats an Abstract Factory? Fortunately, those dierences are too subtle to have any impact on the material in this book. For a compelling counterexample, see Chris Okasakis monograph Functional Data Structures and its more recent descendants.
.. Describing Algorithms
. 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 not necessary 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 dont 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 those frustrating What comes next in this sequence? tests already knows, describing the first few steps of an algorithm says little or nothing about what happens in 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 is recursive, write it recursively, and explicitly describe the case boundaries and what happens in each case.
.6 Analyzing Algorithms
Its 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 its supposed to do, and that it does so eciently.
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 require algorithms 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, isnt good enough. Sometimes correctness is truly obvious, especially for algorithms youve seen in earlier courses. On the other hand, obvious is all too often a synonym for wrong. Most of the algorithms we discuss in this 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 its supposed to do, we have to formally describe what its supposed to do!
If induction is not your friend, you will have a hard time with this book.
.6. Analyzing Algorithms
Running Time
The most common way of ranking dierent algorithms for the same problem is by 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 eciently most of the time, on all reasonable inputs. Not in this book; we require algorithms that always run eciently, 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 BOBn? 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 a computers main memory might take only a few microseconds per verse.
Whats important here is how the singing time changes as n grows. Singing BOB2n requires about twice much time as singing BO Bn, no matter what technology is being used. This is reflected in the asymptotic singing time n.
We can measure time by counting how many times the algorithm executes a certain 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 of BOB, so the number of times you sing beer is a good indication of the total singing time. For this question, we can give an exact answer: BOBn mentions beer exactly 3n3 times.
Incidentally, there are lots of songs with quadratic singing time. This one is probably familiar to most Englishspeakers:
NDOCgifts2 .. n:
for i
1 to n
Sing On the ith day of Christmas, my true love gave to me for j i down to 2
Singj gifts j, if i1
Sing and
Sing a partridge in a pear tree.
The input to NDOC is aPlist of n1 gifts, represented here as an array. Its quite easy to show that the singing time is n2; in particular, the singer mentions the name of a gift ni1 inn12 times counting the partridge in the pear tree. Its also easy to see that during the first n days of Christmas, my true love gave to me exactly Pni1 Pij1 jnn1n26
n3 gifts.
. I
Other quadratictime songs include Old MacDonald Had a Farm, There Was an Old Lady Who Swallowed a Fly, Hole in the Bottom of the Sea, Green Grow the Rushes O, The Rattlin Bog, The Court Of King Caractacus,The BarleyMow, If I Were Not Upon the Stage, Star Trekkin ,Ist das nicht ein Schnitzelbank?,Il Pulcino Pio, Minkurinn i hnsnakofanum, Echad Mi Yodea, and. For more examples, consult your favorite preschooler.
Alapart1 .. n:
ChantezAlouette, gentille alouette, alouette, je te plumerai.pour tout i de 1 a n
ChantezJe te plumerai laparti. Je te plumerai laparti.pour tout j de i a 1 hha reboursii
ChantezEt lapart j ! Et lapart j !
ChantezAlouette! 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 n4. Finally, there are some songs that never 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 be computed using nested summations. The running time of a recursive algorithm is more easily expressed as a recurrence. For example, the peasant multiplication algorithm can be expressed recursively as follows:
80 if x0
xy:b x 2c yyif x is even
bx2cyyy ifxisodd
Let Tx, y denote the number of parity, addition, and mediation operations required to compute xy. This function satisfies the recursive inequality Tx,yTbx2c,2y2withbasecaseT0,y0. Techniquesdescribed in the next chapter imply the upper bound Tx, yOlog x.
Sometimes the running time of an algorithm depends on a particular implementation of some underlying data structure of subroutine. For example, the HuntingtonHill apportionment algorithm AC runs in ONRIRnE time, where N denotes the running time of NP Q, I denotes the running time of I, and E denotes the running time
Ja, das ist Otto von Schnitzelpusskrankengescheitmeyer! They just go on and on, my friend.
6
of EM. Under the reasonable assumption that R2n on average, each state gets at least two representatives, we can simplify this bound to ONRIE. The precise running time depends on the implementation of the underlying priority queue. The Census Bureau implements the priority queue as an unsorted array, which gives us NI1 and En, so the Census Bureaus implementation of AC runs in ORn time. However, if we implement the priority queue as a binary heap or a heapordered array, we have N1 and IEOlog n, so the overall algorithm runs in OR log n time.
Finally, sometimes we are interested in computational resources other than time, such as space, number of coin flips, number of cache or page faults, number of interprocess 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 ndigit numbers requires On2 space if we write down all the partial products before adding them, but only On space if we add them on the fly.
Exercises
. Describe and analyze an ecient 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 oneline solution!
TM. a Identify or write a song that requires n3 time to sing the first n verses.
b Identify or write a song that requires n log n time to sing the first n verses.
c Identify or write a song that requires some other weird amount of time to sing the first n verses.
. Careful readers might complain that our analysis of songs like n Bottles of Beer 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 necessarilycontainlongerwords. Wecanmoreaccuratelyestimatesinging time by counting the number of syllables sung, rather than the number of words.
a How long does it take to sing the integer n?
Ja, das ist das Subatomarteilchenbeschleunigungsnaturmaigkeitsuntersuchungsmaschine!
Exercises
. 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 vesseli is the name of a vessel that holds 2i ounces of beer.
BMn:
Heres a health to the barleymow, my brave boys, Heres a health to the barleymow!
Well drink it out of the jolly brown bowl,
Heres a health to the barleymow!
Heres a health to the barleymow, my brave boys, Heres a health to the barleymow!
for i
1 to n
Well drink it out of the vesseli, boys, Heres a health to the barleymow!
for j i downto 1 The vesselj,
And the jolly brown bowl!
Heres a health to the barleymow!
Heres a health to the barleymow, my brave boys, Heres a health to the barleymow!
Figure .6. The Barley Mow.
a Suppose each name vesseli is a single word, and you can sing four words a second. How long would it take you to sing BMn? Give a tight asymptotic bound.
b If you want to sing this song for arbitrarily large values of n, youll have to make up your own vessel names. To avoid repetition, these names must become progressively longer as n increases. Suppose vesseln has
In practice, the song uses some subset of the following vessels; nipperkin, quartergill, halfagill, gill, quarterpint, halfapint, pint, quart, pottle, gallon, halfanker, anker, firkin, halfbarrelkilderkin, barrel, hogshead, pipebutt, 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 dierent lyrics, and they usually switch to people 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 Drums 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 some disagreement 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 its 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 BMn? 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 vesseli. Assuming for purposes of this problem that you are at leastyears old, exactly how many ounces of beer would you drink if you sang BMn? Give an exact answer, not just an asymptotic bound.
. Recall that the input to the HuntingtonHill algorithm AC is an array Pop1 .. n, where Popi is the population of the ith state, and an integer R, the total number of representatives to be allotted. The output is an array Rep1 .. n, where Repi is the number of representatives allotted to the ith state by the algorithm.
The HuntingtonHill algorithm is sometimes described in a way that avoids the use of priority queues entirely. The toplevel 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 quota of representatives allocated to a state for the given divisor D; the actual number of representatives allocated is always either dqe or bqc.
HHGPop1 .. n, R, D:
reps
else Repi bqc Repi dqe
reps repsRepi return reps
for i q
0
1 to n
PopiD
if qqdqebqc
There are three possibilities for the final return value reps. If repsR, we did not allocate enough representatives, which at least intuitively means our divisor D was too small. If repsR, we allocated too many representatives, which at least intuitively means our divisor D was too large. Finally, if repsR, we can return the array Rep1 .. n as the final apportionment. In practice, we can compute a valid apportionment with repsR by calling HHG with a small number of integer divisors close to the standard divisor DPR. Pn
In the following problems, let Pi1 Popi denote the total popula tion of all n states, and assume that nRP.
. I
a Show that calling HHG with the standard divisor DPR does not necessarily yield a valid apportionment.
b Prove that if HHG returns the same value of reps for two dierent divisors D and D0, it also computes the same allocation Rep1..n for both of those divisors.
c Prove that if HHG returns the correct value R, it computes the same allocation Rep1 .. n as our earlier algorithm AC.
d Prove that a correct divisor D does not necessarily exist! That is, describe inputs Pop1 .. n and R, where nRP , such that for every real number D0, the number of representatives allocated by HHG is not equal to R. Hint: What happens if we changetoin the fourth line of HHG?
Reviews
There are no reviews yet.