Data Structures and Problem Solving Using Java

by Weiss, Mark Allen

• ISBN13: 9780201748352
• ISBN10: 0201748355
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-01-01
• Publisher: Addison Wesley

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