About the Book
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.
Features
-
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.
Related
Books
Algorithms/Advanced Data
Structures - Programming Courses (Algorithms/Advanced
Data Structures)
Table of Contents
Introduction.
What's the Book About?
Mathematics Review.
A Brief Introduction to Recursion.
Generic Objects in Java.
Exceptions.
Input and Output.
Code Organization.
Algorithm Analysis.
Mathematical Background.
Model.
What to Analyze.
Running Time Calculations.
Lists, Stacks, and Queues.
Abstract Data Types (ADTs).
The List ADT.
The Stack ADT.
The Queue ADT.
Trees.
Preliminaries.
Binary Trees.
The Search Tree ADT: Binary Search
Trees.
AVL Trees.
Splay Trees.
Tree Traversals (Revisited).
B-Trees.
Hashing.
General Idea.
Hash Function.
Separate Chaining.
Open Addressing.
Rehasing.
Extendible Hashing.
Priority Queues (Heaps).
Model.
Simple Implementations.
Binary Heap.
Applications of Priority Queues.
d-heaps.
Leftist Heaps.
Skew Heaps.
Binomial Queues.
Sorting.
Preliminaries.
Insertion Sort.
A Lower Bound for Simple Sorting Algorithms.
Shellsort.
Heapsort.
Mergesort.
Quicksort.
A General Lower Bound for Sorting.
Bucket Sort.
External Sorting.
The Disjoint Set ADT.
Equivalence Relations.
The Dynamic Equivalence Problem.
Basic Data Structure.
Smart Union Algorithms.
Path Compression.
Worst Case for Union-by Rank and Path
Compression.
An Application.
Graph Algorithms.
Definitions.
Topological Sort.
Shortest-Path Algorithms.
Network Flow Problems.
Minimum Spanning Tree.
Applications of Depth-First Search.
Introduction to NP-Completeness.
Algorithm Design Techniques.
Greedy Algorithms.
Divide and Conquer.
Dynamic Programming.
Randomized Algorithms.
Backtracking Algorithms.
Amortized Analysis.
An Unrelated Puzzle.
Binomial Queues.
Skew Heaps.
Fibonacci Heaps.
Splay Trees.
Advanced Data Structures and Implementation.
Top-Down Splay Trees.
Red Black Trees.
Deterministic Skip Lists.
AA-Trees.
Treaps.
k-d Trees.
Pairing Heaps.
Appendix A: Some Library Routines.
Classes in Package java.lang.
Classes in Package java.io.
Classes in Package java.util.
Appendix B: The Collections Library.
Introduction.
Basic Classes.
Lists.
Sets.
Maps.
Example: Generating a Concordance.
Example: Shortest Path Calculation. |
