Data Structures and Algorithm Analysis in Java, 3rd edition
Choose the option that's right for you
Single
$9.99 / mo
$4.99 / mo
For first 4 months, then $9.99 a month, 4month minimum term for $19.96
 Access this eText title
 Up to 2 devices
 Discounted tutor access
Multi
$14.99 / mo
$7.49 / mo
For first 4 months, then $14.99 a month, 4month minimum term for $29.96
 Access over 1,500 titles
 Up to 2 devices
 Discounted tutor access
Learn more, spend less

Learn anytime, anywhere
Get the app to access your eText whenever you need it

Make it your own
Your notes. Your highlights. Your eText

Find it fast
Quickly navigate your eText with search

Stay organized
Access all your eTexts in one place

Easily continue access
Keep learning with autorenew
Overview
Data Structures and Algorithm Analysis in Java helps you develop wellconstructed, maximally efficient programs in Java. Topics are organized logically, and figures and examples illustrate successive stages of algorithms. You'll also have full access to source code complementing the text's coverage.
Published by Pearson (July 14th 2021)  Copyright © 2012
ISBN13: 9780137518821
Subject: Intermediate / Advanced Programming
Category: Data Structures
Table of contents
Introduction
What's the Book About?
1. Mathematics Review
Exponents
Logarithms
Series
Modular Arithmetic
The P Word
A Brief Introduction to Recursion
Implementing Generic Components PreJava
Using Object for Genericity
Wrappers for Primitive Types
Using Interface Types for Genericity
Compatibility of Array Types
Implementing Generic Components Using Java Generics
Simple Generic Classes and Interfaces
Autoboxing/Unboxing
The Diamond Operator
Wildcards with Bounds
Generic Static Methods
Type Bounds
Type Erasure
Restrictions on Generics
Function Objects
Summary
Exercises
References
2. Algorithm Analysis
Mathematical Background
Model
What to Analyze
Running Time Calculations
A Simple Example
General Rules
Solutions for the Maximum Subsequence Sum Problem
Logarithms in the Running Time
A Grain of Salt
Summary
Exercises
References
3. Lists, Stacks, and Queues
Abstract Data Types (ADTs)
The List ADT
Simple Array Implementation of Lists
Simple Linked Lists
Lists in the Java Collections API
Collection Interface
Iterators
The List Interface, ArrayList, and LinkedList
Example: Using remove on a LinkedList
ListIterators
Implementation of ArrayList
The Basic Class
The Iterator and Java Nested and Inner Classes
Implementation of LinkedList
The Stack ADT
Stack Model
Implementation of Stacks
Applications
The Queue ADT
Queue Model
Array Implementation of Queues
Applications of Queues
Summary
Exercises
4. Trees
Preliminaries
Implementation of Trees
Tree Traversals with an Application
Binary Trees
Implementation
An Example: Expression Trees
The Search Tree ADT–Binary Search Trees
contains
findMin and findMax
insert
remove
AverageCase Analysis
AVL Trees
Single Rotation
Double Rotation
Splay Trees
A Simple Idea (That Does Not Work)
Splaying
Tree Traversals (Revisited)
BTrees
Sets and Maps in the Standard Library
Sets
Maps
Implementation of TreeSet and TreeMap
An Example That Uses Several Maps
Summary
Exercises
References
5. Hashing
General Idea
Hash Function
Separate Chaining
Hash Tables Without Linked Lists
Linear Probing
Quadratic Probing
Double Hashing
Rehashing
Hash Tables in the Standard Library
Hash Tables with WorstCase O() Access
Perfect Hashing
Cuckoo Hashing
Hopscotch Hashing
Universal Hashing
Extendible Hashing
Summary
Exercises
References
6. Priority Queues (Heaps)
Model
Simple Implementations
Binary Heap
Structure Property
HeapOrder Property
Basic Heap Operations
Other Heap Operations
Applications of Priority Queues
The Selection Problem
Event Simulation
dHeaps
Leftist Heaps
Leftist Heap Property
Leftist Heap Operations
Skew Heaps
Binomial Queues
Binomial Queue Structure
Binomial Queue Operations
Implementation of Binomial Queues
Priority Queues in the Standard Library
Summary
Exercises
References
7. Sorting
Preliminaries
Insertion Sort
The Algorithm
Analysis of Insertion Sort
A Lower Bound for Simple Sorting Algorithms
Shellsort
WorstCase Analysis of Shellsort
Heapsort
Analysis of Heapsort
Mergesort
Analysis of Mergesort
Quicksort
Picking the Pivot
Partitioning Strategy
Small Arrays
Actual Quicksort Routines
Analysis of Quicksort
A LinearExpectedTime Algorithm for Selection
A General Lower Bound for Sorting
Decision Trees
DecisionTree Lower Bounds for Selection Problems
Adversary Lower Bounds
LinearTime Sorts: Bucket Sort and Radix Sort
External Sorting
Why We Need New Algorithms
Model for External Sorting
The Simple Algorithm
Multiway Merge
Polyphase Merge
Replacement Selection
Summary
Exercises
References
8. The Disjoint Set Class
Equivalence Relations
The Dynamic Equivalence Problem
Basic Data Structure
Smart Union Algorithms
Path Compression
Worst Case for UnionbyRank and Path Compression
Slowly Growing Functions
An Analysis By Recursive Decomposition
An O(M log * N) Bound
An O( M α (M, N) ) Bound
An Application
Summary
Exercises
References
9. Graph Algorithms
Definitions
Representation of Graphs
Topological Sort
ShortestPath Algorithms
Unweighted Shortest Paths
Dijkstra's Algorithm
Graphs with Negative Edge Costs
Acyclic Graphs
AllPairs Shortest Path
ShortestPath Example
Network Flow Problems
A Simple MaximumFlow Algorithm
Minimum Spanning Tree
Prim's Algorithm
Kruskal's Algorithm
Applications of DepthFirst Search
Undirected Graphs
Biconnectivity
Euler Circuits
Directed Graphs
Finding Strong Components
Introduction to NPCompleteness
Easy vs Hard
The Class NP
NPComplete Problems
Summary
Exercises
References
10. Algorithm Design
Techniques
Greedy Algorithms
A Simple Scheduling Problem
Huffman Codes
Approximate Bin Packing
Divide and Conquer
Running Time of DivideandConquer Algorithms
ClosestPoints Problem
The Selection Problem
Theoretical Improvements for Arithmetic Problems
Dynamic Programming
Using a Table Instead of Recursion
Ordering Matrix Multiplications
Optimal Binary Search Tree
AllPairs Shortest Path
Randomized Algorithms
Random Number Generators
Skip Lists
Primality Testing
Backtracking Algorithms
The Turnpike Reconstruction Problem
Games
Summary
Exercises
References
11. Amortized Analysis
An Unrelated Puzzle
Binomial Queues
Skew Heaps
Fibonacci Heaps
Cutting Nodes in Leftist Heaps
Lazy Merging for Binomial Queues
The Fibonacci Heap Operations
Proof of the Time Bound
Splay Trees
Summary
Exercises
References
12. Advanced Data Structures
and Implementation
TopDown Splay Trees
RedBlack Trees
BottomUp Insertion
TopDown RedBlack Trees
TopDown Deletion
Treaps
Suffix Arrays and Suffix Trees
Suffix Arrays
Suffix Trees
LinearTime Construction of Suffix Arrays and Suffix Trees
kd Trees
Pairing Heaps
Summary
Exercises
References
Index
Your questions answered
Introducing Pearson+. Reimagined learning, designed for you. Choose from one eText or over 1,500 eTexts and study tools, all in one place, for one low monthly subscription. A new way to buy books that fits your budget. Make the most of your study time with offline access, enhanced search, notes and flashcards — to get organized, get the work done quicker and get results. Plus, with the app, put textbooks in your pocket and learn wherever. It's time to upgrade the textbook and simplify learning, so you can have time to live too.
Pearson eText is an easytouse digital textbook available from Pearson+. Make it your own by adding notes and highlights. Download the Pearson+ mobile app to learn on the go, even offline. Listen on the go with our new audiobook feature, available for most titles.
When you choose a plan, you're signing up for a 4month 'term'. We will charge your payment method each month until your 4month term has ended. You can turn on autorenew in My account at any time to continue your subscription before your 4month term has ended.
When you purchase a Pearson+ subscription, it will last 4 months. Before your initial 4month term ends, you can extend your subscription by turning autorenew on in My account. If you turn autorenew on, we’ll automatically renew your subscription and charge you every month until you turn off autorenew.
To avoid the next payment charge, make sure you turn auto renewal off 1 day before the auto renewal date. You can subscribe again after autorenew has been turned off by purchasing another Pearson+ subscription. We use your credit card to renew your subscription automatically. To make sure your learning is uninterrupted, please check your card details before your first monthly payment.
With a Multi Pearson+ subscription plan, you can download up to 5 titles on the Pearson+ app from My list on each of your authorized devices every month.
When you're using your Multi Pearson+ subscription plan in a browser, you can select and read from as many titles as you like.