Algorithms Books

Even though it is more than ten years old now, Moret & Shapiro is still the best book available on NP completeness and related topics. In a way I disagree with other reveiwers who advise that only graduate students read this book. It all depends. I have known a number of graduate students who might not have understood this material as well as some undergraduate students. It is not so much a matter of college level as it is your personal tools for dealing with abstraction and complexity.

I was required to purchase a leather-bound copy of this text for a Junior (undergraduate 3rd year) course. It is a wonderful book and I came across the Amazon listing just now on a search for volume 2.

This text is wonderful because it contains information relevant to students of Computation at all levels from Undergraduate onward. Fundamentally, the book is about analyzing the "complexity" of algorithms -- which is a way of defining how long some operations will require to complete. This volume concentrates almost entirely on algorithms which can be solved in an amount of time that is a polynomial function of the number of inputs.

Even formerly mundane-seeming algorithms as sorting are made more exciting by the inclusion of advanced material, for example on sorting networks. The book also includes very exciting algorithms involving two-dimensional (2D) geometric searches and other operations such as merging polygons. Graph theory is covered in particularly special detail with this text. Seven greedy algorithms are classified according to multiple toxonomies according to different mathematical views. Generalized pattern matching (such as regular expressions, finite state automata and beyond) is covered from beginning to advanced detail, as well.

A key quality of this book, I think, is that each reader will make "so much" of each section -- and then the reader might move on the next topic, and read up until the point of covering those parts of the book which seem readable. It might be good to read about twice during college and periodically every 4-7 years thereafter, until you can read the whole book. I see parts I still have not read. The book is written in a combination of clear exposition but the each chapter's topic coverage ranges (smoothly) from the introductory to the very advanced. Most chapters end in "optional" sections as a hint that they are to be skipped by those early in their studies.

In contrast to other reviewers here at Amazon, I find the coverage of P vs NP and NP-completeness to be rather brief although very understandable. In my copy of the text, there is a discussion on page 60 of NP-completeness, and that is the only such exposition mentioned in the index. I see that my copy of Volume I bears a "P" on the cover and on page 60 the text indicates that more detailed coverage of "NP" algorithmic complexity will follow in the second volume.

This is a very good book, well written with a lot of material -- BUT NOT FOR A UNDERGRADUATE student. Undergrads looking to get some basic help and introduction to NP Completeness, should avoid this book .. But others with a strong mathematical background and most importantly a lot of interest in this very interesting theory should definitely invest.

Hope this helps..

You're looking for the alogritm of making video confrence, orany video transfer, this is the book for you! While reading youunderstand where the price coming from! The Author knows the matterialvery well, and lets the reader to understand the mpeg-4 technology!

For mpeg4 motion estimation, it is the only book on the market that well explains and covers with complete algorithms analysis. The references of the papers for each chapter give you more clues about the each algorithm implementation. I would recommend also reference to ISO/IEC 14496-5 MPEG4 codec software and specs to help you understand MPEG4 codec in digital video processing and implementation on streaming media

an exceleent book with deep investigation on motion estimation. you can find most algorithms proposed before with complete references. The author also provides a profiling tool which is so efficent for complexity analysis. you will be able to benefit it definitly :)

Three classic volumes from Donald Knuth. I have the 3rd edition. Once your get pass understanding MIX ( MMIX, 4th edition), it is a great technical read. Bring so much to Computer Science. I used them in school. I use them today.

Decades ago, when Knuth wrote the first edition of his classic Art of Computer Programming, he invented an assembly language in which to implement the many algorithms of the books. He called it MIX. It was quite representative of the actual assemblers of the time [late 60s]. But time and Moore's Law marched on. The 8 bit nature of MIX grew increasingly outdated.

In response, Knuth gives us here a massively upgraded version, called MMIX. It operates on 64 bit wide data. Yay! Still a classic von Neumann architecture, mind you. But very spiffy. MMIX also has 256 general purpose registers and 32 special purpose registers, where these all are 64 bits wide, naturally. Plus, MMIX lives in an address space of 2**64 bytes of memory.

Unlike the Intel or AMD chips, which are CISC, Knuth opted for a RISC MMIX. So learning the opcodes is very rapid, if you have dealt with assemblers before.

This little text gets you up to speed in MMIX. Consider it as prep for the full volume 4, when that comes out. [Prof. Knuth, it's late.]

But this MMIX book is utterly unlike any other assembler book. It comes replete with programming problems (and answers) of considerable intellectual heft. Conventional assembler books simply don't do this. Their problems tend to be mundane and trivial. This book lets you find surprising conceptual depths hidden under a deceptively simple language. Compare this to chess.

The Art of Computer Programming is a classic from Professor Knuth.

this is required CS reading and should be required for every programmer.

The books are very detailed and take a lot of analysis... they are not written in a current Object Oriented Language... that was a disappointment but otherwise it is very good... just uses old "spaghetti code"

Only an author as smart and well known in his field as Donald Knuth would have tried this unusual format, which he terms a fascicle. In this third little book, he gives another extensive preview of his eventual fourth volume of "The Art of Computer Programming". When it finally appears, this volume is expected to span several books. In the interim, you will have to be content with these fascicles.

Even though this book is so slender, it is chock-a-block with tidbits, in the style of the first three volumes. Thus you can find out about a binomial tree, or even an infinite binomial tree. Or see how the Gray binary code also arises in the context of combinations.

An elegant aspect of this book is how Knuth ties in the discrete math of combinations with calculus applications. Quite often, these are two different worlds of maths, with different practitioners. Knuth uses the example of the varied properties of Bell numbers. Specifically, the rate at which these grow can be estimated by complex residues and saddle point analysis. Surprising results!

First, the brevity. This book nominally contains 160 pages - take off a few for indicia and intro, and it's down to 150. Of those, page 87 and up are all "answers to exercises" - not really part of the exposition. Then, within those 86 pages, about 30 are exercises. Although helpful to the involved reader, they aren't direct exposition either.

The 50 or 60 pages left are good, though. They present the combinatorial content in deep detail, even if breadth sometimes seems to suffer. Proofs and analyses are thorough, but become lengthy and require fair bits of calculus. These discussions range across the width of contemporary math and the length of its last few generations of history.

That leaves the algorithms - a few good ones, but only a few. If you came to this as a cut-and-paster, you won't find much to take home. On the whole, it's a worthy addition to "The Art" and to the collection that makes up Volume 4. For many, however, it won't be the hardest-working reference on the shelf.

-- wiredweird

With 'Cryptography for Developers' by Tom St Denis I am not even going to try and pretend that I am an expert in this field. Written with software developers in mind, this book is a complex look at how software cryptography algorithms are designed and developed. With 400 pages of material contained within and a solid look at the source content, this is a great book for a niche field/market. If you are interested in software cryptography or do it for a job, you will no doubt find this to be a fascinating read.

**** RECOMMENDED

Cryptography for Developers deserves ongoing recommendation as a basic text - the only one written for software developers - probing the foundations of cryptography. Here are details covering message authentication codes, encryption models, public key cryptography, and more that discuss and provide examples of cryptographic goals and security measures. Any software developer serious about security must have this.

A lot of people who have read "Applied Cryptography" by BRuce Schneier are themselves not cryptographers or developing cryptographic software. In fact, very few people actually develop cryptographic software because it's tough to get right and most crypto libraries provide everything you need. However, for those that wish to enter the field, it can be daunting to learn. If you'd like to be one of those few, Tom St Denis' "Cryptography for Developers" may be for you.

The book's writing is clear and focused, not surprising given that the author has written before. St Denis makes a good choice to focus on new material for this book, specifically pointing you at other books for a background in cryptography and "bignum" math (very, very large numbers, which require atypical methods to manipulate).

If you're a C code developer, you'll get the material very well. If you're C isn't very strong, or you need the code for another language, you'll probably have some difficulty in making use of it (depending on how skilled you are with C). However, the code is clear and well annotated, so you can make pretty good sense of it pretty quickly.

Chapter 2 starts off with a bang and covers ASN.1 encoding. This is not a very common topic, so this is one of the only places you may find this sort of thing covered well. Right away you can see what you're in for: very clear background info, good use of illustrations, well written code with lots of annotations, and very sharp focus.

Chapter 3 covers random numbers (specifically RNGs and PRNGs). While you'll want to complement this with something like the CRC Applied Crypto chapters on random numbers, you'll get a pretty good idea of how to gather and make use of random numbers. One probem I noticed here was that notes that Yarrow and Fortuna are RNGs but later (and, I believe, correctly) states that they are PRNG algorithms. Overall, though, a good treatment of the topic and a discussion of where to use random numbers, how to test them, the limits of the tests, and what pitfalls to watch out for.

Chapter 4 is really one of the meaty chapters and covers AES very in depth. Many of the concepts covered here are reused in other chapters, so make sure you get this one under your belt.

Chapters 5 and 6 cover hash functions and message authentication code algorithms, respectively. Again, great treatment of a limited subset of the algorithms out there and very good discussions about the myths, truths, and appropriate uses of the algorithms. Very good, useful insights all around.

Chapter 7 covers encryption and authentication modes, providing you with code that starts to really put it all together.

Chapter 8 covers large integer arithmatic, but also states that it's no replacement for St Denis' other book on BigNum math. Another very useful topic covered here somewhat looks at optimizations and how to make efficient code. Again, valuable insights that you can apple to other topics.

Chapter 9 covers public key algorithms, but sadly doesn't give much code. This is a disappointment and unexpected, given how much code is in the rest of the book. Perhaps it was a length consideration or by design, I don't know.

I'm not a cryptographer, so I can't attest to the veracity of the code. I didn't spot any obvious errors in the code design or use, however. Finally, this book wont replace Applied Crypto (either the Schneier or the CRC tomes), you'll want to use this book in tandem with those volumes. So few algorithms are covered that you'll really want to have studied those first before you can make full use of this volume.

Finally, one other thing that's missing is a unified set of links and references. He would have benefitted the reader had he done so, because so much material is covered and referenced.

St Denis has produced a clear, focused volume that's well organized. If you want to go from algorithm outlines to implementations, this is the book to work with. The quality of the writing and production is higher than many other Syngress books, and that's much appreciated.

You can find all of the source code and errata for this book here:

http://www.lclark.edu/~drake/dsaj.html

(I am the author. I hope it will not be seen as overhyping to rate my own book at 5 stars, but I couldn't find a way to post this information outside of a review, nor to post a review without giving a rating.)

The explanations are good but the examples are too thick and hard to follow if you haven't known the language that long.

Drake wastes little time in getting to his subject. You are expected to already know at least the rudiments of Java. Hopefully of version 1.5, which is the current major release of Java. The numerous code snippets in the text are drawn from this version. Because it has a very extensive set of native classes that implement many of the structures covered by the book.

The text can be read at one or both of two levels. Firstly, you might already be well familiar with such ideas as linked lists, hash tables, trees, graphs, sorting, searching etc. Perhaps from other languages. What you are looking for is a comprehensive description of how these are expressed or can be expressed in Java.

The other level is where you need to learn the data structures and algorithms for the first time. Here, there is a stark contrast with Knuth's classic "Art of Computer Programming". That is a far more advanced text. But the relevant difference in our context is that Knuth requires you to write all the code yourself, in some language. Whereas Drake demonstrates how, right out of the box with Java 1.5, you get so much already implemented, for free. The latter is not figurative. The Java 1.5 distribution is made freely available by Sun.

It should also be said that this book will still be germane when 1.5 is superseded by future versions of Java. You can safely expect that those versions will be supersets of the functionality used in this book, based on the prior history of the major Java versions and how each differed from its predecessor.

This book covers a lot of interesting topics and is very up-to-date with current research results in the field. Its main drawback is that it has few examples. It is also at times hard to follow, unless the reader is already somehow familiar with the material.

The text conists of of 40 'lectures' or chapters, each about 4-5 pages, 10 moderately difficult 'homeworks', each about 3-4 problems and one set of 29 miscellaneous exercises. Solutions to both the homeworks and miscellaneous exercises are provided. The text is based on the notes used by the author at Cornell in a one-semester graduate course.

Each lecture is (largely) self-contained and brief. Being clearly written and concise makes it an excellent choice for those interested in self-study. The homeworks are the key to understanding the material. I would suggest trying for atleast a day before looking up the solutions.

For more comprehensive treatment of the topics dicussed in the book see "The design and analysis of computer algorithms" (Aho, Hopcroft and Ullman) and "Computers and Intractability" (Garey and Johnson).

This book is basically a set of lecture notes used by Prof. Kozen at Cornell, plus some practise 'homework' exercises.

As such, it isn't really a textbook, and can't be used as the only book for a course in the design and analysis of algorithms - for that, you'll need the books by Aho et al, or Cormen et al. (Knuth's books, of course are great for the topics they cover; and while on the book by Cormen et al, there's a second edition now, since September 2001).

However,this is an excellent self-study supplement. There are 40 lectures, each being a concise, self-contained discussion on a chosen topic. Thus, you get a condensed presentation of the important points, along with invaluable insights from Prof. Kozen.

Another feature which makes this a great option for self-study/rapid review is that each chapter ends with 'homeworks', for which answers have been provided. There's a set of miscellaneous exercises as well.

It is important to realize that this is a graduate text, for those who are already familiar with data structures and algorithms. This is not an introductory text by any means, and would ill serve that purpose.

The author presumes a fairly strong background in basic data structures and algorithms as well as mathematics on the part of the reader, without which it may be very difficult to follow the presentation.

All in all, if you're doing a graduate course in the design and analysis of algorithms, then this is a superb choice for self-study, practising problem-solving and rapid review of already familiar topics.

The book is brand new. And it is delivered to me on time for usage.

a must read for anyone interested in cipher design. the authors provide their rationale for the design of Rijndael with theoretical and practical evidence.

This book is great, straight from the designers of Rijndael.

you could not find a better book in the subject.

my only gripe is the price, a bit on the high end.

I am using the case study and guidelines in this book to engineer my own small system interface as a demo to employers AND as demo to potential clients for new product prototype implementation(just getting started on my own business). I find this book to be of excellent value in what the author provides. I would recommend it to anybody who is engineering PC to embedded microcontroller based interfaces.

This is a great book to get use to terminology.
Its great for learning serial communications I2C Communications.
The processes of which.
And it is also a great book from a hardware standpoint.

But for the applications end of the spectrum.
Falls short of complete. Unless you have the money for programs
basically advertised in this book.

A really great book would be titled.
[...]What else do you need?"

And it would be complete with working programs. Not left thinking... "man I need another 1000 or so bucks to do what I need"

It would be good for a reference in your collection.

I recently purchased this book for a project at work. I am a project manager for a large appliance manufacturer and needed to make a decision on which method of communications would be used between a new appliance and personal computer. This book helped me not only assess the best method of communications but also aided in chossing PC development tools and which operating systems to support. This book not only educated me in choosing the right tools to support multiple OS platforms but also in how to compare serial, USB, and ethernet communications. If you need to develop for multiple operating systems or want to understand and compare different methods of PC communications I would highly recommend this book.

This book is nothing short of brilliant. The pace is
relaxed and discplined at the same time, the examples
are interesting, and the coverage surprisingly extensive
for its mere 124 pages. The idea to present Markov chains
in the context of algorithms and applications is innovative
and very useful. There is no other book of its kind.

This is a very clearly written, succinct introduction to Markov Chains (it does not aim to be exhaustive).
I think this book offers one of the most accessible and efficient routes to learning the basics about markov chain monte carlo, perfect simulation,sandwiching and simulated annealing.

I enjoyed this book a lot.Better to read this a few times and do the questions, and then if you must, tackle one of the more bloated expositions.

Markov chains, a sequence of actions with a random element, can be applied to nearly any process that is composed of discrete steps. Such processes include manufacturing operations, building large structures and even visiting web sites on the Internet. This book is a set of lecture notes for a course for advanced undergraduates offered by the author.
It begins with a basic introduction to probability theory and covers some applications of Markov chains that I had never thought about, such as surfing the Internet. There are exercises at the end of each section although solutions are not included. With a section on computer simulation of Markov chains, the book could also be used in a special topics course in computer science, where the emphasis is on optimization.
Markov chains are a valuable tool that should receive more emphasis in the education of math and computer science students. This book can serve as a basic text for classes aimed at both types of student.