Data Structures and Problem Solving Using Java

by Weiss, Mark A.

• ISBN13: 9780321322135
• ISBN10: 0321322134
• Edition: 4th
• Format: Hardcover
• Copyright: 2010-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 one Tour of Java
primitive java	3	(22)
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	7	(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	(7)
overloading of method names	19	(1)
storage classes	20	(1)
summary	20	(1)
key concepts	20	(2)
common errors	22	(1)
on the internet	23	(1)
exercises	23	(2)
references	25	(38)
reference types	27	(1)
what is a reference?	27	(8)
basics of objects and references	30	(1)
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 to strings	37	(1)
arrays	37	(11)
declaration, assignment, and methods	38	(2)
dynamic array expansion	40	(3)
ArrayList	43	(2)
multidimensional arrays	45	(1)
command-line arguments	46	(1)
enhanced for loop	46	(2)
exception handling	48	(3)
processing exceptions	48	(1)
the finally clause	48	(2)
common exceptions	50	(1)
the throw and throws clauses	51	(1)
input and output	51	(12)
basic stream operations	52	(1)
the StringTokenizer type	53	(2)
sequential files	55	(3)
summary	58	(1)
key concepts	58	(2)
common errors	60	(1)
on the internet	60	(1)
exercises	61	(1)
references	62	(1)
objects and classes	63	(30)
what is object-oriented programming?	63	(2)
a simple example	65	(2)
javadoc	67	(3)
basic methods	70	(3)
constructors	70	(1)
mutators and accessors	70	(2)
output and toString	72	(1)
equals	72	(1)
main	72	(1)
static fields and methods	72	(1)
additional constructs	73	(5)
the this reference	73	(1)
the this shorthand for constructors	74	(1)
the instanceof operator	74	(1)
instance members versus static members	75	(1)
static fields and methods	75	(2)
static initializers	77	(1)
packages	78	(4)
the import directive	78	(2)
the package statement	80	(1)
the Classpath environment variable	81	(1)
package visibility rules	82	(1)
a design pattern: composite (pair)	82	(11)
summary	83	(1)
key concepts	84	(3)
common errors	87	(1)
on the internet	87	(1)
exercises	88	(3)
references	91	(2)
inheritance	93	(70)
what is inheritance?	94	(15)
creating new classes	94	(5)
type compatibility	99	(1)
dynamic dispatch and polymorphism	100	(1)
inheritance hierarchies	101	(1)
visibility rules	101	(1)
the constructor and super	102	(1)
final methods and classes	103	(2)
overriding a method	105	(1)
type compatibility revisited	105	(3)
compatibility of array types	108	(1)
covariant return types	108	(1)
designing hierarchies	109	(5)
abstract methods and classes	110	(4)
multiple inheritance	114	(1)
the interface	115	(3)
specifying an interface	115	(1)
implementing an interface	116	(1)
multiple interfaces	117	(1)
interfaces are abstract classes	117	(1)
fundamental inheritance in java	118	(6)
the Object class	118	(1)
the hierarchy of exceptions	119	(1)
i/o: the decorator pattern	120	(4)
implementing generic components using inheritance	124	(7)
using Object for genericity	124	(1)
wrappers for primitive types	125	(2)
autoboxing/unboxing	127	(1)
adapters: changing an interface	128	(1)
using interface types for genericity	129	(2)
implementing generic components using java 1.5 generics	131	(6)
simple generic classes and interfaces	131	(1)
wildcards with bounds	132	(1)
generic static methods	133	(1)
type bounds	134	(1)
type erasure	135	(1)
restrictions on generics	136	(1)
the functor (function objects)	137	(9)
nested classes	142	(1)
local classes	143	(1)
anonymous classes	144	(1)
nested classes and generics	145	(1)
dynamic dispatch details	146	(17)
summary	149	(1)
key concepts	150	(2)
common errors	152	(1)
on the internet	153	(1)
exercises	154	(6)
references	160	(3)
part two Algorithms and Building Blocks
algorithm analysis	163	(38)
what is algorithm analysis?	164	(4)
examples of algorithm running times	168	(1)
the maximum contiguous subsequence sum problem	169	(8)
the obvious O(N3) algorithm	170	(3)
an improved O(N2) algorithm	173	(1)
a linear algorithm	173	(4)
general big-oh rules	177	(4)
the logarithm	181	(2)
static searching problem	183	(5)
sequential search	183	(1)
binary search	184	(3)
interpolation search	187	(1)
checking an algorithm analysis	188	(1)
limitations of big-oh analysis	189	(12)
summary	190	(1)
key concepts	190	(1)
common errors	191	(1)
on the internet	192	(1)
exercises	192	(7)
references	199	(2)
the collections api	201	(50)
introduction	202	(1)
the iterator pattern	203	(5)
basic iterator design	204	(2)
inheritance-based iterators and factories	206	(2)
collections api: containers and iterators	208	(6)
the Collection interface	209	(3)
Iterator interface	212	(2)
generic algorithms	214	(6)
Comparator function objects	215	(1)
the Collections class	215	(3)
binary search	218	(1)
sorting	218	(2)
the List interface	220	(5)
the ListIterator interface	221	(2)
LinkedList class	223	(2)
stacks and queues	225	(3)
stacks	225	(1)
stacks and computer languages	226	(1)
queues	227	(1)
stacks and queues in the collections api	228	(1)
sets	228	(8)
the TreeSet class	229	(2)
the HashSet class	231	(5)
maps	236	(3)
priority queues	239	(12)
summary	243	(1)
key concepts	244	(1)
common errors	245	(1)
on the internet	245	(1)
exercises	246	(3)
references	249	(2)
recursion	251	(52)
what is recursion?	252	(1)
background: proofs by mathematical induction	253	(2)
basic recursion	255	(14)
printing numbers in any base	257	(2)
why it works	259	(2)
how it works	261	(1)
too much recursion can be dangerous	262	(1)
preview of trees	263	(1)
additional examples	264	(5)
numerical applications	269	(8)
modular arithmetic	269	(1)
modular exponentiation	270	(2)
greatest common divisor and multiplicative inverses	272	(3)
the rsa cryptosystem	275	(2)
divide-and-conquer algorithms	277	(10)
the maximum contiguous subsequence sum problem	278	(3)
analysis of a basic divide-and-conquer recurrence	281	(4)
a general upper bound for divide-and-conquer running times	285	(2)
dynamic programming	287	(4)
backtracking	291	(12)
summary	294	(2)
key concepts	296	(1)
common errors	297	(1)
on the internet	297	(1)
exercises	298	(4)
references	302	(1)
sorting algorithms	303	(40)
why is sorting important?	304	(1)
preliminaries	305	(1)
analysis of the insertion sort and other simple sorts	305	(4)
shellsort	309	(4)
performance of shellsort	310	(3)
mergesort	313	(3)
linear-time merging of sorted arrays	313	(2)
the mergesort algorithm	315	(1)
quicksort	316	(15)
the quicksort algorithm	317	(3)
analysis of quicksort	320	(3)
picking the pivot	323	(2)
a partitioning strategy	325	(2)
keys equal to the pivot	327	(1)
median-of-three partitioning	327	(1)
small arrays	328	(1)
java quicksort routine	329	(2)
quickselect	331	(1)
a lower bound for sorting	332	(11)
summary	334	(1)
key concepts	335	(1)
common errors	336	(1)
on the internet	336	(1)
exercises	336	(5)
references	341	(2)
randomization	343	(24)
why do we need random numbers?	343	(1)
random number generators	344	(5)
nonuniform random numbers	349	(4)
generating a random permutation	353	(1)
randomized algorithms	354	(3)
randomized primality testing	357	(10)
summary	360	(1)
key concepts	360	(1)
common errors	361	(1)
on the internet	362	(1)
exercises	362	(2)
references	364	(3)
part three Applications
fun and games	367	(22)
word search puzzles	367	(6)
theory	368	(1)
java implementation	369	(4)
the game of tic-tac-toe	373	(16)
alpha-beta pruning	374	(3)
transposition tables	377	(4)
computer chess	381	(3)
summary	384	(1)
key concepts	384	(1)
common errors	384	(1)
on the internet	384	(1)
exercises	385	(2)
references	387	(2)
stacks and compilers	389	(30)
balanced-symbol checker	389	(11)
basic algorithm	390	(1)
implementation	391	(9)
a simple calculator	400	(19)
postfix machines	402	(1)
infix to postfix conversion	403	(2)
implementation	405	(9)
expression trees	414	(1)
summary	415	(1)
key concepts	416	(1)
common errors	416	(1)
on the internet	417	(1)
exercises	417	(1)
references	418	(1)
utilities	419	(32)
file compression	420	(21)
prefix codes	421	(2)
huffman's algorithm	423	(2)
implementation	425	(16)
a cross-reference generator	441	(10)
basic ideas	441	(1)
java implementation	441	(4)
summary	445	(1)
key concepts	446	(1)
common errors	446	(1)
on the internet	446	(1)
exercises	446	(4)
references	450	(1)
simulation	451	(20)
the josephus problem	451	(6)
the simple solution	453	(1)
a more efficient algorithm	453	(4)
event-driven simulation	457	(14)
basic ideas	457	(1)
example: a modem bank simulation	458	(8)
summary	466	(1)
key concepts	466	(1)
common errors	467	(1)
on the internet	467	(1)
exercises	467	(4)
graphs and paths	471	(68)
definitions	472	(11)
representation	474	(9)
unweighted shortest-path problem	483	(6)
theory	483	(6)
java implementation	489	(1)
positive-weighted, shortest-path problem	489	(7)
theory: dijkstra's algorithm	490	(4)
java implementation	494	(2)
negative-weighted, shortest-path problem	496	(3)
theory	496	(1)
java implementation	497	(2)
path problems in acyclic graphs	499	(19)
topological sorting	499	(2)
theory of the acyclic shortest-path algorithm	501	(1)
java implementation	501	(3)
an application: critical-path analysis	504	(2)
summary	506	(1)
key concepts	507	(1)
common errors	508	(1)
on the internet	509	(1)
exercises	509	(4)
references	513	(5)
part four Implementations
inner classes and implementation of ArrayList
iterators and nested classes	518	(2)
iterators and inner classes	520	(4)
the AbstractCollection class	524	(4)
StringBuilder	528	(1)
implementation of ArrayList with an iterator	529	(10)
summary	534	(1)
key concepts	535	(1)
common errors	535	(1)
on the internet	535	(1)
exercises	535	(4)
stacks and queues	539	(24)
dynamic array implementations	539	(10)
stacks	540	(4)
queues	544	(5)
linked list implementations	549	(8)
stacks	550	(3)
queues	553	(4)
comparison of the two methods	557	(1)
the java.util.Stack class	557	(2)
double-ended queues	559	(4)
summary	559	(1)
key concepts	559	(1)
common errors	559	(1)
on the internet	559	(1)
exercises	560	(3)
linked lists	563	(32)
basic ideas	563	(5)
header nodes	565	(1)
iterator classes	566	(2)
java implementation	568	(6)
doubly linked lists and circularly linked lists	574	(3)
sorted linked lists	577	(2)
implementing the collections api LinkedList class	579	(16)
summary	590	(1)
key concepts	590	(1)
common errors	591	(1)
on the internet	591	(1)
exercises	591	(4)
trees	595	(34)
general trees	595	(7)
definitions	596	(1)
implementation	597	(1)
an application: file systems	598	(4)
binary trees	602	(7)
recursion and trees	609	(2)
tree traversal: iterator classes	611	(18)
postorder traversal	615	(4)
inorder traversal	619	(1)
preorder traversal	619	(3)
level-order traversals	622	(1)
summary	623	(1)
key concepts	624	(1)
common errors	625	(1)
on the internet	626	(1)
exercises	626	(3)
binary search trees	629	(84)
basic ideas	629	(10)
the operations	630	(2)
java implementation	632	(7)
order statistics	639	(5)
java implementation	640	(4)
analysis of binary search tree operations	644	(4)
avl trees	648	(9)
properties	649	(2)
single rotation	651	(3)
double rotation	654	(2)
summary of avl insertion	656	(1)
red-black trees	657	(13)
bottom-up insertion	658	(2)
top-down red-black trees	660	(1)
java implementation	661	(7)
top-down deletion	668	(2)
aa-trees	670	(10)
insertion	672	(2)
deletion	674	(1)
java implementation	675	(5)
implementing the collections apl TreeSet and TreeMap classes	680	(18)
b-trees	698	(15)
summary	704	(1)
key concepts	705	(1)
common errors	706	(1)
on the internet	706	(1)
exercises	707	(2)
references	709	(4)
hash tables	713	(32)
basic ideas	714	(1)
hash function	715	(2)
linear probing	717	(6)
naive analysis of linear probing	719	(1)
what really happens: primary clustering	720	(1)
analysis of the find operation	721	(2)
quadratic probing	723	(13)
java implementation	727	(6)
analysis of quadratic probing	733	(3)
separate chaining hashing	736	(1)
hash tables versus binary search trees	737	(1)
hashing applications	737	(8)
summary	738	(1)
key concepts	738	(1)
common errors	739	(1)
on the internet	740	(1)
exercises	740	(2)
references	742	(3)
a priority queue: the binary heap	745	(36)
basic ideas	746	(6)
structure property	746	(2)
heap-order property	748	(1)
allowed operations	749	(3)
implementation of the basic operations	752	(4)
insertion	752	(2)
the deleteMin operation	754	(2)
the buildHeap operation: linear-time heap construction	756	(5)
advanced operations: decreaseKey and merge	761	(1)
internal sorting: heapsort	761	(3)
external sorting	764	(17)
why we need new algorithms	764	(1)
model for external sorting	765	(1)
the simple algorithm	765	(2)
multiway merge	767	(1)
polyphase merge	768	(2)
replacement selection	770	(1)
summary	771	(1)
key concepts	772	(1)
common errors	772	(1)
on the internet	773	(1)
exercises	773	(4)
references	777	(4)
part five Advanced Data Structures
splay trees	781	(28)
self-adjustment and amortized analysis	782	(3)
amortized time bounds	783	(1)
a simple self-adjusting strategy (that does not work)	783	(2)
the basic bottom-up splay tree	785	(3)
basic splay tree operations	788	(1)
analysis of bottom-up splaying	789	(6)
proof of the splaying bound	792	(3)
top-down splay trees	795	(3)
implementation of top-down splay trees	798	(5)
comparison of the splay tree with other search trees	803	(6)
summary	804	(1)
key concepts	804	(1)
common errors	805	(1)
on the internet	805	(1)
exercises	805	(1)
references	806	(3)
merging priority queues	809	(22)
the skew heap	809	(5)
merging is fundamental	810	(1)
simplistic merging of heap-ordered trees	810	(1)
the skew heap: a simple modification	811	(1)
analysis of the skew heap	812	(2)
the pairing heap	814	(17)
pairing heap operations	815	(1)
implementation of the pairing heap	816	(6)
application: dijkstra's shortest weighted path algorithm	822	(4)
summary	826	(1)
key concepts	826	(1)
common errors	826	(1)
on the internet	827	(1)
exercises	827	(1)
references	828	(3)
the disjoint set class	831	(34)
equivalence relations	832	(1)
dynamic equivalence and applications	832	(10)
application: generating mazes	833	(3)
application: minimum spanning trees	836	(3)
application: the nearest common ancestor problem	839	(3)
the quick-find algorithm	842	(1)
the quick-union algorithm	843	(5)
smart union algorithms	845	(2)
path compression	847	(1)
java implementation	848	(3)
worst case for union-by-rank and path compression	851	(14)
analysis of the union/find algorithm	852	(7)
summary	859	(1)
key concepts	859	(1)
common errors	860	(1)
on the internet	860	(1)
exercises	861	(2)
references	863	(2)
appendix A operators	865	(2)
appendix B graphical user interfaces	867	(30)
the abstract window toolkit and swing	868	(1)
basic objects in swing	869	(9)
Component	870	(1)
Container	871	(1)
top-level containers	871	(1)
JPanel	872	(2)
important i/o components	874	(4)
basic principles	878	(19)
layout managers	879	(4)
graphics	883	(2)
events	885	(2)
event handling: adapters and anonymous inner classes	887	(2)
summary: putting the pieces together	889	(1)
is this everything i need to know about swing?	890	(1)
summary	891	(1)
key concepts	891	(2)
common errors	893	(1)
on the internet	894	(1)
exercises	894	(1)
references	895	(2)
appendix C bitwise operators	897	(4)
index	901