Extended Algorithms and Supporting Analysis
Well put together, with extended coverage of techniques and several advanced algorithms not covered elsewhere.
ORIGINAL DRAFT
Developers always need to understand the applicability of algorithms and the basics of performance analysis. A number of authors and publishers have put together data structure and algorithm books, leveraging Java’s simplified syntax and pointer-free programming features, thus making the program examples more accessible to a larger number of readers. One of the more recent entries is "Data Structures and Algorithm Analysis in Java" by Mark Allen Weiss. Weiss also published a related book called "Data Structures and Problem Solving Using Java". While both books overlap to some extent, they are different enough to consider purchasing individually.
The Introduction chapter provides an overview of basic mathematical concepts, reference objects, exceptions, packages and other basic ideas, laying the foundation for the rest of the book. This book doesn’t spend a lot of time explaining Java, moving directly into Chapter 2, "Algorithm Analysis". This is where the mechanics of measuring algorithm efficiency get explained, taking a closer look at the basic principles and methods you’ll need. Chapter 3 jumps into the first set of data structures, "Lists, Stacks, and Queues". These are covered in most algorithm books and offer little in the way of new information if you’ve read about the topic before.
Chapter 4, "Trees", looks at binary, search and AVL trees, but goes further to explore advanced concepts like Splay Trees and B-Trees. Most algorithm books treat B-Trees as disk-based implementations, but they are introduced here without coupling to any particular memory dependency. Chapter 5 covers "Hashing", touching on various algorithms. Chapter 6 covers "Priority Queues (Heaps)", exploring multiple variations, such as d-heaps, leftist, skew, and binomial queues. Chapter 7 provides a nice review of sorting algorithms and related analysis results, ending the chapter with a bucket sort algorithm.
One of the more interesting chapters in this book is Chapter 8 which explores "The Disjoint Set ADT". Among the solutions presented, are algorithms for handling fast, intelligent union and find operations. This is especially relevant to anyone working with large collections of data which can easily be mapped onto set structures. Chapter 9 covers "Graph Algorithms", with the more expected minimum spanning tree, depth-first and other search algorithms, concluding with a look at what NP-Completeness is all about.
The last three chapters explore design and analysis before looking at more advanced algorithms. Chapter 10, titled "Algorithm Design Techniques" can help developers think about the critical parts of their programs more effectively, calling on several strategies that combine to meet the needs of modern application development. Algorithms like Huffman codes, matrix multiplication, skip lists and random number generators are used as examples worthy of deeper study. Chapter 11, "Amortized Analysis" breaks algorithms into subcomponents for analysis purposes, looking at Fibonacci heaps and splay trees.
The final chapter, Chapter 12, "Advanced Data Structures and Implementation" takes all that’s been covered earlier in the book to the pinnacle with a look at advanced splay trees, red-black trees, deterministic skip lists, AA-trees, Treaps, k-d trees and pairing heaps. Appendix A does little more than list some of the Java class documentation for convenience, but Appendix B takes an effective look at how the Java 1.2 Collections API can be leveraged with a number of algorithms presented in the book.
All in all, this book is a good investment for developers trying to keep up with advanced algorithms. Coverage of data structures and algorithms like splay trees, treaps, disjoint sets, skip lists, AA-trees, and others are not very common, so this book brings a lot to the table. The text is clear, well illustrated and to the point, explaining what you need to know to make the algorithms effective. The analysis and design chapters contribute a great deal to understanding real implementation issues and potential solutions that can help you avoid serious pitfalls. With scaling and performance problems foremost in the minds of Internet developers, this material is well worth reading.