Data Structures and Algorithms in Java, Second Edition

by Drozdek, Adam

• ISBN13: 9780534492526
• ISBN10: 0534492525
• Edition: 2nd
• Format: Hardcover
• Copyright: 2004-09-24
• Publisher: Cengage Learning

Summary

Using the Java programming language, author Adam Drozdek highlights three important aspects of data structures and algorithms. First, the book places special emphasis on the connection between data structures and their algorithms, including an analysis of the algorithms' complexity. Second, the book presents data structures in the context of object-oriented program design, stressing the principle of information hiding in its treatment of encapsulation and decomposition. Finally, the book closely examines data structure implementation. Overall, this practical and theoretical book prepares students with a solid foundation in data structures for future courses and work in design implementation, testing, or maintenance of virtually any software system.

Table of Contents

Object-Oriented Programming Using Java	1	(55)
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	(16)
Encapsulation	8	(8)
Abstract Data Types	16	(2)
Inheritance	18	(3)
Polymorphism	21	(3)
Input and Output	24	(7)
Reading and Writing Bytes	26	(1)
Reading Lines	27	(1)
Reading Tokens: Words and Numbers	28	(1)
Reading and Writing Primitive Data Types	29	(1)
Reading and Writing Objects	29	(1)
Random Access File	30	(1)
Java and Pointers	31	(4)
Vectors in java.util	35	(7)
Data Structures and Object-Oriented Programming	42	(1)
Case Study: Random Access File	42	(9)
Exercises	51	(2)
Programming Assignments	53	(3)
Bibliography	55	(1)
Complexity Analysis	56	(24)
Computational and Asymptotic Complexity	56	(1)
Big-O Notation	57	(2)
Properties of Big-O Notation	59	(2)
Ω and Θ Notations	61	(1)
Possible Problems	62	(1)
Examples of Complexities	62	(2)
Finding Asymptotic Complexity: Examples	64	(2)
The Best, Average, and Worst Cases	66	(3)
Amortized Complexity	69	(4)
NP-Completeness	73	(3)
Exercises	76	(4)
Bibliography	79	(1)
Linked Lists	80	(60)
Singly Linked Lists	80	(15)
Insertion	86	(2)
Deletion	88	(5)
Search	93	(2)
Doubly Linked Lists	95	(4)
Circular Lists	99	(2)
Skip Lists	101	(6)
Self-Organizing Lists	107	(4)
Sparse Tables	111	(3)
Lists in java.util	114	(9)
LinkedList	114	(6)
ArrayList	120	(3)
Concluding Remarks	123	(1)
Case Study: A Library	124	(10)
Exercises	134	(2)
Programming Assignments	136	(4)
Bibliography	139	(1)
Stacks and Queues	140	(29)
Stacks	140	(9)
Stacks in java.util	148	(1)
Queues	149	(8)
Priority Queues	157	(1)
Case Study: Exiting a Maze	158	(6)
Exercises	164	(2)
Programming Assignments	166	(3)
Bibliography	168	(1)
Recursion	169	(45)
Recursive Definitions	169	(3)
Method Calls and Recursion Implementation	172	(2)
Anatomy of a Recursive Call	174	(4)
Tail Recursion	178	(1)
Nontail Recursion	179	(6)
Indirect Recursion	185	(2)
Nested Recursion	187	(1)
Excessive Recursion	188	(3)
Backtracking	191	(7)
Concluding Remarks	198	(1)
Case Study: A Recursive Descent Interpreter	199	(8)
Exercises	207	(3)
Programming Assignments	210	(4)
Bibliography	212	(2)
Binary Trees	214	(85)
Trees, Binary Trees, and Binary Search Trees	214	(5)
Implementing Binary Trees	219	(2)
Searching a Binary Search Tree	221	(2)
Tree Traversal	223	(16)
Breadth-First Traversal	224	(1)
Depth-First Traversal	225	(6)
Stackless Depth-First Traversal	231	(8)
Insertion	239	(3)
Deletion	242	(7)
Deletion by Merging	243	(3)
Deletion by Copying	246	(3)
Balancing a Tree	249	(11)
The DSW Algorithm	252	(3)
AVL Trees	255	(5)
Self-Adjusting Trees	260	(7)
Self-Restructuring Trees	261	(1)
Splaying	262	(5)
Heaps	267	(8)
Heaps as Priority Queues	269	(3)
Organizing Arrays as Heaps	272	(3)
Polish Notation and Expression Trees	275	(5)
Operations on Expression Trees	277	(3)
Case Study: Computing Word Frequencies	280	(9)
Exercises	289	(3)
Programming Assignments	292	(7)
Bibliography	296	(3)
Multiway Trees	299	(77)
The Family of B-Trees	300	(49)
B-Trees	301	(11)
B*-Trees	312	(1)
B+-Trees	313	(3)
Prefix B+-Trees	316	(3)
Bit-Trees	319	(1)
R-Trees	320	(3)
2--4 Trees	323	(15)
Trees in java.util	338	(11)
Tries	349	(9)
Concluding Remarks	358	(1)
Case Study: Spell Checker	358	(11)
Exercises	369	(1)
Programming Assignments	370	(6)
Bibliography	374	(2)
Graphs	376	(93)
Graph Representation	377	(2)
Graph Traversals	379	(4)
Shortest Paths	383	(9)
All-to-All Shortest Path Problem	390	(2)
Cycle Detection	392	(3)
Union-Find Problem	393	(2)
Spanning Trees	395	(4)
Connectivity	399	(6)
Connectivity in Undirected Graphs	399	(3)
Connectivity in Directed Graphs	402	(3)
Topological Sort	405	(2)
Networks	407	(14)
Maximum Flows	407	(10)
Maximum Flows of Minimum Cost	417	(4)
Matching	421	(11)
Stable Matching Problem	426	(2)
Assignment Problem	428	(2)
Matching in Nonbipartite Graphs	430	(2)
Eulerian and Hamiltonian Graphs	432	(10)
Eulerian Graphs	432	(4)
Hamiltonian Graphs	436	(6)
Graph Coloring	442	(3)
NP-Complete Problems in Graph Theory	445	(5)
The Clique Problem	445	(1)
The 3-Colorability Problem	446	(2)
The Vertex Cover Problem	448	(1)
The Hamiltonian Cycle Problem	449	(1)
Case Study: Distinct Representatives	450	(10)
Exercises	460	(4)
Programming Assignments	464	(5)
Bibliography	466	(3)
Sorting	469	(50)
Elementary Sorting Algorithms	470	(7)
Insertion Sort	470	(4)
Selection Sort	474	(1)
Bubble Sort	475	(2)
Decision Trees	477	(4)
Efficient Sorting Algorithms	481	(21)
Shell Sort	481	(3)
Heap Sort	484	(4)
Quicksort	488	(6)
Mergesort	494	(3)
Radix Sort	497	(5)
Sorting in java.util	502	(3)
Concluding Remarks	505	(2)
Case Study: Adding Polynomials	507	(8)
Exercises	515	(1)
Programming Assignments	516	(3)
Bibliography	517	(2)
Hashing	519	(51)
Hash Functions	520	(2)
Division	520	(1)
Folding	520	(1)
Mid-Square Function	521	(1)
Extraction	521	(1)
Radix Transformation	522	(1)
Collision Resolution	522	(9)
Open Addressing	522	(6)
Chaining	528	(2)
Bucket Addressing	530	(1)
Deletion	531	(1)
Perfect Hash Functions	532	(6)
Cichelli's Method	533	(3)
The FHCD Algorithm	536	(2)
Hash Functions for Extendible Files	538	(6)
Extendible Hashing	539	(2)
Linear Hashing	541	(3)
Hashing in java.util	544	(13)
HashMap	544	(3)
HashSet	547	(5)
HashTable	552	(5)
Case Study: Hashing with Buckets	557	(9)
Exercises	566	(1)
Programming Assignments	567	(3)
Bibliography	568	(2)
Data Compression	570	(34)
Conditions for Data Compression	570	(2)
Huffman Coding	572	(14)
Adaptive Huffman Coding	581	(5)
Run-Length Encoding	586	(1)
Ziv-Lempel Code	587	(3)
Case Study: Huffman Method with Run-Length Encoding	590	(11)
Exercises	601	(1)
Programming Assignments	601	(3)
Bibliography	603	(1)
Memory Management	604	(45)
The Sequential-Fit Methods	605	(1)
The Nonsequential-Fit Methods	606	(9)
Buddy Systems	608	(7)
Garbage Collection	615	(18)
Mark-and-Sweep	616	(7)
Copying Methods	623	(2)
Incremental Garbage Collection	625	(8)
Concluding Remarks	633	(1)
Case Study: An In-Place Garbage Collector	634	(9)
Exercises	643	(1)
Programming Assignments	644	(5)
Bibliography	647	(2)
String Matching	649	(88)
Exact String Matching	649	(45)
Straightforward Algorithms	649	(3)
The Knuth-Morris-Pratt Algorithm	652	(8)
The Boyer-Moore Algorithm	660	(10)
Multiple Searches	670	(2)
Bit-Oriented Approach	672	(4)
Matching Sets of Words	676	(6)
Regular Expression Matching	682	(4)
Suffix Tries and Trees	686	(7)
Suffix Arrays	693	(1)
Approximate String Matching	694	(10)
String Similarity	695	(6)
String Matching with k Errors	701	(3)
Case Study: Longest Common Substring	704	(9)
Exercises	713	(2)
Programming Assignments	715	(3)
Bibliography	716	(2)
Appendixes
A Computing Big-O	718	(6)
A.1 Harmonic Series	718	(1)
A.2 Approximation of the Function lg(n!)	718	(2)
A.3 Big-O for Average Case of Quicksort	720	(2)
A.4 Average Path Length in a Random Binary Tree	722	(1)
A.5 The Number of Nodes in an AVL Tree	723	(1)
B NP-Completeness	724	(13)
B.1 Cook's Theorem	724	(13)
Name Index	737	(3)
Subject Index	740