Algorithms Books

In short: very small book in terms of pages (Under 200), discusses and reviews major Mathematical concepts around Computer Science, Number Theory and Quantum Computing including Shor's Theorom. The author being a Mathematician, seems to be very good at describing these topics in a concise manner. The book briefly introduces material from Theoretical CS (e.g. From Computer Language Theory such as Turing machines etc.) as well as Number theory (Abelian groups etc.) for people who may not have that background.

There is, by now, some variety of textbooks to choose from, covering quantum computing and quantum information;-- the output of research papers has been explosive since Peter Shor discovered his algorithm. Two books stand out as being especially ready for use in the class room, the one by Nielsen-Chuang, and the present one by Hirvensalo. The first covers more ground in physics (theory), and has a bigger selection of exercises;-- the second stresses the math and the CS side of the subject;-- it has more worked examples. It can be readily used in the classroom in a one semester course, and it will go over well with students in both math and in CS. The level is even, and a beginning student can progress in steps, following the text, and doing the exercises.

This book provides a good intro to Quantum Computing for beginners, plus it gives a clear presentation of the current results to more advanced readers. It does, to put it in the author's words, provides a good bridge between quantum mechanics and the theory of computation. It covers the basics, Turing Machines, some Theory of Computation, Shor's factorization algorithm, Grover's Method, etc.

It also has some helpful appendices for beginners in the end.

Quantum Algorithms are covered fairly well, but as the author himself acknowledges, Qm. Info. theory, Qm. Communication, Qm. error Correcting, Qm. Crypto. etc are not covered.

On the whole, a good read. Highly recommended.

The book by Prof. Diniz is indeed amongst the best on adaptive signal processing. Most of the fundamental concepts are well explained, suitable examples are given and practical applications are also discussed. The chapter on adaptive IIR filters is unique and still cannot be found in any other book. Moreover, solutions to the problems can be obtained by ftp, which is something very useful for students. Despite this is an excellent book (5 star), the price is ridiculous, as occurs with most titles from this publisher. If I were Prof. Diniz I would change from Kluwer Academic Publishers to a more competitive publisher.

Dr. Paulo Diniz has a unique view of the Adaptive Filtering field, due to years of extensive teaching experience. His book on Adaptive Filtering is a complete reference to the field, describing the theory in a concise way. The book develops the most important results in the field in less than 500 pages, including one chapter on IIR Adaptive Filtering - something that Haykin cannot beat.

The book is appealing to anyone who is interested in Adaptive Filtering and needs an extremely complete and concise reference. Highly recommended.

This book is a valuable reference -- a real work of mathematical scholarship concerning problems from elementary number theory, such as primality testing, square roots mod p, quadratic residues, polynomial factoring, and generation of random primes -- algorithms for which efficient solutions are known.

Related algorithms such as the lattice reduction algorithm of Lenstra, Lenstra, and Lovasz, and elliptic curve point counting over finite fields are not covered.

Three outstanding features of this book are:

1) The extensive chapter end notes that provide a comprehensive review of the history and state of the art for each topic addressed in the book. These notes are so detailed that they are like having a mini book within a book. Anyone doing research in the field would do well to own this book for this reason alone.

2) Exhaustive bibliography, all together there are over 1750 bibliographic entries.

3) Applications of the RH and ERH(Riemann Hypothesis and Extended Riemann Hypothesis). I know of no other single reference that covers the consequences of these conjectures being true in terms of primality testing, quadratic non-residue testing, primitive root finding and so on.

The algorithms are presented in pseudo code and practical implementation remarks are reserved for the notes section of each chapter.

Recommended for upper level undergraduates and all the way on up to faculty.

As a bonus the book is a real pleasure to view due to the excellent job done in the layout and typesetting.

I look forward to volume two which will focus on algorithms for intractable problems for which efficient (polynomial time) algorithms are NOT known such as factoring and the discrete log problem.

Bach and Shallit have done a wonderful job of preparing a survey of Number Theoretic Algorithms. After covering the basic mathematical material and complexity theory background, the book plunges in to discuss computation in (Z/(n)) and various algorithms in Finite Fields.

The part of the book that I like best are the last two chapters which deal with prime numbers and algorithms for primality testing. The authors have done an exhaustive survey of this area. Proofs of the correctness of the algorithms are wonderfully concise and lucid. The second volume [not published yet] will discuss problems for which efficient algorithms are currently unknown for example factoring, discrete log etc. The authors also promise coverage of the Adleman, Huang proof that Primes \in ZPP.

Exercises have been chosen carefully, and most of the solutions are available as an appendix (for the others references are given). Finally the bibliography is *huge* with close to 2000 citations. Overall an excellent book for reference and for a one stop introduction to the wonderful area of Algorithmic Number Theory.

This is the best book i had ever come across

This is the best book i had ever come across

With a book as technical as this, it's hard to know who my potential review readers will be. Nevertheless, I will give a very CONCRETE and ACCESSIBLE review. Also you should bear in mind this: the book does have some concrete and accessible aspects before getting into complex issues; moreover -- and maybe this is the most important of all: the simpler, concrete and accessible aspects of this book DO HAVE UTILITY. I'll give a personal example of the utility of the book's simpler material at the end of my review. But now let's proceed in a nice logical order...

The book deals with "combinatorial optimization" problems. These are problems where there are (1) a gigantic number of discrete configurations that are possible, (2) a way of scoring how desirous a configuration is, and (3) ways to change the configuration from the present one. Examples include the scheduling problem of how to assign 20 workers to one job apiece for 20 jobs (with different worker/job pairings having different costs); and, of course, the famous traveling salesman problem -- requiring precisely one visit to each of N cities and a return to the first.

The most easily understood algorithm to solve combinatorial optimization is BLIND RANDOM SEARCH (BRS): generate a random configuration, score it, repeat (always keeping the best score yet encountered and its corresponding configuration saved in memory). You can have stop criteria as you wish -- including an OR'd pair (which I find to be itself a great improvement) -- such as UNTIL (a) score is X good or better OR (b) you've generated N random configurations.

BRS performs relatively poorly. A HUGE improvement is an algorithm called "Iterative Improvement" (II). This algorithm is covered on pages 6 thru 8 of the book. The idea is to take a BRS configuration then do some modest moves around that configuration -- scoring and repeating until you had k failures to improve. The best obtained is that one BRS "point". Generate a new BRS point and compare to the old as usual, but now the II loop probably substantially improved that old BRS score to which you are comparing.

Both BRS and II involve only "downhill" moves. Only a lower score and its companion configuration are kept and a new configuration never becomes the current one if its score is worse. The danger is "getting stuck" in a local minimum as opposed to the global minimum (truly best score). To avoid this danger there is the "probabilistic hill-climbing" algorithm of Metropolis. An improved configuration (one with a better score) still becomes the next current configuration, but you have some probability of taking the next current configuration as being the current contendor even if this contendor configuration has a worse score. The probability is related to the score and a parameter that might be thought of as temperature.

From the probabilistic hill-climbing algorithm of Metropolis, all you need to get to an annealing algorithm is a schedule for appropriately reducing the "temperature" parameter (which controls up-hill acceptance probability) in successive steps. The analogy is freezing a liquid to get its perfectly crystalline line-up of atoms, free of defects. Go too fast and you may get a glass rather than a crystal.

The book's chief aim is how to recommend IN GENERAL, without recourse to your specific problem, a schedule for the "temperature" changes. If this be your aim in considering the book, well it goes without saying you need not consider further: here's your book.

But what about the less technical reader? First of all, the book does gently introduce you to combinatorial optimization, blind random search, Metropolis and annealing. Second, the few pages on Iterative Improvement are EMINENTLY USEFUL in a PRACTICAL sense -- and are a good simple alternative to annealing (my example will be at the end). Third is that the book includes several ancillary extras.

The ancillary extras:

· tutorial on all of matrix mathematics
· tutorial on Markov Chains
· material on probability and conditional probability
· tutorial on Statistics -- esp. w.r.t. the Normal distribution and Central Limit Thm

I'm not saying that the ancillary extras are the best there is for a novice level reader, but most folks would not know of the existence of this material in a book called "The Annealing Algorithm".

The final bit of ancillary material is Pascal computer code for all the algorithms in the book and a complete program for doing the whole annealing bit on the electronic chip placement combinatorial problem.

MY EXAMPLE OF UTILITY OF ITERATIVE IMPROVEMENT ALGORITHM:

My problem is not combinatorial optimization, but can still use the ideas of iterative improvement since I am solving a deterministic problem (one without any random element) using Monte Carlo methods (using random numbers). My problem: I have the coordinates of the midpoint of a line segment; the line segment's length is also known and is roughly one-fourth the diameter of a circle; the line segment lies the annular area between this circle and a circle with a radius half-a-line-segment bigger radius than that of the original circle; lastly, given the rotation angle of my line segment, I ask this: what are the coordinates (x,y) of the intersection of the line segment and the original circle? (I took steps to check that YES, there was an intersection.) Solving the problem analytically didn't work. (Or at least, I couldn't do it.) I had used a BRS Monte Carlo approach. Then, re-reading this book, it occurred to me to use the book's algorithm (Iterative Improvement) on pages 6-8 (Pascal code page 8). I got a big improvement in lowering the error. Obviously, I had to delete details in this review (like how I even know error in my problem, and if I do know it, why can't I fix it exactly -- hint: circle is the locus of all points equidistant from a given point), but the POINT FOR YOU is that I attained a great improvement in my problem just by using the book's explicit algorithm (Pascal code) for Iterative Improvement.

Finally, the book is nice to read -- both very easy-on-the-eyes typography (unusual for a "math" book) and a good flow to the authors' writing.

The Annealing Algorithm is part of The Kluwer International Series in Engineering and Computer Science, concentrating on VLSI, Computer Architecture And Digital Signal Processing. The Consulting Editor, Jonathan Allen, has put together a concise, academic publication that introduces the conceptually simple procedures of simulated mathematical annealing and mathematical optimization. Research for the book was carried out at the Thomas J Watson Research Center of the IBM Corporation in Yorktown Heights, NY. Chapters include A Preview of The Annealing Algorithm, Preliminaries from Matrix Theory, (Markov) Chains, Chain Statistics, Annealing Chains, Samples from Normal Distributions, Score Densities, The Control Parameter, Finite-Time Behavior of the Annealing Algorithm, The Structure of the State Space, and (Pascal) Implementation Aspects. References and an Index are included. Mathematicians and computer science professionals seeking to learn about the conception of annealing as a combinatorial optimization tool, will find this publication interesting and will appreciate its use as a basis for further research.

The book covers the most important topics in applied optimization. The main focus of this book is how to formulate and transform optimization problems so that they can be solved by well-developed software. This aim has been achieved magnificently and skillfully.

The most important problem in applied optimization, I believe, is problem formulation, that is to translate the intuitive ideas into rigorous mathematics. The book has done an excellent job in explaining the process of formulating an optimization problem. It provides step-by-step descriptions that are very helpful and useful. A lot of good examples and exercises are illustrated, which can be used as templates to formulate many real engineering problems with minor revisions.

The second major issue in applied optimization is to reformulate an original optimization problem to its standard form, so that it can be directly solved by known software. This part is tough because it involves a lot of mathematics. But the author succeeds to solve it in a magic way. Many abstract and complicated definitions and algorithms are visualized by beautiful and meaningful figures. The author also tries to avoid the unnecessary mathematics. Many theorems and proofs are deliberately rewritten to ease the understanding of this part.

Applied optimization has two sides: science and art. Most of the books in this field focus on the science side, but not so satisfactory in the art side. The book has done a very good job in balancing both sides. You can expect to obtain both "optimization" and "the art of optimization" from this book.

(Written by Chengtao Wen)

I came across this book recently when I was researching pricing mechanisms in deregulated electricity markets. Most of the books on optimization and numerical methods that I have studied focused on constructing algorithms for arbitrarily defined problems. Most of the time, the logic and the rationale are buried beneath the intimidating mathematical equations. This is one of such books where the authors do not shy from using elementary examples and simple English language to clarify fundamental concepts. Nowhere did I come across such easy-to-follow explanations supported by case-studies and examples as it was done in this book.


It would not take a genius to realize that in the real world constrained by time and computational power the perfect method is most often beyond the reach. Our world revolves around the so called "second best solutions". The "art" in optimization are formulation and approximation. For those of you, who intend to formulate, construct and solve optimization problems presented by the world around you (not just understand the theory), this book is a great asset. I know I benefited from it greatly.

If you have ever been curious to know what is the mathematics behind the fancy formulas describing the average-case behavior of algorithms -- this book is for you. An excellent addition to the classic "The Art of Computer Programming" by D.Knuth, "Introduction to Analysis of Algorithms" by R.Sedgewick and P.Flajolet, and "Analysis of Algorithms" by M.Hofri, this book walks reader through a beautiful, and at the same time very diverse (not to say complex) world of mathematical tools and techniques needed to obtain precise answers to questions like "what is the average depth of a digital tree built over $n$ strings?", or "what is the average number of comparisons performed by a Knuth-Morris-Pratt algorithm when it searches for a given pattern of length $m$ in a random text of length $n$?".

Being well organized, the book present these (sometimes very sophisticated) techniques in a simple step-by-step fashion, starting with brief reviews of several known (and necessary for future presentation) results from probability, complex analysis/special functions, and information theory. The presentation of the numerous specific techniques is split in two parts: explaining probabilistic and analytic approaches to the analysis of algorithms correspondingly. Probabilistic techniques (inequalities of moments, limit theorems, large deviations, etc.) are very useful in the analysis of complex random structures, as they often yield simple estimates of their asymptotic behavior, where more accurate techniques fail or become prohibitively laborious. Analytic techniques (generating functions, singularity analysis, saddle point techniques, Mellin transform, analytic poissonization and depoissonization) on the other hand, represent a toolbox for exact modelling of the characteristics of the algorithms, yielding estimates of unparalleled precision.

As indicated by its title, this book is mostly devoted to the analysis of a special class of combinatorial algorithms - ones that operate with sequences of symbols, or sequences. For example, it includes a detailed analysis of various algorithms for searching and sorting alphanumeric sequences based on digital trees (tries, digital search tries, Patricia-tries, etc.), redundancy expressions for popular Lempel-Ziv data compression schemes, average complexity estimates for text pattern-matching algorithms (such as Knuth-Morris-Pratt scheme), and so on.

Following the tradition of "The Art of Computer Programming", the author wraps many results in the form of exercises, so that active readers can have fun solving them. These excersises are grouped into several classes, ranging from simple routine calculations to serious research problems (including ones that are currently unsolved).

Overall, this is a very good graduate-level textbook and a valuable (and almost self-contained) source of information for everyone interested in the analysis of algorithms.

If you have ever been curious to know what is the mathematics behind the fancy formulas describing the average-case behavior of algorithms -- this book is for you. An excellent addition to the classic "The Art of Computer Programming" by D.Knuth, "Introduction to Analysis of Algorithms" by R.Sedgewick and P.Flajolet, and "Analysis of Algorithms" by M.Hofri, this book walks reader through a beautiful, and at the same time very diverse (not to say complex) world of mathematic tools and techniques needed to obtain precise answers to questions like "what is the average depth of a digital tree built over $n$ strings?", or "what is the average number of comparisons performed by a Knuth-Morris-Pratt algorithm when it searches for a given pattern of length $m$ in a random text of length $n$?".

Being well organized, the book present these (sometimes very sophisticated) techniques in a simple step-by-step fashion, starting with brief reviews of several known (and necessary for future presentation) results from probability, complex analysis/special functions, and information theory. The presentation of the numerous specific techniques is split in two parts: explaining probabilistic and analytic approaches to the analysis of algorithms correspondingly. Probabilistic techniques (inequalities of moments, limit theorems, large deviations, etc.) are very useful in the analysis of complex random structures, as they often yield simple estimates of their asymptotic behavior, where more accurate techniques fail or become prohibitively laborious. Analytic techniques (generating functions, singularity analysis, saddle point techniques, Mellin transform, analytic poissonization and depoissonization) on the other hand, represent a toolbox for exact modelling of the characteristics of the algorithms, yielding estimates of unparalleled precision.

As indicated by its title, this book is mostly devoted to the analysis of a special class of combinatorial algorithms -- ones that operate with sequences of symbols, or sequences. For example, it includes a detailed analysis of various algorithms for searching and sorting alphanumeric sequences based on digital trees (tries, digital search tries, Patricia-tries, etc.), redundancy expressions for popular Lempel-Ziv data compression schemes, average complexity estimates for text pattern-matching algorithms (such as Knuth-Morris-Pratt scheme), and so on.

Following the famous tradition of "The Art of Computer Programming", the author wraps many (in some case very difficult to derive) results in the form of exercises, so that active readers can have fun solving them. As a special bonus, some of these "exercises" represent currently open research problems.

Overall, this is a very good graduate-level textbook and a valuable (and almost self-contained) source of information for everyone interested in the analysis of algorithms.

Whether you have enjoyed the previous book "Calendrical Calculations : The Millenium Edition", or you do not care for that book's theory, you'll love this one because you get to see the results, laid out in clean crisp typography, with many small details (holidays, moon phases, ...) that make this book a pleasure to use as a reference. Well worth the price.

Whether you have enjoyed the previous book "Calendrical Calculations : The Millenium Edition", or you do not care for that book's theory, you'll love this one because you get to see the results, laid out in clean crisp typography, with many small details (holidays, moon phases, ...) that make this book a pleasure to use as a reference. Well worth the price.

This is an outstanding summary of research (as of 2001 or so) in leading techniques for compiler optimization in performance computing. There's not much here for the typical software developer, even those who write applications compiled for massively parallel systems. Most compiler writers won't find much of immediate use either - if you haven't mastered Optimizing Compilers for Modern Architectures and Parallel Programming With MPI, you're in for a rough ride. These techniques all apply to parallel systems, with hundreds to hundreds of thousands of processors acting together. And laugh if you want: many of these researchers address the needs of Fortran programmers. Anyone who laughs at Fortran just doesn't understand the performance computing market or the recent advances in that venerable language.

If you're deep into compiler development on that class of machine (or something similar enough) this collection presents 21 chapters, a bit under 800 pages, of cutting edge analysis and algorithms. Topics cover every level, from the micro-level checking of dependencies between one array element and another in a looped computation, up to macro-level OS level constructs for distributing and synchronizing coarse-grained tasks.

Even specialists will find only a few chapters that address their immediate needs. Specialists at this level, however, are used to that. Commercial gold mines today yield one gram of gold per tonne of useless tailings. The ratio is better in this case, but even readers with the greatest interest will skip parts of this goldmine of information. Still, if this is your area of interest, you may well find something of value. Highly recommended to the right reader.

-- wiredweird

Scalable parallel systems or, more generally, distributed memory systems offer a challenging model of computing and pose fascinating problems regarding compiler optimization, ranging from language design to run time systems. Research in this area is foundational to many challenges from memory hierarchy optimizations to communication optimization.
This unique, handbook-like monograph assesses the state of the art in the area in a systematic and comprehensive way. The 21 coherent chapters by leading researchers provide complete and competent coverage of all relevant aspects of compiler optimization for scalable parallel systems. The book is divided into five parts on languages, analysis, communication optimizations, code generation, and run time systems. This book will serve as a landmark source for education, information, and reference to students, practitioners, professionals, and researchers interested in updating their knowledge about or active in parallel computing.

The editors DeLiang Wang and Guy Brown represent two of the teams with the most experience in auditory scene analysis, but in this book they've gone out of their way to also include the best and latest work of many other teams working in the field, and they have edited it into a coherent whole. Since I'm getting back into this field after a ten-year side track, I found this book to be a good guide to the current state of the CASA art. For newer people in the field, it will be a welcome overview and history of the fundamentals, including cochleagrams, correlograms, time-frequency masks, tracking multiple pitches, binaural localization, etc. The book goes into depth on auditory scene analysis based on a variety of cues, such as pitch and localization, and explores both feature-based and model-based approaches, including techniques that explicitly exploit the structure of speech and music. Techniques motivated by mathematical and computational elegance are contrasted with techniques based on known properties of the auditory nervous system and psychoacoustics. For anyone needing an introduction to this exciting field, or anyone wanting to do work in it, this book is a must-have.

How do we manage to separate, in the everyday acoustic cacophony, the sound we hear from those we wish to ignore? We, humans, may be able to do it, but often inefficiently and with great effort. This is why work by groups of scientists and engineers, aimed at having the machine accomplish separation of sounds, especially speech sources, is becoming an important and ever-growing area of computer science. The book edited by DeLiang Wang and Guy Brown, two of the foremost experts of the area, is a notable achievement aimed at exposing intriguing aspects of computational signal separation with special emphasis on speech, written by leading figures of the field. This volume should be a required addition to the bookshelf of audio engineers, computer scientists, and applied mathematicians, but it is also likely to end up as a textbook to be used in graduate- and upper-level undergraduate courses in engineering departments.