9780321370136

Data Structures and Algorithm Analysis in Java

by
  • ISBN13:

    9780321370136

  • ISBN10:

    0321370139

  • Edition: 2nd
  • Format: Paperback
  • Copyright: 2007-01-01
  • Publisher: Addison Wesley
  • View Upgraded Edition
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
  • Write a Review
List Price: $143.00

Summary

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second.This new edition contains all the enhancements of the new Java 5.0 code including detailed examples and an implementation of a large subset of the Java 5.0 Collections API.This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math.

Table of Contents

Preface xv
Introduction
1(28)
What's the Book About?
1(1)
Mathematics Review
2(5)
Exponents
3(1)
Logarithms
3(1)
Series
4(1)
Modular Arithmetic
5(1)
The P Word
6(1)
A Brief Introduction to Recursion
7(4)
Implementing Generic Components Pre Java 5
11(5)
Using Object for Genericity
12(1)
Wrappers for Primitive Types
12(1)
Using Interface Types for Genericity
13(2)
Compatibility of Array Types
15(1)
Implementing Generic Components Using Java 5 Generics
16(7)
Simple Generic Classes and Interfaces
16(1)
Autoboxing/Unboxing
17(1)
Wildcards with Bounds
18(1)
Generic Static Methods
19(1)
Type Bounds
20(1)
Type Erasure
21(1)
Restrictions on Generics
22(1)
Function Objects
23(6)
Summary
25(1)
Exercises
25(1)
References
26(3)
Algorithm Analysis
29(28)
Mathematical Background
29(3)
Model
32(1)
What to Analyze
32(3)
Running Time Calculations
35(22)
A Simple Example
35(1)
General Rules
36(2)
Solutions for the Maximum Subsequence Sum Problem
38(6)
Logarithms in the Running Time
44(4)
Checking Your Analysis
48(1)
A Grain of Salt
48(2)
Summary
50(1)
Exercises
50(5)
References
55(2)
Lists, Stacks, and Queues
57(44)
Abstract Data Types (ADTs)
57(1)
The List ADT
58(2)
Simple Array Implementation of Lists
58(1)
Simple Linked Lists
59(1)
Lists in the Java Collections API
60(7)
Collection Interface
61(1)
Iterators
62(1)
The List Interface, ArrayList, and LinkedList
63(2)
Example: Using Remove on a LinkedList
65(1)
Listlterators
66(1)
Implementation of ArrayList
67(8)
The Basic Class
68(1)
The Iterator and Java Nested and Inner Classes
68(7)
Implementation of LinkedList
75(7)
The Stack ADT
82(9)
Stack Model
82(1)
Implementation of Stacks
83(1)
Applications
83(8)
The Queue ADT
91(10)
Queue Model
91(1)
Array Implementation of Queues
91(3)
Applications of Queues
94(1)
Summary
95(1)
Exercises
95(6)
Trees
101(68)
Preliminaries
101(6)
Implementation of Trees
102(1)
Tree Traversals with an Application
103(4)
Binary Trees
107(5)
Implementation
108(1)
An Example: Expression Trees
109(3)
The Search Tree ADT---Binary Search Trees
112(11)
contains
113(2)
findMin and findMax
115(1)
insert
115(2)
remove
117(3)
Average-Case Analysis
120(3)
AVL Trees
123(12)
Single Rotation
125(3)
Double Rotation
128(7)
Splay Trees
135(8)
A Simple Idea (That Does Not Work)
135(2)
Splaying
137(6)
Tree Traversals (Revisited)
143(2)
B-Trees
145(5)
Sets and Maps in the Standard Library
150(7)
Sets
151(1)
Maps
151(1)
Implementation of TreeSet and TreeMap
152(1)
An Example That Uses Several Maps
152(5)
Summary
157(12)
Exercises
159(6)
References
165(4)
Hashing
169(32)
General Idea
169(1)
Hash Function
170(2)
Separate Chaining
172(5)
Hash Tables Without Linked Lists
177(9)
Linear Probing
177(2)
Quadratic Probing
179(2)
Double Hashing
181(5)
Rehashing
186(1)
Hash Tables in the Standard Library
187(3)
Extendible Hashing
190(11)
Summary
193(1)
Exercises
194(4)
References
198(3)
Priority Queues (Heaps)
201(46)
Model
201(1)
Simple Implementations
202(1)
Binary Heap
202(12)
Structure Property
203(2)
Heap Order Property
205(1)
Basic Heap Operations
205(5)
Other Heap Operations
210(4)
Applications of Priority Queues
214(2)
The Selection Problem
214(1)
Event Simulation
215(1)
d-Heaps
216(1)
Leftist Heaps
217(8)
Leftist Heap Property
217(1)
Leftist Heap Operations
218(7)
Skew Heaps
225(2)
Binomial Queues
227(10)
Binomial Queue Structure
228(1)
Binomial Queue Operations
229(3)
Implementation of Binomial Queues
232(5)
Priority Queues in the Standard Library
237(10)
Summary
237(2)
Exercises
239(4)
References
243(4)
Sorting
247(46)
Preliminaries
247(1)
Insertion Sort
248(1)
The Algorithm
248(1)
Analysis of Insertion Sort
248(1)
A Lower Bound for Simple Sorting Algorithms
249(1)
Shellsort
250(4)
Worst-Case Analysis of Shellsort
252(2)
Heapsort
254(4)
Analysis of Heapsort
256(2)
Mergesort
258(6)
Analysis of Mergesort
260(4)
Quicksort
264(12)
Picking the Pivot
264(2)
Partitioning Strategy
266(2)
Small Arrays
268(1)
Actual Quicksort Routines
268(3)
Analysis of Quicksort
271(3)
A Linear-Expected-Time Algorithm for Selection
274(2)
A General Lower Bound for Sorting
276(2)
Decision Trees
276(2)
Bucket Sort
278(1)
External Sorting
279(14)
Why We Need New Algorithms
279(1)
Model for External Sorting
279(1)
The Simple Algorithm
279(2)
Multiway Merge
281(1)
Polyphase Merge
282(1)
Replacement Selection
283(1)
Summary
284(1)
Exercises
285(5)
References
290(3)
The Disjoint Set Class
293(24)
Equivalence Relations
293(1)
The Dynamic Equivalence Problem
294(1)
Basic Data Structure
295(4)
Smart Union Algorithms
299(2)
Path Compression
301(2)
Worst Case for Union-by-Rank and Path Compression
303(6)
Analysis of the Union/Find Algorithm
304(5)
An Application
309(8)
Summary
312(1)
Exercises
312(2)
References
314(3)
Graph Algorithms
317(68)
Definitions
317(3)
Representation of Graphs
318(2)
Topological Sort
320(3)
Shortest-Path Algorithms
323(21)
Unweighted Shortest Paths
325(4)
Dijkstra's Algorithm
329(9)
Graphs with Negative Edge Costs
338(1)
Acyclic Graphs
338(4)
All-Pairs Shortest Path
342(1)
Shortest-Path Example
342(2)
Network Flow Problems
344(5)
A Simple Maximum-Flow Algorithm
344(5)
Minimum Spanning Tree
349(6)
Prim's Algorithm
351(2)
Kruskal's Algorithm
353(2)
Applications of Depth-First Search
355(14)
Undirected Graphs
357(1)
Biconnectivity
358(3)
Euler Circuits
361(5)
Directed Graphs
366(1)
Finding Strong Components
367(2)
Introduction to NP-Completeness
369(16)
Easy vs. Hard
369(1)
The Class NP
370(1)
NP-Complete Problems
371(2)
Summary
373(1)
Exercises
373(8)
References
381(4)
Algorithm Design Techniques
385(80)
Greedy Algorithms
385(18)
A Simple Scheduling Problem
386(3)
Huffman Codes
389(6)
Approximate Bin Packing
395(8)
Divide and Conquer
403(15)
Running Time of Divide and Conquer Algorithms
404(2)
Closest-Points Problem
406(5)
The Selection Problem
411(3)
Theoretical Improvements for Arithmetic Problems
414(4)
Dynamic Programming
418(11)
Using a Table Instead of Recursion
418(3)
Ordering Matrix Multiplications
421(3)
Optimal Binary Search Tree
424(2)
All-Pairs Shortest Path
426(3)
Randomized Algorithms
429(11)
Random Number Generators
431(4)
Skip Lists
435(2)
Primality Testing
437(3)
Backtracking Algorithms
440(25)
The Turnpike Reconstruction Problem
440(5)
Games
445(7)
Summary
452(1)
Exercises
452(9)
References
461(4)
Amortized Analysis
465(26)
An Unrelated Puzzle
466(1)
Binomial Queues
466(5)
Skew Heaps
471(2)
Fibonacci Heaps
473(10)
Cutting Nodes in Leftist Heaps
474(2)
Lazy Merging for Binomial Queues
476(4)
The Fibonacci Heap Operations
480(1)
Proof of the Time Bound
480(3)
Splay Trees
483(8)
Summary
487(1)
Exercises
487(2)
References
489(2)
Advanced Data Structures and Implementation
491(50)
Top-Down Splay Trees
491(6)
Red-Black Trees
497(11)
Bottom-Up Insertion
499(2)
Top-Down Red-Black Trees
501(5)
Top-Down Deletion
506(2)
Deterministic Skip Lists
508(5)
AA-Trees
513(8)
Treaps
521(2)
k-d Trees
523(4)
Pairing Heaps
527(14)
Summary
532(2)
Exercises
534(4)
References
538(3)
Index 541

Rewards Program

Write a Review