Jon Kleinberg and Eva Tardos
Algorithm Design,
Hardcover, pp. 838, plus XXIII
Pearson Education Inc., Addison Wesley, Boston, 2006
ISBN 0-321-29535-8
In general about book
The design of algorithms is a well-known field of study. Programmers have always
been interested in finding better methods for achieving their goals, whether
those are solving system of linear equations of high order or they are sorting large
strings, writing efficient compilers, etc. Programming a computer requires more
than just translating well-understood instructions into a language a computer can
understand. In most cases, we need to devise a new method for solving a problem.
This method is often independent of particular computer to be used: it's likely to
be equally appropriate for many computers. In other words, it is the method, not
the computer program itself, which must be studied in order to learn how the problem
is being attacked. The term algorithm is standardly used in computer science
to describe problem-solving methods suitable for implementation as computer programs.
Informally, an algorithm is any well-defined computational procedure that
takes some values, or set of values, as input and produces some values, or set of
values, as output, i.e. it is a sequence of computational steps that transforms the
input into the output.
This book provides a comprehensive introduction to the modern study of
computer algorithms. Its objective is to study a broad variety of important and
useful algorithms, always trying to concentrate on fundamental algorithms, which
are important to known and interesting to study.
Chapter content
The book is organized into thirteen chapters, an Epilogue, References with 170
entries, and a comprehensive Index. The details of each chapter are as follow:
Chapter 1, Introduction: Some Representative Problems, pp. 1-28, begins
by introducing some representative algorithmic problems. It points to the following
five problems: greedy algorithms, dynamic programming, network flow, NPcompleteness
and PSPACE completeness, that are the main topics of studying in
this book.
Chapter 2, Basics of Algorithms Analysis, pp. 29-71, describes the mathematical
definitions and notations used for analyzing algorithms. The main themes
discussed here are with computational tractability, asymptotic order of growth, implementation
of stable matching algorithms, a survey of algorithm running times,
and the most broadly useful data structures: the priority queue.
Chapter 3, Graphs, pp. 73-113, covers the basic definitions and algorithmic
primitives needed for working with graphs. It points to the fact how graphs can
model a large variety of situations and they have been used in diverse fields ranging
from VLSI ICs design, modeling of real-time systems, computer networks, etc.
Interesting details concerning graph connectivity and graph traversal, testing bipartiteness,
and directed acyclic graphs, are given.
Chapter 4, Greedy Algorithms, pp. 115-207, concentrates on algorithms that
always make the choice that seems to be the best at the moment: greedy algorithms.
The chapter includes the main applications of greedy algorithms such as the shortest
paths, indirected and directed spanning trees, clustering, and compression.
Chapter 5, Divide and Conquer, pp. 209-250, shows how a problem is divided
into smaller subproblems, each problem is solved recursively, and a combine
algorithm is used to solve the original problem. Design of efficient algorithms that
are based on this method including the comparison of rankings, the computation of
closed pairs of point in the plane, and the Fast Fourier Transform are presented.
Chapter 6, Dynamic Programming, pp. 251-336, explains how dynamic programming
algorithm is applicable when the subproblems are not independent, i.e.
subproblems share subsubproblems. Then it is shown how this algorithm solves
each subsubproblem just once and then saves its answer in a table. The chapter
includes an extended discussion related to two fundamental problems such as sequence
alignment and shortest paths in graphs.
Chapter 7, Network Flow, pp. 337-450, is concerned with a basic problem
in graph theory and combinational optimization: algorithms for network flow. The
discussion includes details that deal with maximum flow and minimum cuts in a
network, the bipartite matching problem and disjoints paths in directed and undirected
graphs. In addition, designing efficient algorithms for airline scheduling,
image segmentation, project selection and baseball elimination are presented.
Chapter 8, NP and Computational Intractability, pp. 451-530, is devoted to
computational intractability and covers the subject of NP-completeness. It points
that this aspect of complexity theory has become a crucial part of algorithm design,
and programmers should known a lot about NP-completeness and the techniques
for proving this property.
Chapter 9, PSPACE: A Class of Problems beyond NP, pp. 531-552, concentrates
on PSPACE as a typical example of a class of intractable problems beyond
NP. The main themes discussed here are with solving hard problems in PSPACE,
solving quantified problems and games in polynomial space, and solving the planning
problem in polynomial space.
Chapter 10, Extending the Limits and Tractability, pp. 553-598, shows how
some instances of NP-complete problems often contain some structures that can be
used in the design of an efficient algorithm. More details concerning finding small
vertex covers, solving NP-hard problems on trees, coloring a set of circular arcs,
the decomposition of graphs and constructing tree decomposition, are presented.
Chapter 11, Approximation Algorithms, pp. 599-660, discusses algorithms
that may not lead to the optimal, or precise, results, known as approximation algorithms.
It shows how approximation algorithms can be used to find approximate
solutions to NP-complete problems efficiently. In addition, it explains in more details
a load-balancing problem, center balancing problem, set cover, vertex cover,
and the disjoint paths problem.
Chapter 12, Local Search, pp. 661-706, discusses local search heuristics, including
Metropolis and algorithm for simulated annealing. The chapter also covers
an application of local search to Hopfield neural network, focuses on some NP-hard
problems for which local search is used in order to design efficient algorithms, and
ends by discussing different types of local searches, such as best-response dynamics
and Nash equlibria.
Chapter 13, Randomized Algorithms, pp. 707-794, considers the use of randomization
in the design of algorithms. Several interesting topics are covered,
including finding the global minimum cut, randomized divide and conquer, randomized
caching, load balancing, packet routing, and others.
Useful book for students
The design of efficient algorithms is becoming important in many diverse fields including
mathematics, statistics, VLSI ICs design, data communications and computer
networks, real-time digital signal processing, etc. This book can serve as
an introduction to algorithm design in general. Its main intent is to find efficient
algorithms for computational problems. The book presents many algorithms and
covers them in considerable depth. Most of the algorithms, discussed here have
great practical utility.
The book is well written, very well organized and the presentation of the
material is quite clear. Each chapter of the book is organized in a scholarly way,
containing a brief introduction, analysis of the main theme, set of solved exercises,
large set of unsolved exercises, notes and further reading.
The book is appropriate for the use as a textbook for senior level text in
computer science, computer engineering and electrical engineering after students
have acquired some programming skills and familiarity with computer systems,
but before they have specialized courses in advanced areas of computer science
or computer applications. In addition this text can be used as a reference book
for engineers, researchers and specialists who are interested in learning the basic
principles of efficient algorithms design.
Without question, this is an important book. On the whole, I find the text
both stimulating and interesting. According to the above mentioned, I highly recommend
this book.
Prof. Mile Stojčev
Faculty of Electronic Engineering Niš
Beogradska 14, PO BOX 73
18000 Niš, Serbia and Montenegro
e-mail: stojcev@elfak.ni.ac.yu
Phone: +381 18 529 660
Fax: +381 18 588 399