Algorithms in Java: Parts 1-4, Third Edition

book cover

Algorithms in Java: Parts 1-4, Third Edition

By Robert Sedgewick

Publisher: Addison Wesley
Pub Date: July 23, 2002
ISBN: 0-201-36120-5, 768 pages



Sedgewick has a real gift for explaining concepts in a way that makes them easy to understand. The use of real programs in page-size (or less) chunks that can be easily understood is a real plus. The figures, programs, and tables are a significant contribution to the learning experience of the reader; they make this book distinctive.-William A. Ward, University of South Alabama

This edition of Robert Sedgewick's popular work provides current and comprehensive coverage of important algorithms for Java programmers. Michael Schidlowsky and Sedgewick have developed new Java implementations that both express the methods in a concise and direct manner and provide programmers with the practical means to test them on real applications.

Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 400,000 programmers!

This particular book, Parts 1-4, represents the essential first half of Sedgewick's complete work. It provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. Although the substance of the book applies to programming in any language, the implementations by Schidlowsky and Sedgewick also exploit the natural match between Java classes and abstract data type (ADT) implementations.

Highlights

  • Java class implementations of more than 100 important practical algorithms

  • Emphasis on ADTs, modular programming, and object-oriented programming

  • Extensive coverage of arrays, linked lists, trees, and other fundamental data structures

  • Thorough treatment of algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT implementations (search algorithms)

  • Complete implementations for binomial queues, multiway radix sorting, randomized BSTs, splay trees, skip lists, multiway tries, B trees, extendible hashing, and many other advanced methods

  • Quantitative information about the algorithms that gives you a basis for comparing them

  • More than 1,000 exercises and more than 250 detailed figures to help you learn properties of the algorithms

Whether you are learning the algorithms for the first time or wish to have up-to-date reference material that incorporates new programming styles with classic and new algorithms, you will find a wealth of useful information in this book.

Algorithms in Java: Parts 1-4, Third Edition


Copyright
Preface
    Scope
    Use in the Curriculum
    Algorithms of Practical Use
    Programming Language
    Acknowledgments
Java Consultant's Preface
Notes on Exercises


Part I: Fundamentals

  Chapter 1. Introduction
      Section 1.1. Algorithms
      Section 1.2. A Sample Problem: Connectivity
      Section 1.3. Union–Find Algorithms
      Section 1.4. Perspective
      Section 1.5. Summary of Topics

  Chapter 2. Principles of Algorithm Analysis
      Section 2.1. Implementation and Empirical Analysis
      Section 2.2. Analysis of Algorithms
      Section 2.3. Growth of Functions
      Section 2.4. Big-Oh Notation
      Section 2.5. Basic Recurrences
      Section 2.6. Examples of Algorithm Analysis
      Section 2.7. Guarantees, Predictions, and Limitations

  References for Part One


Part II: Data Structures

  Chapter 3. Elementary Data Structures
      Section 3.1. Building Blocks
      Section 3.2. Arrays
      Section 3.3. Linked Lists
      Section 3.4. Elementary List Processing
      Section 3.5. Memory Allocation for Lists
      Section 3.6. Strings
      Section 3.7. Compound Data Structures

  Chapter 4. Abstract Data Types
      Exercises
      Section 4.1. Collections of Items
      Section 4.2. Pushdown Stack ADT
      Section 4.3. Examples of Stack ADT Clients
      Section 4.4. Stack ADT Implementations
      Section 4.5. Generic Implementations
      Section 4.6. Creation of a New ADT
      Section 4.7. FIFO Queues and Generalized Queues
      Section 4.8. Duplicate and Index Items
      Section 4.9. First-Class ADTs
      Section 4.10. Application-Based ADT Example
      Section 4.11. Perspective

  Chapter 5. Recursion and Trees
      Section 5.1. Recursive Algorithms
      Section 5.2. Divide and Conquer
      Section 5.3. Dynamic Programming
      Section 5.4. Trees
      Section 5.5. Mathematical Properties of Binary Trees
      Section 5.6. Tree Traversal
      Section 5.7. Recursive Binary-Tree Algorithms
      Section 5.8. Graph Traversal
      Section 5.9. Perspective

  References for Part Two


Part III: Sorting

  Chapter 6. Elementary Sorting Methods
      Section 6.1. Rules of the Game
      Section 6.2. Generic Sort Implementations
      Section 6.3. Selection Sort
      Section 6.4. Insertion Sort
      Section 6.5. Bubble Sort
      Section 6.6. Performance Characteristics of Elementary Sorts
      Section 6.7. Algorithm Visualization
      Section 6.8. Shellsort
      Section 6.9. Sorting of Linked Lists
      Section 6.10. Key-Indexed Counting

  Chapter 7. Quicksort
      Section 7.1. The Basic Algorithm
      Section 7.2. Performance Characteristics of Quicksort
      Section 7.3. Stack Size
      Section 7.4. Small Subfiles
      Section 7.5. Median-of-Three Partitioning
      Section 7.6. Duplicate Keys
      Section 7.7. Strings and Vectors
      Section 7.8. Selection

  Chapter 8. Merging and Mergesort
      Section 8.1. Two-Way Merging
      Section 8.2. Abstract In-Place Merge
      Section 8.3. Top-Down Mergesort
      Section 8.4. Improvements to the Basic Algorithm
      Section 8.5. Bottom-Up Mergesort
      Section 8.6. Performance Characteristics of Mergesort
      Section 8.7. Linked-List Implementations of Mergesort
      Section 8.8. Recursion Revisited

  Chapter 9. Priority Queues and Heapsort
      Exercises
      Section 9.1. Elementary Implementations
      Section 9.2. Heap Data Structure
      Section 9.3. Algorithms on Heaps
      Section 9.4. Heapsort
      Section 9.5. Priority-Queue ADT
      Section 9.6. Priority Queues for Client Arrays
      Section 9.7. Binomial Queues

  Chapter 10. Radix Sorting
      Section 10.1. Bits, Bytes, and Words
      Section 10.2. Binary Quicksort
      Section 10.3. MSD Radix Sort
      Section 10.4. Three-Way Radix Quicksort
      Section 10.5. LSD Radix Sort
      Section 10.6. Performance Characteristics of Radix Sorts
      Section 10.7. Sublinear-Time Sorts

  Chapter 11. Special-Purpose Sorting Methods
      Section 11.1. Batcher's Odd–Even Mergesort
      Section 11.2. Sorting Networks
      Section 11.3. Sorting In Place
      Section 11.4. External Sorting
      Section 11.5. Sort–Merge Implementations
      Section 11.6. Parallel Sort–Merge

  References for Part Three


Part IV: Searching

  Chapter 12. Symbol Tables and Binary Search Trees
      Section 12.1. Symbol-Table Abstract Data Type
      Section 12.2. Key-Indexed Search
      Section 12.3. Sequential Search
      Section 12.4. Binary Search
      Section 12.5. Index Implementations with Symbol Tables
      Section 12.6. Binary Search Trees
      Section 12.7. Performance Characteristics of BSTs
      Section 12.8. Insertion at the Root in BSTs
      Section 12.9. BST Implementations of Other ADT Operations

  Chapter 13. Balanced Trees
      Exercises
      Section 13.1. Randomized BSTs
      Section 13.2. Splay BSTs
      Section 13.3. Top-Down 2-3-4 Trees
      Section 13.4. Red–Black Trees
      Section 13.5. Skip Lists
      Section 13.6. Performance Characteristics

  Chapter 14. Hashing
      Section 14.1. Hash Functions
      Section 14.2. Separate Chaining
      Section 14.3. Linear Probing
      Section 14.4. Double Hashing
      Section 14.5. Dynamic Hash Tables
      Section 14.6. Perspective

  Chapter 15. Radix Search
      Section 15.1. Digital Search Trees
      Section 15.2. Tries
      Section 15.3. Patricia Tries
      Section 15.4. Multiway Tries and TSTs
      Section 15.5. Text-String–Index Algorithms

  Chapter 16. External Searching
      Section 16.1. Rules of the Game
      Section 16.2. Indexed Sequential Access
      Section 16.3. B Trees
      Section 16.4. Extendible Hashing
      Section 16.5. Perspective

  References for Part Four


Appendix
    Exercises

Top