CART

(0) items

Data Structures and Problem Solving Using Java,9780201748352
This item qualifies for
FREE SHIPPING!

FREE SHIPPING OVER $59!

Your order must be $59 or more, you must select US Postal Service Shipping as your shipping preference, and the "Group my items into as few shipments as possible" option when you place your order.

Bulk sales, PO's, Marketplace Items, eBooks, Apparel, and DVDs not included.

Data Structures and Problem Solving Using Java

by
Edition:
2nd
ISBN13:

9780201748352

ISBN10:
0201748355
Format:
Hardcover
Pub. Date:
1/1/2002
Publisher(s):
Addison Wesley
List Price: $109.40
More New and Used
from Private Sellers
Starting at $0.01
See Prices

Rent Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

New Textbook

We're Sorry
Sold Out

Summary

Data Structures and Problem Solving Using Java&&3/e& provides a practical introduction to data structures from a viewpoint of abstract thinking and problem solving, and incorporates the enhancements of Java 5.0.& It includes coverage of generic programming, and content on the design of generic collection classes. This book is appropriate for readers who are familiar with basic Java programming concepts or are new to the language and want to learn how it treats data structures concepts.

Table of Contents

PART I: TOUR OF JAVA
Primitive Java
3(24)
The General Environment
4(1)
The First Program
5(1)
Comments
5(1)
main
6(1)
Terminal Output
6(1)
Primitive Types
6(2)
The Primitive Types
6(1)
Constants
7(1)
Declaration and Initialization of Primitive Types
8(1)
Terminal Input and Output
8(1)
Basic Operators
8(3)
Assignment Operators
9(1)
Binary Arithmetic Operators
10(1)
Unary Operators
10(1)
Type Conversions
10(1)
Conditional Statements
11(7)
Relational and Equality Operators
11(1)
Logical Operators
12(1)
The if Statement
13(1)
The while Statement
14(1)
The for Statement
14(1)
The do Statement
15(1)
break and continue
16(1)
The switch Statement
17(1)
The Conditional Operator
17(1)
Methods
18(9)
Overloading of Method Names
19(1)
Storage Classes
20(1)
Summary
20(1)
Objects of the Game
20(2)
Common Errors
22(1)
On the Internet
23(1)
Exercises
23(2)
References
25(2)
Reference Types
27(34)
What Is a Reference?
27(3)
Basics of Objects and References
30(5)
The Dot Operator (.)
30(1)
Declaration of Objects
30(1)
Garbage Collection
31(1)
The Meaning of =
32(1)
Parameter Passing
33(1)
The Meaning of ==
33(1)
No Operator Overloading for Objects
34(1)
Strings
35(2)
Basics of String Manipulation
35(1)
String Concatenation
35(1)
Comparing Strings
36(1)
Other String Methods
36(1)
Converting Other Types of Strings
37(1)
Arrays
37(10)
Declaration, Assignment, and Methods
38(2)
Dynamic Array Expansion
40(3)
ArrayList
43(2)
Multidimensional Arrays
45(1)
Command-line Arguments
45(2)
Exception Handling
47(3)
Processing Exceptions
47(1)
The finally Clause
47(2)
Common Exceptions
49(1)
The throw and throws Clauses
50(1)
Input and Output
50(11)
Basic Stream Operations
51(1)
The StringTokenizer Type
52(1)
Sequential Files
53(2)
Summary
55(2)
Objects of the Game
57(1)
Common Errors
58(1)
On the Internet
59(1)
Exercises
59(1)
References
60(1)
Objects and Classes
61(28)
What Is Object-Oriented Programming?
61(2)
A Simple Example
63(2)
Javadoc
65(3)
Basic Methods
68(3)
Constructors
68(1)
Mutators and Accessors
68(2)
Output and toString
70(1)
equals
70(1)
main
70(1)
Static Fields and Methods
71(1)
Additional Constructs
71(5)
The this Reference
71(1)
The this Shorthand for Constructors
72(1)
The instanceof Operator
72(1)
Instance Members vs. Static Members
73(1)
Static Fields and Methods
73(1)
Static Initializers
74(2)
Packages
76(4)
The import Directive
76(2)
The package Statement
78(1)
The CLASSPATH Environment Variable
78(1)
Package Visibility Rules
79(1)
A Design Pattern: Composite (Pair)
80(9)
Summary
81(2)
Objects of the Game
83(1)
Common Errors
84(1)
On the Internet
85(1)
Exercises
85(3)
References
88(1)
Inheritance
89(58)
What Is Inheritance?
90(13)
Creating New Classes
90(5)
Type Compatibility
95(1)
Dynamic Binding and Polymorphism
96(1)
Inheritance Hierarchies
97(1)
Visibility Rules
97(1)
The Constructor and super
98(1)
final Methods and Classes
99(1)
Overriding a Method
100(1)
Type Compatibility Revisited
101(2)
Designing Hierarchies
103(6)
Abstract Methods and Classes
107(2)
Multiple Inheritance
109(1)
The Interface
110(3)
Specifying an Interface
110(1)
Implementing an Interface
111(1)
Multiple Interfaces
112(1)
Interfaces are Abstract Classes
112(1)
Fundamental Inheritance in Java
113(5)
The Object Class
113(1)
The Hierarchy of Exceptions
113(1)
I/O: The Decorator Pattern
113(5)
Implementing Generic Components
118(7)
Using Object for Genericity
119(1)
Wrappers for Primitive Types
120(1)
Adapters: Changing an Interface
120(3)
Using Interface Types for Genericity
123(2)
The Functor (Function Objects)
125(6)
Nested Classes
128(1)
Local Classes
129(1)
Anonymous Classes
130(1)
Dynamic Binding Details
131(16)
Summary
135(1)
Objects of the Game
136(2)
Common Errors
138(1)
On the Internet
138(2)
Exercises
140(4)
References
144(3)
PART II: ALGORITHMS AND BUILDING BLOCKS
Algorithm Analysis
147(36)
What Is Algorithm Analysis?
148(3)
Examples of Algorithm Running Times
151(2)
The Maximum Contiguous Subsequence Sum Problem
153(7)
The Obvious O(N3) Algorithm
154(3)
An Improved O(N2) Algorithm
157(1)
A Linear Algorithm
158(2)
General Big-Oh Rules
160(4)
The Logarithm
164(3)
Static Searching Problem
167(4)
Sequential Search
167(1)
Binary Search
168(2)
Interpolation Search
170(1)
Checking an Algorithm Analysis
171(2)
Limitations of Big-Oh Analysis
173(10)
Summary
174(1)
Objects of the Game
174(1)
Common Errors
175(1)
On the Internet
175(1)
Exercises
176(5)
References
181(2)
The Collections API
183(48)
Introduction
184(1)
The Iterator Pattern
185(5)
Basic Iterator Design
186(2)
Inheritance-based Iterators and Factories
188(2)
Collections API: Containers and Iterators
190(5)
The Collection Interface
190(3)
Iterator Interface
193(2)
Generic Algorithms
195(4)
Comparator Function Objects
195(1)
The Collections Class
195(3)
Binary Search
198(1)
Sorting
199(1)
The List Interface
199(6)
The ListIterator Interface
201(1)
LinkedList Class
202(3)
Stacks and Queues
205(4)
Stacks
205(1)
Stacks and Computer Languages
206(2)
Queues
208(1)
Stacks and Queues in the Collections API
208(1)
Sets
209(7)
The TreeSet Class
210(1)
The HashSet Class
211(5)
Maps
216(4)
Priority Queues
220(11)
Summary
224(1)
Objects of the Game
225(1)
Common Errors
226(1)
On the Internet
226(1)
Exercises
227(3)
References
230(1)
Recursion
231(52)
What Is Recursion?
232(1)
Background: Proofs by Mathematical Induction
233(2)
Basic Recursion
235(13)
Printing Numbers in Any Base
237(2)
Why It Works
239(2)
How It Works
241(1)
Too Much Recursion Can Be Dangerous
242(1)
Preview of Trees
243(1)
Additional Examples
244(4)
Numerical Applications
248(9)
Modular Arithmetic
250(1)
Modular Exponentiation
250(2)
Greatest Common Divisor and Multiplicative Inverses
252(2)
The RSA Cryptosystem
254(3)
Divide-and-Conquer Algorithms
257(10)
The Maximum Contiguous Subsequence Sum Problem
258(2)
Analysis of a Basic Divide-and-Conquer Recurrence
260(5)
A General Upper Bound for Divide-and-Conquer Running Times
265(2)
Dynamic Programming
267(5)
Backtracking
272(11)
Summary
276(1)
Objects of the Game
276(1)
Common Errors
277(1)
On the Internet
278(1)
Exercises
278(4)
References
282(1)
Sorting Algorithms
283(40)
Why Is Sorting Important?
284(1)
Preliminaries
285(1)
Analysis of the Insertion Sort and Other Simple Sorts
285(4)
Shellsort
289(4)
Performance of Shellsort
290(3)
Mergesort
293(2)
Linear-Time Merging of Sorted Arrays
293(2)
The Mergesort Algorithm
295(1)
Quicksort
295(16)
The Quicksort Algorithm
296(3)
Analysis of Quicksort
299(4)
Picking the Pivot
303(1)
A Partitioning Strategy
304(3)
Keys Equal to the Pivot
307(1)
Median-of-Three Partitioning
307(1)
Small Arrays
308(1)
Java Quicksort Routine
309(2)
Quickselect
311(1)
A Lower Bound for Sorting
312(11)
Summary
314(1)
Objects of the Game
315(1)
Common Errors
315(1)
On the Internet
316(1)
Exercises
316(4)
References
320(3)
Randomization
323(24)
Why Do We Need Random Numbers?
323(1)
Random Number Generators
324(6)
Nonuniform Random Numbers
330(3)
Generating a Random Permutation
333(1)
Randomized Algorithms
334(3)
Randomized Primality Testing
337(10)
Summary
340(1)
Objects of the Game
340(1)
Common Errors
341(1)
On the Internet
342(1)
Exercises
342(2)
References
344(3)
PART III: APPLICATIONS
Fun and Games
347(22)
Word Search Puzzles
347(3)
Theory
348(2)
Java Implementation
350(1)
The Game of Tic-Tac-Toe
350(19)
Alpha-Beta Pruning
353(6)
Transposition Tables
359(3)
Computer Chess
362(2)
Summary
364(1)
Objects of the Game
364(1)
Common Errors
364(1)
On the Internet
365(1)
Exercises
365(2)
References
367(2)
Stacks and Compilers
369(30)
Balanced-Symbol Checker
369(11)
Basic Algorithm
370(1)
Implementation
371(9)
A Simple Calculator
380(19)
Postfix Machines
382(1)
Infix to Postfix Conversion
383(3)
Implementation
386(5)
Expression Trees
391(4)
Summary
395(1)
Objects of the Game
396(1)
Common Errors
396(1)
On the Internet
397(1)
Exercises
397(1)
References
398(1)
Utilities
399(30)
File Compression
399(21)
Prefix Codes
401(2)
Huffman's Algorithm
403(2)
Implementation
405(15)
A Cross-Reference Generator
420(9)
Basic Ideas
420(1)
Java Implementation
420(4)
Summary
424(1)
Objects of the Game
425(1)
Common Errors
425(1)
On the Internet
425(1)
Exercises
425(3)
References
428(1)
Simulation
429(18)
The Josephus Problem
429(6)
The Simple Solution
431(1)
A More Efficient Algorithm
431(4)
Event-Driven Simulation
435(12)
Basic Ideas
435(1)
Example: A Modem Bank Simulation
436(8)
Summary
444(1)
Objects of the Game
444(1)
Common Errors
444(1)
On the Internet
444(1)
Exercises
445(2)
Graphs and Paths
447(46)
Definitions
448(11)
Representation
449(10)
Unweighted Shortest-Path Problem
459(8)
Theory
462(4)
Java Implementation
466(1)
Positive-Weighted, Shortest-Path Problem
467(4)
Theory: Dijkstra's Algorithm
467(2)
Java Implementation
469(2)
Negative-Weighted, Shortest-Path Problem
471(3)
Theory
473(1)
Java Implementation
474(1)
Path Problems in Acyclic Graphs
474(19)
Topological Sorting
474(2)
Theory of the Acyclic Shortest-Path Algorithm
476(2)
Java Implementation
478(2)
An Application: Critical-Path Analysis
480(3)
Summary
483(1)
Objects of the Game
483(2)
Common Errors
485(1)
On the Internet
485(1)
Exercises
485(4)
References
489(4)
PART IV: IMPLEMENTATIONS
Inner Classes and Implementation of ArrayList
493(20)
Iterators and Nested Classes
493(2)
Iterators and Inner Classes
495(5)
The AbstractCollection Class
500(1)
Implementation of ArrayList with an Iterator
500(13)
Summary
508(1)
Objects of the Game
508(1)
Common Error
508(1)
On the Internet
509(1)
Exercises
509(4)
Stacks and Queues
513(24)
Dynamic Array Implementations
513(11)
Stacks
514(4)
Queues
518(6)
Linked List Implementations
524(6)
Stacks
524(1)
Queues
525(5)
Comparison of the Two Methods
530(1)
The java.util.Stack Class
531(2)
Double-Ended Queues
533(4)
Summary
534(1)
Objects of the Game
534(1)
Common Errors
534(1)
On the Internet
534(1)
Exercises
535(2)
Linked Lists
537(32)
Basic Ideas
537(5)
Header Nodes
539(2)
Iterator Classes
541(1)
Java Implementation
542(6)
Doubly Linked Lists and Circularly Linked Lists
548(3)
Sorted Linked Lists
551(1)
Implementing the Collections API LinkedList Class
551(18)
Summary
563(1)
Objects of the Game
563(1)
Common Errors
563(1)
On the Internet
563(1)
Exercises
564(5)
Trees
569(34)
General Trees
569(7)
Definitions
570(1)
Implementation
571(1)
An Application: File Systems
572(4)
Binary Trees
576(6)
Recursion and Trees
582(3)
Tree Traversal: Iterator Classes
585(18)
Postorder Traversal
589(3)
Inorder Traversal
592(1)
Preorder Traversal
592(4)
Level-Order Traversals
596(1)
Summary
597(1)
Objects of the Game
598(1)
Common Errors
599(1)
On the Internet
599(1)
Exercises
600(3)
Binary Search Trees
603(80)
Basic Ideas
603(10)
The Operations
604(2)
Java Implementation
606(7)
Order Statistics
613(5)
Java Implementation
614(4)
Analysis of Binary Search Tree Operations
618(3)
AVL Trees
621(9)
Properties
622(2)
Single Rotation
624(3)
Double Rotation
627(3)
Summary of AVL Insertion
630(1)
Red-Black Trees
630(14)
Bottom-Up Insertion
631(3)
Top-Down Red-Black Trees
634(2)
Java Implementation
636(5)
Top-Down Deletion
641(3)
AA-Trees
644(10)
Insertion
646(2)
Deletion
648(1)
Java Implementation
649(5)
Implementing the Collections API TreeSet and TreeMap Classes
654(9)
B-Trees
663(20)
Summary
675(1)
Objects of the Game
676(1)
Common Errors
677(1)
On the Internet
677(1)
Exercises
678(2)
References
680(3)
Hash Tables
683(32)
Basic Ideas
684(1)
Hash Function
685(2)
Linear Probing
687(6)
Naive Analysis of Linear Probing
689(1)
What Really Happens: Primary Clustering
690(1)
Analysis of the find Operation
691(2)
Quadratic Probing
693(13)
Java Implementation
697(6)
Analysis of Quadratic Probing
703(3)
Separate Chaining Hashing
706(1)
Hash Tables Versus Binary Search Trees
707(1)
Hashing Applications
707(8)
Summary
708(1)
Objects of the Game
708(1)
Common Errors
709(1)
On the Internet
710(1)
Exercises
710(2)
References
712(3)
A Priority Queue: The Binary Heap
715(36)
Basic Ideas
716(5)
Structure Property
716(2)
Heap-Order Property
718(1)
Allowed Operations
718(3)
Implementation of the Basic Operations
721(5)
The insert Operation
722(1)
The deleteMin Operation
723(3)
The buildHeap Operation: Linear-Time Heap Construction
726(5)
Advanced Operations: decreaseKey and merge
731(1)
Internal Sorting: Heapsort
731(3)
External Sorting
734(17)
Why We Need New Algorithms
734(1)
Model for External Sorting
735(1)
The Simple Algorithm
735(2)
Multiway Merge
737(1)
Polyphase Merge
738(2)
Replacement Selection
740(1)
Summary
741(1)
Objects of the Game
741(1)
Common Errors
742(1)
On the Internet
742(1)
Exercises
743(4)
References
747(4)
PART V: ADVANCED DATA STRUCTURES
Splay Trees
751(28)
Self-Adjustment and Amortized Analysis
752(3)
Amortized Time Bounds
753(1)
A Simple Self-Adjusting Strategy (That Does Not Work)
753(2)
The Basic Bottom-Up Splay Tree
755(3)
Basic Splay Tree Operations
758(1)
Analysis of Bottom-Up Splaying
759(6)
Proof of the Splaying Bound
762(3)
Top-Down Splay Trees
765(3)
Implementation of Top-Down Splay Trees
768(3)
Comparison of the Splay Tree with Other Search Trees
771(8)
Summary
773(1)
Objects of the Game
773(3)
Common Errors
776(1)
On the Internet
776(1)
Exercises
776(1)
References
777(2)
Merging Priority Queues
779(22)
The Skew Heap
779(5)
Merging Is Fundamental
780(1)
Simplistic Merging of Heap-Ordered Trees
780(1)
The Skew Heap: A Simple Modification
781(1)
Analysis of the Skew Heap
782(2)
The Pairing Heap
784(17)
Pairing Heap Operations
785(1)
Implementation of the Pairing Heap
786(5)
Application: Dijkstra's Shortest Weighted Path Algorithm
791(5)
Summary
796(1)
Objects of the Game
796(1)
Common Errors
796(1)
On the Internet
797(1)
Exercises
797(1)
References
798(3)
The Disjoint Set Class
801(70)
Equivalence Relations
802(1)
Dynamic Equivalence and Applications
802(11)
Application: Generating Mazes
803(3)
Application: Minimum Spanning Trees
806(3)
Application: The Nearest Common Ancestor Problem
809(4)
The Quick-Find Algorithm
813(1)
The Quick-Union Algorithm
814(4)
Smart Union Algorithms
815(2)
Path Compression
817(1)
Java Implementation
818(3)
Worst Case for Union-by-Rank and Path Compression
821(14)
Analysis of the Union/Find Algorithm
822(6)
Summary
828(1)
Objects of the Game
829(1)
Common Errors
830(1)
On the Internet
830(1)
Exercises
830(3)
References
833(2)
APPENDICES
Appendix A Operators
835(2)
Appendix B Graphical User Interfaces
837(30)
B.1 The Abstract Window Toolkit and Swing
838(1)
B.2 Basic Objects in Swing
839(1)
B.2.1 Component
839(2)
B.2.2 Container
841(1)
B.2.3 Top-level Containers
841(1)
B.2.4 JPanel
842(1)
B.2.5 Important I/O Components
843(5)
B.3 Basic Principles
848(1)
B.3.1 Layout Managers
848(4)
B.3.2 Graphics
852(1)
B.3.3 Events
853(3)
B.3.4 Event Handling: Adapters and Anonymous Inner Classes
856(3)
B.3.5 Summary: Putting the Pieces Together
859(1)
B.3.6 Is This Everything I Need To Know About Swing?
860(1)
Summary
860(1)
Objects of the Game
861(2)
Common Errors
863(1)
On the Internet
863(1)
Exercises
863(2)
Reference
865(2)
Appendix C Bitwise Operators
867(4)
Index 871


Please wait while the item is added to your cart...