Thiện gửi bài

ALGORITHMS
(Thuật toán)
ROBERT SEDGEWICK
BROWN UNIVERSITY


Preface (Lời nói đầu)
This book is intended(dùng để) to survey(nghiên cứu) the most important algorithms in use on computers today and to teach fundamental(qui tắc cơ bản) techniques(kỉ thuật) to the growing number of people who are interested in becoming serious computer users. It is appropriate(thích hợp) for use as a textbook(sách giáo khoa) for a second, third or fourth course in computer science: after students have acquired(có được) some programming skills(kĩ năng lập trình) and familiarity(quen thuộc) with computer systems, but before they have specialized(chuyên môn) courses in advanced areas of computer science or computer pplications. Additionally(ngoài ra), the book may be useful as a reference(tham khảo) for those who already have some familiarity with the material(tài liệu), since it contains(bao gồm) a number of computer implementations(thi hành) of useful algorithms.
The book consists of(gồm có) forty chapters which are grouped into seven major(chuyên đề)
parts: -mathematical algorithms (thuật toán toán học)
-sorting (sắp xếp)
-searching (tìm kiếm)
-string processing (xử lý chuỗi)
-geometric (hình học)
-algorithms (thuật toán)
-graph algorithms and advanced topics. (thuật toán đồ thị và …)
A major goal in the development of this book has been to bring together the fundamental(qui tắc cơ bản) methods from these diverse(thay đổi khác nhau) areas, in order to provide access to the best methods that we know for solving problems by computer for as many people as possible(có thể). The treatment(bàn luận, nghiên cứu,giải quyết) of sorting, searching and string processing (which may not be covered(bao trùm) in other courses) is somewhat(có phần, 1 chút) more complete than the treatment of mathematical algorithms (which may be covered in more depth in applied(ứng dụng) mathematics or engineering courses), or geometric and graph algorithms (which may be covered in more depth in advanced computer science
courses). Some of the chapters involve introductory(để giới thiệu) treatment of advanced material(tài liệu cao cấp). It is hoped that the descriptions here can provide students with some understanding of the basic properties of fundamental algorithms(thuật toán cơ bản) such as the FFT or the simplex(đơn hình) method, while at the same time preparing them to better appreciate(đánh giá) the methods when they learn them in advanced courses.
The orientation(định hướng) of the book is towards(nhằm) algorithms that are likely to be of practical use. The emphasis(tầm quan trọng) is on teaching students the tools of their trade to the point that they can confidently(tin tưởng) implement(phương tiện), run and debug useful algorithms. Full implementations(sự thi hành) of the methods discussed (in an actual (hiện tại) programming language) are included in the text, along with (cùng với) descriptions of the operations(phép toán) of these programs on a consistent(nhất quán) set of examples. Though not emphasized(nhấn mạnh), connections to theoretical(lý thuyết) computer science and the analysis(phân tích) of algorithms are not ignored(lờ đi). When appropriate, analytic(phân tích) results are discussed to illustrate(minh họa) why certain(chắc chắn) algorithms are preferred(đc ưu tiên). When interesting, the relationship of the practical algorithms being discussed to purely(chỉ là) theoretical(lý thuyết) results is described. More information of the orientation(định hướng) and coverage(việc đưa tin về những sự kiện) of the material in the book may be found in the Introduction which follows. One or two previous courses in computer science are recommended(giới thiệu) for students to be able to appreciate(hiểu rõ) the material in this book: one course in programming in a high-level language such as Pascal, and perhaps another course which teaches fundamental(cơ bản) oncepts(khái niệm) of programming systems. In short, students should be conversant with(thông thạo với) a modern programming language and have a comfortable understanding of the basic features(đặc trưng) of modern computer systems. There is some mathematical material which requires(đòi hỏi, yêu cầu) nowledge of calculus, but this is isolated(cô lập) within a few chapters and could be skipped(nhảy qua). There is a great deal of (nhiều) flexibility(linh động) in the way that the material in the book can be taught. To a large extent(quy mô), the individual(riêng lẻ) chapters in the book can each be read independently of the others. The material can be adapted(thích nghi) for use for various courses by selecting perhaps thirty of the forty chapters. An elementary course on “data structures and algorithms” might omit(bỏ qua) some of the mathematical algorithms and some of the advanced graph algorithms and other advanced topics, then emphasize(nhấn mạnh) the ways in which various data structures are used in the implementation(bổ sung). An intermediate(trung cấp) course on “design and analysis(phân tích) of algorithms” might omit(bỏ qua) some of the more practically-oriented(định hướng) sections(đoạn), then emphasize(nhấn mạnh) the identification(nhận ra, xác minh) and study of the ways in which good algorithms achieve(đạt đc) good asymptotic(tiệm cận) performance(thực thi). A course on “software tools” might omit the mathematical and advanced algorithmic material, then emphasize means by which the implementations given here can be integrated(hợp nhất) for use into large programs or systems. Some supplementary(bổ sung) material might be required for each of these examples to reflect (suy nghĩ) their particular orientation(định hướng riêng biệt) (on elementary data structures for “data structures and algorithms,” on mathematical analysis for “design and analysis of algorithms,” and on software engineering techniques for “software tools”); in this book, the emphasis(nhấn mạnh) is on the algorithms themselves.


At Brown University, we’ve used preliminary(sơ bộ) versions(bản dịch) of this book in our third course in computer science, which is prerequisite(đk quyết định trước hết) to all later courses. Typically(điển hình), about one-hundred students take the course, perhaps half of whom are majors(đỗ cao). Our experience(kinh nghiệm) has been that the breadth(bề rộng) of coverage(mức độ 1 vật đc bao phủ) of material in this book provides an “introduction to computer science” for our majors which can later be expanded(phát triển, nới rộng) upon(nhờ vào) in later courses on analysis of algorithms, systems programming and theoretical computer science, while at the same time providing all the students with a large set of techniques that they can immediately put to good use. The programming language used throughout(suốt) the book is Pascal. The
advantage of using Pascal is that it is widely available and widely known; the disadvantage(sự bất lợi) is that it lacks(thiếu, ko có) many features needed by sophisticated(phức tạp) algorithms. The programs are easily translatable to other modern programming languages, since relatively(tương đối) few Pascal constructs are used. Some of the programs can be simplified by using more advanced language features (some not available in Pascal), but this is true less often than one might think. A goal of this book is to present the algorithms in as simple and direct form as possible.

The programs are not intended(đc dự định) to be read by themselves, but as part of the
Surrounding(phụ cận, bao quanh) text. This style was chosen as an alternative(lựa chọn,luân phiên), for example, to having inline(trong dòng) comments. Consistency(trước sau như một) in style is used whenever(bất cứ lúc nào) possible(có thể thực hiện đc), so that programs which are similar, look similar. There are 400 exercises, ten following each chapter, which generally divide (phân chia thông thường) into one of two types. Most of the exercises are intended(đã đc nhằm) to test students’ understanding of material in the text, and ask students to work through an example or apply concepts( k/n) described in the text. A few of the exercises at the end of each chapter involve implementing(phương tiện, thi hành) and putting together some of the algorithms, perhaps running empirical(do kinh nghiệm) studies to learn their properties.
Acknowledgments(lời cảm ơn)
Many people, too numerous to mention(kể ra) here, have provided me with helpful Feedback(phản hồi) on earlier drafts(bản phát thảo) of this book. In particular(riêng), students and teaching assistants at Brown have suffered through preliminary versions of the material in this book over the past three years. Thanks are due to Trina Avery, Tom Freeman and Janet Incerpi, all of whom carefully read the last two drafts of the book. Janet provided extensive(rộng rãi, bao quát) detailed comments and suggestions which helped me fix innumerable(vô số) technical errors and omissions(bỏ sót); Tom ran and checked the programs; and Trina’s copy editing helped me make the text clearer and more nearly correct.

Much of what I’ve written in this book I’ve learned from the teaching and writings of Don Knuth, my thesis(luận văn) advisor(cố vấn) at Stanford. Though Don had no direct influence(ảnh hưởng) at all on this work, his presence(có mặt) may be felt in the book, for it was he who put the study of algorithms on a scientific footing(chỗ đứng) that makes a work such as this possible.
Special thanks are due(mang ơn) to Janet Incerpi who initially(ban đầu) converted the book into TEX format, added the thousands of changes I made after the “last draft,” guided(hướng dẫn) the files through various systems to produce printed pages and even wrote the scan conversion(chuyển đổi) routine for TEX that we used to produce draft manuscripts(viết tay), among many other things.
The text for the book was typeset(sắp chữ) at the American Mathematical Society; the drawings were done with pen-and-ink by Linda Sedgewick; and the final(cuối cùng) assembly and printing were done by Addison-Wesley under the guidance(sự hướng dẫn) of Jim DeWolf. The help of all the people involved is gratefully acknowledged(bày tỏ lòng biết ơn).
Finally, I am very thankful for the support of Brown University and INRIA where I did most of the work on the book, and the Institute for Defense Analyses and the Xerox Palo Alto Research Center, where I did some work on the book while visiting.
Robert Sedgewick
Marly-le-Roi, France
February, 1985’
Contents
MATHEMATICAL ALGORITHMS............................................................................................................ 21
SORTING......................................................................................................................................................... 91
SEARCHING.................................................................................................................................................. 171
STRING PROCESSING................................................................................................................................. 241
GEOMETRIC ALGORITHMS..................................................................................................................... 307
GRAPH ALGORITHMS............................................................................................................................... 373
ADVANCED TOPICS.................................................................................................................................. 457

Introduction
The objective(mục tiêu) of this book is to study a broad variety of important and useful algorithms: methods for solving problems which are suited for computer implementation. We’ll deal with many different areas of application, always trying to concentrate(tập trung) on “fundamental(qui tắc cơ bản)” algorithms which are important to know and interesting to study. Because of the large number of areas and algorithms to be covered, we won’t have room to study many of the methods in great depth. However, we will try to spend enough time on each algorithm to understand its essential(thực chất, chủ yếu) characteristics(đặc điểm) and to respect(khía cạnh) its subtleties(sự tinh vi). In short(tóm lại), our goal is to learn a large number of the most important algorithms used on computers today, well enough to be able to use and appreciate them.
To learn an algorithm well, one must implement it. Accordingly(do đó), the best strategy(chiến lược) for understanding the programs presented in this book is to implement and test them, experiment(thử nghiệm) with variants(biến thể), and try them out on real problems. We will use the Pascal programming language to discuss and implement most of the algorithms; since, however, we use a relatively small subset(tập con) of the language, our programs are easily translatable to most modern programming languages.
Readers of this book are expected(đòi hỏi) to have at least a year’s experience in programming in high- and low-level languages. Also, they should have some familiarity with elementary algorithms on simple data structures such as arrays, stacks, queues, and trees. (We’ll review some of this material but within the context of their use to solve particular problems.) Some elementary acquaintance(sự hiểu biết sơ sài) with machine organization(cấu tạo, tổ chức) and computer architecture(kiến trúc, cấu trúc) is also assumed. A few of the applications areas that we’ll deal with will require knowledge of elementary calculus. We’ll also be using some very basic material involving linear algebra, geometry, and discrete mathematics, but previous knowledge of these topics is not necessary.

This book is divided into forty chapters which are organized into seven
major parts. The chapters are written so that they can be read independently,
to as great extent as possible. Generally, the first chapter of each part
gives the basic definitions and the “ground rules” for the chapters in that
part; otherwise specific references make it clear when material from an earlier
chapter is required.
Algorithms
When one writes a computer program, one is generally implementing a method
of solving a problem which has been previously devised. This method is often
independent of the particular computer to be used: it’s likely to be equally
appropriate for many computers. In any case, it is the method, not the
computer program itself, which must be studied to learn how the problem
is being attacked. The term algorithm is universally used in computer science
to describe problem-solving methods suitable for implementation as computer
programs. Algorithms are the “stuff” of computer science: they are central
objects of study in many, if not most, areas of the field.
Most algorithms of interest involve complicated methods of organizing
the data involved in the computation. Objects created in this way are called
data structures, and they are also central objects of study in computer science.
Thus algorithms and data structures go hand in hand: in this book we will
take the view that data structures exist as the byproducts or endproducts of
algorithms, and thus need to be studied in order to understand the algorithms.
Simple algorithms can give rise to complicated data structures and, conversely,
complicated algorithms can use simple data structures.
When a very large computer program is to be developed, a great deal
of effort must go into understanding and defining the problem to be solved,
managing its complexity, and decomposing it into smaller subtasks which can
be easily implemented. It is often true that many of the algorithms required
after the decomposition are trivial to implement. However, in most cases
there are a few algorithms the choice of which is critical since most of the
system resources will be spent running those algorithms. In this book, we will
study a variety of fundamental algorithms basic to large programs in many
applications areas.
The sharing of programs in computer systems is becoming more widespread,
so that while it is true that a serious computer user will use a large
fraction of the algorithms in this book, he may need to implement only a
somewhat smaller fraction of them. However, implementing simple versions
of basic algorithms helps us to understand them better and thus use advanced
versions more effectively in the future. Also, mechanisms for sharing software
on many computer systems often make it difficult to tailor standard programs
to perform effectively on specific tasks, so that the opportunity to reimplement
basic algorithms frequently arises.
Computer programs are often overoptimized. It may be worthwhile to
take pains to ensure that an implementation is the most efficient possible only
if an algorithm is to be used for a very large task or is to be used many times.
In most situations, a careful, relatively simple implementation will suffice: the
programmer can have some confidence that it will work, and it is likely to
run only five or ten times slower than the best possible version, which means
that it may run for perhaps an extra fraction of a second. By contrast, the
proper choice of algorithm in the first place can make a difference of a factor
of a hundred or a thousand or more, which translates to minutes, hours, days
or more in running time. In this book, -we will concentrate on the simplest
reasonable implementations of the best algorithms.
Often several different algorithms (or implementations) are available to
solve the same problem. The choice of the very best algorithm for a particular
task can be a very complicated process, often involving sophisticated mathematical
analysis. The branch of computer science where such questions are
studied is called analysis of algorithms. Many of the algorithms that we will
study have been shown to have very good performance through analysis, while
others are simply known to work well through experience. We will not dwell
on comparative performance issues: our goal is to learn some reasonable algorithms
for important tasks. But we will try to be aware of roughly how well
these algorithms might be expected to perform.
Outline of Topics
Below are brief descriptions of the major parts of the book, which give some of
the specific topics covered as well as some indication of the general orientation
towards the material described. This set of topics is intended to allow us
to cover as many fundamental algorithms as possible. Some of the areas
covered are “core” computer science areas which we’ll study in some depth
to learn basic algorithms of wide applicability. We’ll also touch on other
disciplines and advanced fields of study within computer science (such as
numerical analysis, operations research, clompiler construction, and the theory
of algorithms): in these cases our treatment will serve as an introduction to
these fields of study through examination of some basic methods.
MATHEMATICAL ALGORITHMS include fundamental methods from
arithmetic and numerical analysis. We study methods for addition and multiplication
of integers, polynomials, and matrices as well as algorithms for
solving a variety of mathematical problems which arise in many contexts:
random number generation, solution of simultaneous equations, data fitting,
and integration. The emphasis is on algorithmic aspects of the methods, not
the mathematical basis. Of course we can’t do justice to advanced topics
with this kind of treatment, but the simple methods given here may serve to
introduce the reader to some advanced fields of study.
SORTING methods for rearranging files into order are covered in some
depth, due to their fundamental importance. A variety of methods are developed,
described, and compared. Algorithms for several related problems are
treated, including priority queues, selection, and merging. Some of these
algorithms are used as the basis for other algorithms later in the book.
SEARCHING methods for finding things in files are also of fundamental
importance. We discuss basic and advanced methods for searching using trees
and digital key transformations, including binary search trees, balanced trees,
hashing, digital search trees and tries, and methods appropriate for very large
files. These methods are related to each other and similarities to sorting
methods are discussed.
STRING PROCESSING algorithms include a range of methods for dealing
with (long) sequences of characters. String searching leads to pattern
matching which leads to parsing. File compression techniques and cryptology
are also considered. Again, an introduction to advanced topics is given
through treatment of some elementary problems which are important in their
own right.
GEOMETRIC ALGORITHMS comprise a collection of methods for solving
problems involving points and lines (and other simple geometric objects)
which have only recently come into use. We consider algorithms for finding
the convex hull of a set of points, for finding intersections among geometric
objects, for solving closest point problems, and for multidimensional searching.
Many of these methods nicely complement more elementary sorting and
searching methods.
GRAPH ALGORITHMS are useful for a variety of difficult and important
problems. A general strategy for searching in graphs is developed and
applied to fundamental connectivity problems, including shortest-path, minimal
spanning tree, network flow, and matching. Again, this is merely an
introduction to quite an advanced field of study, but several useful and interesting
algorithms are considered.
ADVANCED TOPICS are discussed for the purpose of relating the material
in the book to several other advanced fields of study. Special-purpose hardware,
dynamic programming, linear programming, exhaustive search, and NPcompleteness
are surveyed from an elementary viewpoint to give the reader
some appreciation for the interesting advanced fields of study that are suggested
by the elementary problems confronted in this book.
The study of algorithms is interesting because it is a new field (almost
all of the algorithms we will study are less than twenty-five years old) with
a rich tradition (a few algorithms have been known for thousands of years).
New discoveries are constantly being made, and few algorithms are comp!etely
understood. In this book we will consider intricate, complicated, and difficult
algorithms as well as elegant, simple, and easy algorithms. Our challenge is
to understand the former and appreciate the latter in the context of many
different potential application areas. In doing so, we will explore a variety of
useful tools and develop a way of “algorithmic thinking” that will serve us
well in comnutational challenges to come.




1. Preview
To introduce the general approach(phương pháp) that we’ll be taking to studying algorithms, we’ll examine a classic(kinh điển) elementary problem: “Reduce(làm nhỏ) a given fraction(phân số) to lowest terms(số hạng).” We want to write 2/3, not 4/6, 200/300, or 178468/267702. Solving this problem is equivalent(tương đương) to finding the greatest common divisor(số chia) (gcd) of the numerator(tử số) and the denominator(mẫu số): the largest integer which divides them both. A fraction is reduced(làm nhỏ) to lowest terms by dividing both numerator and denominator by their greatest common divisor.
Pascal
A concise(ngắn gọn) description of the Pascal language is given in the Wirth and Jensen Pascal User Manual and Report that serves(cung cấp) as the definition(đ/n) for the language. Our purpose here is not to repeat information from that book but rather to examine the implementation of a few simple algorithms which illustrate(minh họa) some of the basic features of the language and. the style that we’ll be using.
Pascal has a rigorous(nghiêm ngặc) high-level syntax(cú pháp) which allows easy identification(nhận ra) of
the main features of the program. The variables (var) and functions (function) used by the program are declared first, followed by the body of the program. (Other major program parts, not used in the program below which are declared before the program body are constants and types.) Functions have the same
format as the main program except(trừ ra) that they return a value, which is set by assigning something to the function name within the body of the function. (Functions that return no value are called procedures.)
The built-in(đc cài sẵn) function readln reads a line from the input and assigns(ấn định) the values found to the variables given as arguments(đối số); writeln is similar. A standard built-in predicate(thuộc tính), eof, is set to true when there is no more input. (Input and output within a line are possible with read, write, and eoln.) The declaration(khai báo) of input and output in the program statement(câu lệnh) indicates that the program is using the “standard” input and output streams.

To begin, we’ll consider(xem xét) a Pascal program which is essentially(cần thiết) a translation
of the definition of the concept of the greatest common divisor into a programming language.
The body of the program above is trivial: it reads two numbers from the
input, then writes them and their greatest common divisor on the output.
The gcd function implements a “brute-force” method: start at the smaller of
the two inputs and test every integer (decreasing by one until 1 is reached)
until an integer is found that divides both of the inputs. The built-in function
abs is used to ensure that gcd is called with positive arguments. (The mod
function is used to test whether two numbers divide: u mod v is the remainder
when u is divided by v, so a result of 0 indicates that v divides u.)
Many other similar examples are given in the Pascal User Manual and
Report. The reader is encouraged to scan the manual, implement and test
some simple programs and then read the manual carefully to become reasonably
comfortable with most of the features of Pascal.
Euclid’s Algorithm
A much more efficient method for finding the greatest common divisor than
that above was discovered by Euclid over two thousand years ago. Euclid’s
method is based on the fact that if u is greater than v then the greatest
common divisor of u and v is the same as the greatest common divisor of v
and u - v. Applying this rule successively, we can continue to subtract off
multiples of v from u until we get a number less than v. But this number is
exactly the same as the remainder left after dividing u by v, which is what
the mod function computes: the greatee:t common divisor of u and v is the
same as the greatest common divisor of 1) and u mod v. If u mod v is 0, then v
divides u exactly and is itself their greatest common divisor, so we are done.
This mathematical description explains how to compute the greatest
common divisor of two numbers by computing the greatest common divisor
of two smaller numbers. We can implement this method directly in Pascal
simply by having the gcd function call itself with smaller arguments:
(Note that if u is less than v, then u mod v is just u, and the recursive call
just exchanges u and v so things work as described the next time around.)
If the two inputs are 461952 and 116298, then the following table shows the
values of u and v each time gcd is invoked:
It turns out that this algorithm always uses a relatively small number of
steps: we’ll discuss that fact in some moire detail below.
Recursion
A fundamental technique in the design of efficient algorithms is recursion:
solving a problem by solving smaller versions of the same problem, as in the
program above. We’ll see this general approach used throughout this book,
and we will encounter recursion many tirnes. It is important, therefore, for us
to take a close look at the features of the above elementary recursive program.
An essential feature is that a recursive program must have a termination
condition. It can’t always call itself, there must be some way for it to do
something else. This seems an obvious point when stated, but it’s probably
the most common mistake in recursive programming. For similar reasons, one
shouldn’t make a recursive call for a larger problem, since that might lead to
a loop in which the program attempts to solve larger and larger problems.
Not all programming environments support a general-purpose recursion
facility because of intrinsic difficulties involved. Furthermore, when recursion
is provided and used, it can be a source of unacceptable inefficiency. For these
reasons, we often consider ways of removing recursion. This is quite easy to
do when there is only one recursive call involved, as in the function above. We
simply replace the recursive call with a goto to the beginning, after inserting
some assignment statements to reset the values of the parameters as directed
by the recursive call. After cleaning up the program left by these mechanical
transformations, we have the following implementation of Euclid’s algorithm:
Recursion removal is much more complicated when there is more than
one recursive call. The algorithm produced is sometimes not recognizable, and
indeed is very often useful as a different way of looking at a fundamental algorithm.
Removing recursion almost always gives a more efficient implementation.
We’ll see many examples of this later on in the book.
Analysis of Algorithms
In this short chapter we’ve already seen three different algorithms for the same
problem; for most problems there are many different available algorithms.
How is one to choose the best implementation from all those available?
This is actually a well developed area of study in computer science.
Frequently, we’ll have occasion to call on research results describing the performance
of fundamental algorithms. However, comparing algorithms can be
challenging indeed, and certain general guidelines will be useful.
Usually the problems that we solve have a natural “size” (usually the
amount of data to be processed; in the above example the magnitude of
the numbers) which we’ll normally call N. We would like to know the
resources used (most often the amount of time taken) as a function of N.
We’re interested in the average case, the amount of time a program might be
expected to take on “typical” input data, and in the worst case, the amount
of time a program would take on the worst possible input configuration.
Many of the algorithms in this book are very well understood, to the point
that accurate mathematical formulas are known for the average- and worstcase
running time. Such formulas are developed first by carefully studying
the program, to find the running time in terms of fundamental mathematical
quantities and then doing a mathematical analysis of the quantities involved.
For some algorithms, it is easy to hgure out the running time. For example,
the brute-force algorithm above obviously requires min(u, VU)-gcd(u, V)
iterations of the while loop, and this quantity dominates the running time if
the inputs are not small, since all the other statements are executed either
0 or 1 times. For other algorithms, a substantial amount of analysis is involved.
For example, the running time of the recursive Euclidean algorithm
obviously depends on the “overhead” required for each recursive call (which
can be determined only through detailed1 knowledge of the programming environment
being used) as well as the number of such calls made (which can
be determined only through extremely sophisticated mathematical analysis).
Several important factors go into this analysis which are somewhat outside
a given programmer’s domain of influence. First, Pascal programs are
translated into machine code for a given computer, and it can be a challenging
task to figure out exactly how long even one Pascal statement might take to
execute (especially in an environment where resources are being shared, so
that even the same program could have varying performance characteristics).
Second, many programs are extremely sensitive to their input data, and performance
might fluctuate wildly depending on the input. The average case
might be a mathematical fiction that is not representative of the actual data
on which the program is being used, and the worst case might be a bizarre
construction that would never occur in practice. Third, many programs of
interest are not well understood, and specific mathematical results may not
be available. Finally, it is often the case that programs are not comparable at
all: one runs much more efficiently on one particular kind of input, the other
runs efficiently under other circumstances.
With these caveats in mind, we’ll use rough estimates for the running
time of our programs for purposes of classification, secure in the knowledge
that a fuller analysis can be done for important programs when necessary.
Such rough estimates are quite often easy to obtain via the old programming
saw “90% of the time is spent in 10% of the code.” (This has been quoted in
the past for many different values of “go%.“)
The first step in getting a rough estimate of the running time of a program
is to identify the inner loop. Which instructions in the program are executed
most often? Generally, it is only a few instructions, nested deep within the
control structure of a program, that absorb all of the machine cycles. It is
always worthwhile for the programmer to be aware of the inner loop, just to
be sure that unnecessary expensive instructions are not put there.
Second, some analysis is necessary to estimate how many times the inner
loop is iterated. It would be beyond the scope of this book to describe the
mathematical mechanisms which are used in such analyses, but fortunately
the running times many programs fall into one of a few distinct classes. When
possible, we’ll give a rough description of the analysis of the programs, but it
will often be necessary merely to refer to the literature. (Specific references
are given at the end of each major section of the book.) For example, the
results of a sophisticated mathematical argument show that the number of
recursive steps in Euclid’s algorithm when u is chosen at random less than v is
approximately ((12 In 2)/7r2) 1n TJ. Often, the results of a mathematical analysis
are not exact, but approximate in a precise technical sense: the result might
be an expression consisting of a sequence of decreasing terms. Just as we are
most concerned with the inner loop of a program, we are most concerned with
the leading term (the largest term) of a mathematical expression.
As mentioned above, most algorithms have a primary parameter N,
usually the number of data items to be processed, which affects the running
time most significantly. The parameter N might be the degree of a polynomial,
the size of a file to be sorted or searched, the number of nodes in a
graph, etc. Virtually all of the algorithms in this book have running time
proportional to one of the following functions:
The running time of a particular program is likely to be some constant
times one of these terms (the “leading term”) plus some smaller terms. The
values of the constant coefficient and the terms included depends on the results
of the analysis and on implementation details. Roughly, the coefficient of the
leading term has to do with the number of instructions in the inner loop:
at any level of algorithm design it’s prudent to limit the number of such
instructions. For large N the effect of the leading term dominates; for small
N or for carefully engineered algorithms, more terms may contribute and
comparisions of algorithms are more difficult. In most cases, we’ll simply refer
to the running time of programs as “linear,” “N log N, ” “cubic,” etc., with
the implicit understanding that more detailed analysis or empirical studies
must be done in cases where efficiency is very important.
A few other functions do arise. For example, an algorithm with N2
inputs that has a running time that is cubic in N is more properly classed
as an N3/2 algorithm. Also some algorithms have two stages of subproblem
decomposition, which leads to a running time proportional to N(log N)2. Both
of these functions should be considered to be much closer to N log N than to
N2 for large N.
One further note on the “log” function. As mentioned above, the base
of the logarithm changes things only by a constant factor. Since we usually
deal with analytic results only to within a constant factor, it doesn’t matter
much what the base is, so we refer to “logN,” etc. On the other hand,
it is sometimes the case that concepts can be explained more clearly when
some specific base is used. In mathematics, the natural logarithm (base e =
2.718281828.. .) arises so frequently that a special abbreviation is commonly
used: log, N = In N. In computer science, the binary logarithm (base 2) arises
so frequently that the abbreviation log, N = lg N is commonly used. For
example, lg N rounded up to the nearest integer is the number of bits required
to represent N in binary.
Implementing Algorithms
The algorithms that we will discuss in this book are quite well understood,
but for the most part we’ll avoid excessively detailed comparisons. Our goal
will be to try to identify those algorithms which are likely to perform best for
a given type of input in a given application.
The most common mistake made in the selection of an algorithm is to
ignore performance characteristics. Faster algorithms are often more complicated,
and implementors are often willing to accept a slower algorithm to
avoid having to deal with added complexity. But it is often the case that
a faster algorithm is really not much more complicated, and dealing with
slight added complexity is a small price to pay to avoid dealing with a slow
algorithm. Users of a surprising number of computer systems lose substantial
time waiting for simple quadratic algorithms to finish when only slightly more
complicated N log N algorithms are available which could run in a fraction
the time.
The second most common mistake made in the selection of an algorithm
is to pay too much attention to performance characteristics. An N log N
algorithm might be only slightly more complicated than a quadratic algorithm
for the same problem, but a better N log N algorithm might give rise to a
substantial increase in complexity (and might actually be faster only for very
large values of N). Also, many programs are really run only a few times:
the time required to implement and debug an optimized algorithm might be
substantially more than the time required simply to run a slightly slower one.
The programs in this book use only basic features of Pascal, rather than
taking advantage of more advanced capabilities that are available in Pascal
and other programming environments. Our purpose is to study algorithms,
not systems programming nor advanced features of programming languages.
It is hoped that the essential features of the algorithms are best exposed
through simple direct implementations in a near-universal language. For the
same reason, the programming style is somewhat terse, using short variable
names and few comments, so that the control structures stand out. The
“documentation” of the algorithms is the accompanying text. It is expected
that readers who use these programs in actual applications will flesh them out
somewhat in adapting them for a particular use.

SOURCES for background material
A reader interested in learning more about Pascal will find a large number
of introductory textbooks available, for example, the ones by Clancy and
Cooper or Holt and Hune. Someone with experience programming in other
languages can learn Pascal effectively directly from the manual by Wirth and
Jensen. Of course, the most important thing to do to learn about the language
is to implement and debug as many programs as possible.
Many introductory Pascal textbooks contain some material on data structures.
Though it doesn’t use Pascal, an important reference for further information
on basic data structures is volume one of D.E. Knuth’s series on The
Art of Computer Programming. Not only does this book provide encyclopedic
coverage, but also it and later books in the series are primary references for
much of the material that we’ll be covering in this book. For example, anyone
interested in learning more about Euclid’s algorithm will find about fifty pages
devoted to it in Knuth’s volume two.
Another reason to study Knuth’s volume one is that it covers in detail
the mathematical techniques needed for the analysis of algorithms. A reader
with little mathematical background sh’ould be warned that a substantial
amount of discrete mathematics is required to properly analyze many algorithms;
a mathematically inclined reader will find much of this material ably
summarized in Knuth’s first book and applied to many of the methods we’ll
be studying in later books.


MATHEMATICAL ALGORITHMS


2. Arithmetic
Algorithms for doing elementary arithmetic operations such as addition,
multiplication, and division have a. very long history, dating back to
the origins of algorithm studies in the work of the Arabic mathematician
al-Khowdrizmi, with roots going even further back to the Greeks and the
Babylonians.
Though the situation is beginning to change, the raison d’e^tre of many
computer systems is their capability for doing fast, accurate numerical calculations.
Computers have built-in capabilities to perform arithmetic on integers
and floating-point representations of real numbers; for example, Pascal
allows numbers to be of type integer or re;d, with all of the normal arithmetic
operations defined on both types. Algorithms come into play when the operations
must be performed on more complicated mathematical objects, such as
polynomials or matrices.
In this section, we’ll look at Pascal implementations of some simple
algorithms for addition and multiplication of polynomials and matrices. The
algorithms themselves are well-known and straightforward; we’ll be examining
sophisticated algorithms for these problems in Chapter 4. Our main purpose
in this section is to get used to treating th’ese mathematical objects as objects
for manipulation by Pascal programs. This translation from abstract data to
something which can be processed by a computer is fundamental in algorithm
design. We’ll see many examples throughout this book in which a proper
representation can lead to an efficient algorithm and vice versa. In this
chapter, we’ll use two fundamental ways of structuring data, the array and
the linked list. These data structures are used by many of the algorithms in
this book; in later sections we’ll study some more advanced data structures.
Polynomials
Suppose that we wish to write a program that adds two polynomials: we would