Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Java, 3rd edition

  • Mark A. Weiss

Choose the option that's right for you

Single

$9.99 / mo

4-month minimum term for $39.96

  • Access this eText title
  • Up to 2 devices

Multi

$14.99 / mo

4-month minimum term for $59.96

  • Access over 1,500 titles
  • Up to 2 devices
  • Discounted tutor access

Learn more, spend less

  • Icon

    Listen on the go

    Learn how you like with full eText audio

  • Icon

    Learn anytime, anywhere

    Get the app to access your eText whenever you need it

  • Icon

    Make it your own

    Your notes. Your highlights. Your eText

  • Icon

    Find it fast

    Quickly navigate your eText with search

  • Icon

    Stay organized

    Access all your eTexts in one place

Overview

Data Structures and Algorithm Analysis in Java helps you develop well-constructed, 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

ISBN-13: 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 Pre-Java
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
Average-Case Analysis
AVL Trees
Single Rotation
Double Rotation
Splay Trees
A Simple Idea (That Does Not Work)
Splaying
Tree Traversals (Revisited)
B-Trees
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 Worst-Case 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
Heap-Order Property
Basic Heap Operations
Other Heap Operations
Applications of Priority Queues
The Selection Problem
Event Simulation
d-Heaps
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
Worst-Case 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 Linear-Expected-Time Algorithm for Selection
A General Lower Bound for Sorting
Decision Trees
Decision-Tree Lower Bounds for Selection Problems
Adversary Lower Bounds
Linear-Time 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 Union-by-Rank 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
Shortest-Path Algorithms
Unweighted Shortest Paths
Dijkstra's Algorithm
Graphs with Negative Edge Costs
Acyclic Graphs
All-Pairs Shortest Path
Shortest-Path Example
Network Flow Problems
A Simple Maximum-Flow Algorithm
Minimum Spanning Tree
Prim's Algorithm
Kruskal's Algorithm
Applications of Depth-First Search
Undirected Graphs
Biconnectivity
Euler Circuits
Directed Graphs
Finding Strong Components
Introduction to NP-Completeness
Easy vs Hard
The Class NP
NP-Complete 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 Divide-and-Conquer Algorithms
Closest-Points Problem
The Selection Problem
Theoretical Improvements for Arithmetic Problems
Dynamic Programming
Using a Table Instead of Recursion
Ordering Matrix Multiplications
Optimal Binary Search Tree
All-Pairs 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
Top-Down Splay Trees
Red-Black Trees
Bottom-Up Insertion
Top-Down Red-Black Trees
Top-Down Deletion
Treaps
Suffix Arrays and Suffix Trees
Suffix Arrays
Suffix Trees
Linear-Time Construction of Suffix Arrays and Suffix Trees
k-d 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 easy-to-use 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 4-month term. We will charge your payment method each month until your 4-month term has ended. After that, we'll automatically renew your subscription and charge you on a month-to-month basis unless you turn off auto-renewal in My account.

When you purchase a Pearson+ subscription, it will last a minimum of 4 months, and then automatically renew each month thereafter unless you turn off auto-renew in My account.

If you want to stop your subscription at the end of your 4-month term, simply turn off auto-renew from My account. 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 auto-renew 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.