Practical Introduction to Data Structures and Algorithms : Java Edition

by Shaffer, Clifford A.

• ISBN13: 9780136609117
• ISBN10: 0136609112
• Format: Paperback
• Copyright: 1998-01-01
• Publisher: Prentice Hall
• More Book Details
• Purchase Benefits

Summary

The author, Cliff Shaffer provides a superior learning tool for those who desire more rigorous data structures and an algorithm analysis book utilizing Java. While the author covers most of the standard data structures, he concentrates on teaching the principles required to select or design a data structure that will best solve a problem. The emphasis is on data structures, and algorithm analysis, not teaching Java. Java is utilized strictly as a tool to illustrate data structures concepts and only the minimal, useful subset of Java is included.

Table of Contents

Table of Contents	iii	(8)
Preface	xi
I Preliminaries	1	(74)
1 Data Structures and Algorithms	3	(16)
1.1 A Philosophy of Data Structures	3	(4)
1.1.1 The Need for Data Structures	3	(2)
1.1.2 Costs and Benefits	5	(1)
1.1.3 Goals of This Book	6	(1)
1.2 Abstract Data Types and Data Structures	7	(3)
1.3 Problems, Algorithms, and Programs	10	(3)
1.4 Algorithm Efficiency	13	(1)
1.5 Further Reading	14	(1)
1.6 Exercises	15	(4)
2 Mathematical Preliminaries	19	(22)
2.1 Sets	19	(2)
2.2 Miscellaneous Notation	21	(2)
2.3 Logarithms	23	(1)
2.4 Recursion	24	(3)
2.5 Summations and Recurrences	27	(2)
2.6 Mathematical Proof Techniques	29	(5)
2.6.1 Proof by Contradiction	29	(1)
2.6.2 Proof by Mathematical Induction	30	(4)
2.7 Estimating	34	(2)
2.8 Further Reading	36	(1)
2.9 Exercises	37	(4)
3 Algorithm Analysis	41	(34)
3.1 Introduction	41	(6)
3.2 Best, Worst, and Average Cases	47	(1)
3.3 A Faster Computer, or a Faster Algorithm?	48	(3)
3.4 Asymptotic Analysis	51	(6)
3.4.1 Upper Bounds	52	(2)
3.4.2 Lower Bounds	54	(1)
3.4.3 XXX Notation	55	(1)
3.4.4 Simplifying Rules	56	(1)
3.5 Calculating the Running Time of a Program	57	(5)
3.6 Analyzing Problems	62	(1)
3.7 Multiple Parameters	63	(1)
3.8 Space Bounds	64	(4)
3.9 Some Practical Considerations	68	(2)
3.10 Further Reading	70	(1)
3.11 Exercises	70	(4)
3.12 Projects	74	(1)
II Fundamental Data Structures	75	(148)
4 Lists, Stacks, and Queues	77	(44)
4.1 Lists	77	(25)
4.1.1 Array-Based List Implementation	81	(1)
4.1.2 Linked Lists	82	(11)
4.1.3 Comparison of List Implementations	93	(3)
4.1.4 Element Implementations	96	(1)
4.1.5 Doubly Linked Lists	97	(5)
4.1.6 Circular Linked Lists	102	(1)
4.2 Stacks	102	(8)
4.2.1 Array-Based Stacks	103	(2)
4.2.2 Linked Stacks	105	(1)
4.2.3 Comparison of Array-Based and Linked Stacks	106	(1)
4.2.4 Implementing Recursion	107	(3)
4.3 Queues	110	(5)
4.3.1 Array-Based Queues	110	(5)
4.3.2 Linked Queues	115	(1)
4.3.3 Comparison of Array-Based and Linked Queues	115	(1)
4.4 Exercises	115	(4)
4.5 Projects	119	(2)
5 Binary Trees	121	(46)
5.1 Definitions and Properties	121	(5)
5.1.1 The Full Binary Tree Theorem	124	(2)
5.1.2 A Binary Tree Node ADT	126	(1)
5.2 Binary Tree Traversals	126	(2)
5.3 Binary Tree Implementations	128	(7)
5.3.1 Pointer-Based Node Implementations	128	(3)
5.3.2 Space Requirements	131	(3)
5.3.3 Array Implementation for Complete Binary Trees	134	(1)
5.4 Huffman Coding Trees	135	(11)
5.4.1 Building Huffman Coding Trees	137	(5)
5.4.2 Assigning and Using Huffman Codes	142	(4)
5.5 Binary Search Trees	146	(8)
5.6 Heaps and Priority Queues	154	(7)
5.7 Further Reading	161	(1)
5.8 Exercises	161	(3)
5.9 Projects	164	(3)
6 General Trees	167	(22)
6.1 General Tree Definitions and Terminology	167	(3)
6.1.1 An ADT for General Tree Nodes	168	(1)
6.1.2 General Tree Traversals	168	(2)
6.2 The Parent Pointer Implementation	170	(6)
6.3 General Tree Implementations	176	(5)
6.3.1 List of Children	176	(2)
6.3.2 The Left Child/Right Sibling Implementation	178	(1)
6.3.3 Dynamic Node Implementations	178	(2)
6.3.4 Dynamic "Left Child/Right Sibling" Implementation	180	(1)
6.4 K-ary Trees	181	(1)
6.5 Sequential Tree Implementations	182	(3)
6.6 Further Reading	185	(1)
6.7 Exercises	185	(3)
6.8 Projects	188	(1)
7 Graphs	189	(34)
7.1 Terminology and Representations	190	(4)
7.2 Graph Implementations	194	(4)
7.3 Graph Traversals	198	(9)
7.3.1 Depth-First Search	202	(1)
7.3.2 Breadth-First Search	202	(1)
7.3.3 Topological Sort	203	(4)
7.4 Shortest-Paths Problems	207	(7)
7.4.1 Single-Source Shortest Paths	209	(2)
7.4.2 All-Pairs Shortest Paths	211	(3)
7.5 Minimum-Cost Spanning Trees	214	(5)
7.5.1 Prim's Algorithm	214	(3)
7.5.2 Kruskal's Algorithm	217	(2)
7.6 Further Reading	219	(1)
7.7 Exercises	219	(3)
7.8 Projects	222	(1)
III Sorting and Searching	223	(140)
8 Internal Sorting	225	(42)
8.1 Sorting Terminology and Notation	225	(2)
8.2 Three XXX(n(2)) Sorting Algorithms	227	(6)
8.2.1 Insertion Sort	227	(2)
8.2.2 Bubble Sort	229	(2)
8.2.3 Selection Sort	231	(1)
8.2.4 The Cost of Exchange Sorting	232	(1)
8.3 Shellsort	233	(3)
8.4 Quicksort	236	(6)
8.5 Mergesort	242	(4)
8.6 Heapsort	246	(3)
8.7 Binsort and Radix Sort	249	(6)
8.8 An Empirical Comparison of Sorting Algorithms	255	(2)
8.9 Lower Bounds for Sorting	257	(5)
8.10 Further Reading	262	(1)
8.11 Exercises	262	(4)
8.12 Projects	266	(1)
9 File Processing and External Sorting	267	(34)
9.1 Primary Versus Secondary Storage	267	(3)
9.2 Disk and Tape Drives	270	(9)
9.2.1 Disk Access Costs	276	(2)
9.2.2 Magnetic Tape	278	(1)
9.3 Buffers and Buffer Pools	279	(3)
9.4 The Programmer's View of Files	282	(1)
9.5 External Sorting	283	(3)
9.6 Simple Approaches to External Sorting	286	(3)
9.7 Replacement Selection	289	(4)
9.8 Multiway Merging	293	(3)
9.9 Further Reading	296	(1)
9.10 Exercises	296	(3)
9.11 Projects	299	(2)
10 Searching	301	(32)
10.1 Searching Sorted Arrays	302	(1)
10.2 Self-Organizing Lists	303	(6)
10.3 Searching in Sets	309	(1)
10.4 Hashing	310	(18)
10.4.1 Hash Functions	311	(4)
10.4.2 Open Hashing	315	(1)
10.4.3 Closed Hashing	316	(12)
10.5 Further Reading	328	(1)
10.6 Exercises	329	(2)
10.7 Projects	331	(2)
11 Indexing	333	(30)
11.1 Linear Indexing	335	(3)
11.2 ISAM	338	(2)
11.3 Tree Indexing	340	(2)
11.4 2-3 Trees	342	(7)
11.5 B-Trees	349	(9)
11.5.1 B(+)-Trees	351	(5)
11.5.2 B-Tree Analysis	356	(2)
11.6 Further Reading	358	(1)
11.7 Exercises	359	(2)
11.8 Projects	361	(2)
IV Applications and Advanced Topics	363	(98)
12 Lists and Arrays Revisited	365	(32)
12.1 Skip Lists	365	(6)
12.2 Multilists	371	(4)
12.3 Matrix Representations	375	(3)
12.4 Memory Management	378	(15)
12.4.1 Dynamic Storage Allocation	379	(9)
12.4.2 Failure Policies and Garbage Collection	388	(5)
12.5 Further Reading	393	(1)
12.6 Exercises	393	(2)
12.7 Projects	395	(2)
13 Advanced Tree Structures	397	(24)
13.1 Tries	397	(5)
13.2 Splay Trees	402	(4)
13.3 Spatial Data Structures	406	(10)
13.3.1 The K-D Tree	408	(5)
13.3.2 The PR quadtree	413	(2)
13.3.3 Other Spatial Data Structures	415	(1)
13.4 Further Reading	416	(1)
13.5 Exercises	417	(1)
13.6 Projects	418	(3)
14 Analysis Techniques	421	(18)
14.1 Summation Techniques	422	(3)
14.2 Recurrence Relations	425	(6)
14.2.1 Estimating Upper and Lower Bounds	425	(1)
14.2.2 Expanding Recurrences	426	(1)
14.2.3 Divide and Conquer Recurrences	427	(2)
14.2.4 Average-Case Analysis of Quicksort	429	(2)
14.3 Amortized Analysis	431	(3)
14.4 Further Reading	434	(1)
14.5 Exercises	434	(4)
14.6 Projects	438	(1)
15 Limits to Computation	439	(22)
15.1 Introduction	439	(1)
15.2 Reductions	440	(5)
15.3 Hard Problems	445	(6)
15.3.1 NP-Completeness	446	(4)
15.3.2 Getting Around NP-Complete Problems	450	(1)
15.4 Impossible Problems	451	(7)
15.4.1 Uncountability	452	(3)
15.4.2 The Halting Problem is Unsolvable	455	(2)
15.4.3 Determining Program Behavior is Unsolvable	457	(1)
15.5 Further Reading	458	(1)
15.6 Exercises	458	(2)
15.7 Projects	460	(1)
V Appendix	461	(2)
A Java Tutorial for C and Pascal Programmers	463	(10)
A.1 Example 1: Interface for Lists	465	(1)
A.2 Example 2: Array-Based List Implementation	466	(4)
A.3 Example 3: Linked List Implementation	470	(3)
Bibliography	473	(6)
Index	479