Data Structures & Algorithm Analysis in Java
Mark Allen Weiss
Mark Allen Weiss provides a proven approach to algorithms and data structures using the exciting Java programming language as the implementation tool. With Java he highlights conceptual topics, focusing on ADTs and the analysis of algorithms for efficiency as well as performance and running time. Dr. Weiss also distinguishes this text with a logical organization of topics, his engaging writing style and an extensive use of figures and examples showing the successive stages of an algorithm. Included are algorithm and design techniques and amortized analysis, plus a new chapter on advanced data structures and their implementation.
- Contains extensive sample code using Java 1.2, which is available over the Internet.
- Covers the Java Collections Library in an Appendix.
- Includes a chapter on algorithm and design techniques that covers greedy algorithms, divide and conquer algorithms, dynamic programming, randomized algorithms, and backtracking.
- Presents current topics and new data structures such as Fibonacci heaps, skew heaps, binomial queue, skip lists and splay trees.
- Offers a chapter on amortized analysis that examines the advanced data structures presented earlier in the book.
- Provides a chapter on advanced data structures and their implementation covering red black trees, top down splay trees, treaps, k-d trees, pairing heaps, and more.
- Incorporates new results on the average case analysis of heapsort.
A Brief Introduction to Recursion.
Generic Objects in Java.
Input and Output.
What to Analyze.
Running Time Calculations.
Lists, Stacks, and Queues.
The List ADT.
The Stack ADT.
The Queue ADT.
The Search Tree ADT: Binary Search Trees.
Tree Traversals (Revisited).
Priority Queues (Heaps).
Applications of Priority Queues.
A Lower Bound for Simple Sorting Algorithms.
A General Lower Bound for Sorting.
The Disjoint Set ADT.
The Dynamic Equivalence Problem.
Basic Data Structure.
Smart Union Algorithms.
Worst Case for Union-by Rank and Path Compression.
Network Flow Problems.
Minimum Spanning Tree.
Applications of Depth-First Search.
Introduction to NP-Completeness.
Algorithm Design Techniques.
Divide and Conquer.
Advanced Data Structures and Implementation.
Red Black Trees.
Deterministic Skip Lists.
Appendix A: Some Library Routines.
Classes in Package java.io.
Classes in Package java.util.
Appendix B: The Collections Library.
Example: Generating a Concordance.
Example: Shortest Path Calculation. 0201357442T04062001