Data Structures and Algorithms in Java

by Drozdek, Adam

• ISBN13: 9780534376680
• ISBN10: 0534376681
• Format: Hardcover
• Copyright: 2000-07-01
• Publisher: Course Technology Ptr

Summary

Building on the widespread use of the Java programming language in industry and education, this book provides a broad-based and case-driven study of data structures -- and the algorithms associated with them -- using Java as the language of implementation. The book places special emphasis on the connection between data structures and their algorithms, including an analysis of the algorithms' complexity. It presents data structures in the context of object-oriented program design, stressing the principle of information hiding in its treatment of encapsulation and decomposition. The book also closely examines data structure implementation and its implications on the selection of programming languages.

Table of Contents

Object-Oriented Programming Using Java	1	(48)
Rudimentary Java	1	(7)
Variable Declarations	1	(3)
Operators	4	(1)
Decision Statements	5	(1)
Loops	6	(1)
Exception Handling	6	(2)
Object-Oriented Programming in Java	8	(13)
Encapsulation	8	(6)
Abstract Data Types	14	(1)
Inheritance	15	(3)
Polymorphism	18	(3)
Input and Output	21	(3)
Java and Pointers	24	(4)
Vectors in java.util	28	(6)
Data Structures and Object-Oriented Programming	34	(1)
Case Study: Random Access File	35	(8)
Exercises	43	(2)
Programming Assignments	45	(4)
Complexity Analysis	49	(22)
Computational and Asymptotic Complexity	49	(1)
Big-O Notation	50	(3)
Properties of Big-O Notation	53	(1)
Ω and Q Notations	54	(1)
Possible Problems	55	(1)
Examples of Complexities	56	(1)
Finding Asymptotic Complexity: Examples	57	(2)
The Best, Average, and Worst Cases	59	(3)
Amortized Complexity	62	(5)
Exercises	67	(4)
Linked Lists	71	(58)
Singly Linked Lists	71	(15)
Insertion	77	(2)
Deletion	79	(5)
Search	84	(2)
Doubly Linked Lists	86	(4)
Circular Lists	90	(2)
Skip Lists	92	(6)
Self-Organizing Lists	98	(4)
Sparse Tables	102	(4)
Linked Lists in java.util	106	(5)
Concluding Remarks	111	(1)
Case Study: A Library	112	(9)
Exercises	121	(2)
Programming Assignments	123	(6)
Stacks and Queues	129	(30)
Stacks	129	(9)
Stacks in java.util	137	(1)
Queues	138	(9)
Priority Queues	147	(1)
Case Study: Exiting a Maze	148	(5)
Exercises	153	(3)
Programming Assignments	156	(3)
Recursion	159	(44)
Recursive Definitions	159	(3)
Method Calls and Recursion Implementation	162	(2)
Anatomy of a Recursive Call	164	(4)
Tail Recursion	168	(1)
Nontail Recursion	169	(5)
Indirect Recursion	174	(2)
Nested Recursion	176	(1)
Excessive Recursion	177	(3)
Backtracking	180	(7)
Concluding Remarks	187	(1)
Case Study: A Recursive Descent Interpreter	188	(8)
Exercises	196	(3)
Programming Assignments	199	(4)
Binary Trees	203	(84)
Trees, Binary Trees, and Binary Search Trees	203	(5)
Implementing Binary Trees	208	(2)
Searching a Binary Search Tree	210	(2)
Tree Traversal	212	(16)
Breadth-First Traversal	213	(1)
Depth-First Traversal	213	(8)
Stackless Depth-First Traversal	221	(7)
Insertion	228	(3)
Deletion	231	(7)
Deletion by Merging	232	(3)
Deletion by Copying	235	(3)
Balancing a Tree	238	(11)
The DSW Algorithm	241	(2)
AVL Trees	243	(6)
Self-Adjusting Trees	249	(7)
Self-Restructuring Trees	250	(1)
Splaying	251	(5)
Heaps	256	(9)
Heaps as Priority Queues	258	(3)
Organizing Arrays as Heaps	261	(4)
Polish Notation and Expression Trees	265	(5)
Operations on Expression Trees	266	(4)
Case Study: Computing Word Frequencies	270	(6)
Exercises	276	(4)
Programming Assignments	280	(7)
Multiway Trees	287	(68)
The Family of B-Trees	288	(40)
B-Trees	289	(11)
B*-Trees	300	(1)
B+-Trees	301	(3)
Prefix B+-Trees	304	(1)
Bit-Trees	305	(3)
R-Trees	308	(3)
2--4 Trees	311	(8)
Sets in java.util	319	(6)
Maps in java.util	325	(3)
Tries	328	(9)
Concluding Remarks	337	(1)
Case Study: Spell Checker	337	(11)
Exercises	348	(1)
Programming Assignments	349	(6)
Graphs	355	(78)
Graph Representation	357	(1)
Graph Traversals	357	(5)
Shortest Paths	362	(10)
All-to-All Shortest Path Problem	369	(3)
Cycle Detection	372	(3)
Union-Find Problem	372	(3)
Spanning Trees	375	(5)
Boruvka's Algorithm	376	(1)
Kruskal's Algorithm	377	(1)
Jarnik-Prim's Algorithm	377	(3)
Dijkstra's Method	380	(1)
Connectivity	380	(6)
Connectivity in Undirected Graphs	381	(3)
Connectivity in Directed Graphs	384	(2)
Topological Sort	386	(2)
Networks	388	(13)
Maximum Flows	388	(10)
Maximum Flows of Minimum Cost	398	(3)
Matching	401	(11)
Assignment Problem	408	(2)
Matching in Nonbipartite Graphs	410	(2)
Eulerian and Hamiltonian Graphs	412	(4)
Eulerian Graphs	412	(1)
Hamiltonian Graphs	413	(3)
Case Study: Distinct Representatives	416	(9)
Exercises	425	(3)
Programming Assignments	428	(5)
Sorting	433	(50)
Elementary Sorting Algorithms	434	(7)
Insertion Sort	434	(4)
Selection Sort	438	(1)
Bubble Sort	439	(2)
Decision Trees	441	(4)
Efficient Sorting Algorithms	445	(21)
Shell Sort	445	(3)
Heap Sort	448	(4)
Quicksort	452	(6)
Mergesort	458	(3)
Radix Sort	461	(5)
Sorting in java.util	466	(3)
Concluding Remarks	469	(2)
Case Study: Adding Polynomials	471	(7)
Exercises	478	(2)
Programming Assignments	480	(3)
Hashing	483	(44)
Hash Functions	484	(2)
Division	484	(1)
Folding	484	(1)
Mid-Square Function	485	(1)
Extraction	485	(1)
Radix Transformation	486	(1)
Collision Resolution	486	(10)
Open Addressing	487	(5)
Chaining	492	(3)
Bucket Addressing	495	(1)
Deletion	496	(1)
Perfect Hash Functions	497	(6)
Cichelli's Method	498	(2)
The FHCD Algorithm	500	(3)
Hash Functions for Extendible Files	503	(6)
Extendible Hashing	503	(3)
Linear Hashing	506	(3)
Hashing in java.util	509	(5)
Case Study: Hashing with Buckets	514	(8)
Exercises	522	(1)
Programming Assignments	523	(4)
Data Compression	527	(38)
Conditions for Data Compression	527	(2)
Huffman Coding	529	(14)
Adaptive Huffman Coding	539	(4)
Shannon-Fano Code	543	(2)
Run-Length Encoding	545	(1)
Ziv-Lempel Code	546	(3)
Case Study: Huffman Method with Run-Length Encoding	549	(11)
Exercises	560	(1)
Programming Assignments	561	(4)
Memory Management	565	(50)
The Sequential-Fit Methods	566	(1)
The Nonsequential-Fit Methods	567	(9)
Buddy Systems	569	(7)
Garbage Collection	576	(18)
Mark-and-Sweep	577	(7)
Copying Methods	584	(2)
Incremental Garbage Collection	586	(8)
Concluding Remarks	594	(1)
Case Study: An In-Place Garbage Collector	595	(8)
Exercises	603	(1)
Programming Assignments	604	(5)
Appendix
A Computing Big-O	609	(6)
A.1 Harmonic Series	609	(1)
A.2 Approximation of the Function lg (n!)	609	(2)
A.3 Big-O for Average Case of Quicksort	611	(2)
A.4 Average Path Length in a Random Binary Tree	613	(2)
Name Index	615	(4)
Subject Index	619