Algorithms Books

This book really made me think about GIS analysis in a new way. This book covers topics such as thinking of maps "map-ematically", distance across a terrain rather than just straight lines, slope and aspect as mathematical surface derivatives (as in calculus), and much, much more. If you are serious about GIS and spatial modeling, this book is a must read.

Berry has a way of looking a GIS analysis that is different than anybody else I have read or listened to. And his presentation style is exciting and fresh. I have seen Berry in live presentations twice and he never fails to disappoint for content or style.

I think Prof. McCauley is the smartest man on the face of the earth. He must have wonderful, beautiful, smart children.

This is by far one of the clearest most easily understandable studies of the complex topic of algorithm analysis and data structure analysis. The author, utlizing a practical approach, creates an easy to read experience, and a very enjoyable one. Overall, an excellent text, and I recommend it to anyone who has ever tried to figure out what the difference between a red-black tree and a binary search tree really was.

Combinatorial algorithms are widely used in a diverse set of applications areas from engineering, the biological and physical sciences, mathematics and computation, economics, and so on. In addition to their applied nature, combinatorial algorithms often rely on sophisticated results in combinatorics and algebra and on clever data structures. This makes the task of introducing the multi-faceted world of combinatorial algorithms a difficult one.

Kreher and Stinson have written a modern text that addresses the subject systematically, and from a variety of viewpoints. Their text is engaging and accessible to a senior undergraduate student. Nevertheless, a researcher will also find the text informative and useful. It provides an excellent balance of mathematical background, algorithm development, and algorithm implementation. The book has been designed to support an undergraduate course, and provides further material to support a more intensive graduate level course. The text has well designed chapter notes and exercises; the presentation of the methods through description, pseudocode, and examples is particularly clear. However, it is the selection of topics that makes this text especially good.

Numerous strong texts on graph algorithms are concerned with the analysis of properties of graphs rather than the generation and search for combinatorial objects. Highly structured combinatorial objects, such as error-correcting codes or interconnection networks, are notoriously difficult to find via computational methods. The authors develop a powerful toolkit of algorithms for addressing generation and search problems. They start with simple tools and then use these along with some basic combinatorial mathematics to build quite sophisticated tools. The text provides enough information to develop and understand each of the algorithms presented, and enough pointers for the interested reader to find more.

This is an excellent book. I enjoyed reading it. More importantly, there is no doubt that an interesting course can be taught from this book at either the undergraduate or graduate level. There is enough flexibility in the choice of material and emphasis to support a course on mathematical aspects, algorithmic techniques, or applications.

A definitive account of the history and present state of combinatorial optimization from an author who is one of the most respected researchers in this area. The author has won the Dantzig award, the Fulkerson prize (twice) and the Lanchester Prize for his earlier classic text on "Theory of Linear and Integer Programming". Given the current pricing, it is a steal with over 1800 pages spread across three volumes. This is certainly not a text to be read from cover to cover but is a handy reference if you are interested in combinatorial optimization as a research topic or in the related areas of optimization, integer programming, polyhedral combinatorics, or graph theory.

The author gives short and elegants proof of most of the results. The reader is expected to have a background in graph theory, linear programming and integer programming. The author cites some results without proofs from his earlier books , "Theory of Linear and Integer Programming", and "Geometric Algorithms and Combinatorial Optimization". The book does not concentrate on applications and modeling aspects of combinatorial optimization problems and it does not dwell on the computational methods for NP-hard problems. The book does not offer exercises but lists some open problems and research topics (updated on author's website).

The book is mainly devoted to the theoretical developments in this field. Quoting the author, "We aim at offering an introduction and an in-depth survey of polyhedral combinatorics and efficient algorithms ... In the astonishing event that NP=P will be proved, this book will be highly incomplete". The results in this book are up to date till 2002 (updates are available at the author's website). In short this book should be invaluable for a graduate student or a researcher.

Combinatorial Optimisation : Networks and Matroids by Eugene Lawler examines shortest paths, network flows, bipartite matching, non bipartite matching. More importantly there is an excellent introduction to matroid theory including matroids and the greedy algorithm, matroid intersections and matroid parity problems, some of these Lawler's own results.

However there is not much on NP completeness, since this book was published in 1976. For a more to date version of events in combinatorial optimisation one might want to look at Papadimitriou and Steglitz's book on combinatorial optimisation (quite old too, considering this was published in 1982), Ahuja, Magnanti and Orlin's book on Network algorithms, Hochbaum's book on approximation algorithms and Cook, Cunnigham,Pulleyblank and Schrijver's book on combinatorial optimisation (listed in the order they were published).

Lawler's book is extremely well written and I am delighted that this book is now published by Dover, and hence easily affordable.

This is the most comprehensive compilation on combinatorial optiomization I have seen so far.
Usually, Papadimitriou's book is a good place for this material - but in many cases, looking for proofs and theorems - I had to use several books:
(*) Combinatorial Optimization Algorithms and Complexity by Papadimitriou and Steiglitz.
(*) Integer and Combinatorial Optimization by Nemhauser and Wolsey
(*) Theory of linear and integer programming by Schrijver
(*) Combinatorial Optimization by Cook, Cunningham, Pulleyblank and Schrijver
(*)Combinatorial Algorithms by Kreher and Stinson

This book, on the other hand, contains so much information and so many proved theorems - it's the richest resuorce in this topic, in my humble opinion.

Using it as a graduate level textbook for an *introduction* to combinatorial optimization is kind of hard - as although it's richness, some topics are described without enough detail or examples (like the topics on network flow and bipartite graphs) - yet the authors probably assumed some previous knowledge in those topics.

I prefer using this book as a reference rather than and intoduction.

The heavy mathematical notations in this book might scare some readers, but no-fear! You quickly get used to it, and appreciate the greatness in the notations, as they make the theorems more short and to the point. On the other hand - getting back to this book for a quick review on some subject might force you to flip pages for a fwe minutes, just to remember the notation again.

The authors intended this book to be a graduaet level textbook or an up-to-date reference work for current research. I believe they accomplished both targets!

Along with statistics, combinatorics is one of the most maligned fields of mathematics. Often it is not even considered a field in its own right but merely a grab-bag of disparate tricks to be exploited by other, nobler endeavours. Where is the glory in simply counting things? This book goes a long way towards shattering these old stereotypes. By unifying enumerative combinatorics under a strong algebraic framework, Aigner finally bestows upon the humble act of counting the respect it so surely deserves.

At first, it may be somewhat trying to make sense of his presentation as he reworks familiar results in this algebraic view. Often, I was left wondering why it is necessary to go through the trouble of all these high-powered techniques just to obtain results we've already obtained through much simpler means. However, as I progressed through the chapters, it became clear that the only consistent way to tackle the truly difficult problems in enumeration was with these algebraic tools.

If you are serious about combinatorics or merely interested in what combinatorics has to offer, this volume is certainly a valuable addition to your library.

A warning about the title. Some confusion may arise over whether the book is about "computational complexity theory" or the field of "complexity" being pioneered by places like the Santa Fe institute. Without neccessarily pidgeonholing the book into one of these fields, I will warn "complexity" types that it dives heavily into the rigorous field of computational complexity theory (i.e. P/NP, theoretical upper bounds on running times of algorithms ,etc), and re-assure readers from the computational complexity theory camp that the book is more rigorous then the cover, or the title might lead you to believe.

My first introduction to this book/subject area was when Lenore Blum (one of the authors) gave a talk at Carnegie Mellon University, mostly following the outlines of the book. I found the talk to be so interesting that I went out and bought the book. While I am not a professional CS theorist, I did attend many of the theory seminars at CMU while I was an undergrad there (you may call me a "hobby theorist"). The talk on this book was one of the few that seemed as novel and mind-blowing to me as my first introduction to theory had been (just in terms of "Wow this is cool!" "Ooh, I never thought of those things in that way", etc).

The book is about a novel approach to applying discoveries from complexity theory to the analysis of numerical algorithms. Pure complexity theory quickly becomes unwieldy, as input/output sizes for real-numbers approximated on a turing tape depends on many factors, including the precision of the representation, and the representation method itself. Techniques from applied algorithms (most notably, the "RAM machine" model of the 1970s) have the unfortunate side-effect of being able to solve problems in NP in polynomial time. Blum (and the other authors) take the novel approach of just allowing this side effect, while getting meaningful complexity bounds on real-valued computation, by creating a real-valued analog to the discrete turing machine used in classical complexity theory. Along the way, the authors show that, while this model does allow problems in NP to be solved in polynomial time, it introduces a class, which is not NP, but analogous to it, in the sense that theorems on real-valued algorithms have similar proofs to their discrete counterparts in classical complexity theory.

While this is not neccessarily useful to most practical programmers, it is, in addition to being a fascinating and novel way to look at numerical algorithms, also a fascinating subject to think about when looking at the physical world. Among the physical processes that can be looked at from the perspective of this book, are the much-hyped chaotic systems prevalant in the (unfortunately named -- and not very closely connected to "Computational Complexity Theory") field of "complexity" associated with the Santa Fe institute (hence the picture of the Mandelbrot set on the cover, which the authors study as a decidability problem within the framework of the new real-valued Turing machines introduced in this book)

My one complaint about the book was that, while the talk Lenore gave at CMU was aimed at an audience more familiar with computational complexity theory then with continuous mathematics, the book goes the other way around, making painstaking explanations of elementary computability / complexity theory, but assuming a strong knowledge of continuous mathematics.

This book provides a good introduction to both complexity and cryptology theory. I highly recommend it for a higher level undergraduate computer science student or to a beginner level graduate student.

If you are interested in the theory of cryptology this book will help you enormously.