Data Structures and Algorithm Analysis in Java, Third Edition (Dover Books on Computer Science)

With its focus on creating efficient data structures and algorithms, this comprehensive text helps readers understand how to select or design the tools that will best solve specific problems. It uses Java as the programming language and is suitable for second-year data structure courses and computer science courses in algorithm analysis. Techniques for representing data are presented within the context of assessing costs and benefits, promoting an understanding of the principles of algorithm analysis and the effects of a chosen physical medium. The text also explores tradeoff issues, familiarizes readers with the most commonly used data structures and their algorithms, and discusses matching appropriate data structures to applications. The author offers explicit coverage of design patterns encountered in the course of programming the book's basic data structures and algorithms. Numerous examples appear throughout the text. Preface I Preliminaries 1 Data Structures and Algorithms 1.1 A Philosophy of Data Structures 1.1.1 The Need for Data Structures 1.1.2 Costs and Benefits 1.2 Abstract Data Types and Data Structures 1.3 Design Patterns 1.3.1 Flyweight 1.3.2 Visitor 1.3.3 Composite 1.3.4 Strategy 1.4 Problems, Algorithms, and Programs 1.5 Further Reading 1.6 Exercises 2 Mathematical Preliminaries 2.1 Sets and Relations 2.2 Miscellaneous Notation 2.3 Logarithms 2.4 Summations and Recurrences 2.5 Recursion 2.6 Mathematical Proof Techniques 2.6.1 Direct Proof 2.6.2 Proof by Contradiction 2.6.3 Proof by Mathematical Induction 2.7 Estimation 2.8 Further Reading 2.9 Exercises 3 Algorithm Analysis 3.1 Introduction 3.2 Best, Worst, and Average Cases 3.3 A Faster Computer, or a Faster Algorithm? 3.4 Asymptotic Analysis 3.4.1 Upper Bounds 3.4.2 Lower Bounds 3.4.3 Notation 3.4.4 Simplifying Rules 3.4.5 Classifying Functions 3.5 Calculating the Running Time for a Program 3.6 Analyzing Problems 3.7 Common Misunderstandings 3.8 Multiple Parameters 3.9 Space Bounds 3.10 Speeding Up Your Programs 3.11 Empirical Analysis 3.12 Further Reading 3.13 Exercises 3.14 Projects II Fundamental Data Structures 4 Lists, Stacks, and Queues 4.1 Lists 4.1.1 Array-Based List Implementation 4.1.2 Linked Lists 4.1.3 Comparison of List Implementations 4.1.4 Element Implementations 4.1.5 Doubly Linked Lists 4.2 Stacks 4.2.1 Array-Based Stacks 4.2.2 Linked Stacks 4.2.3 Comparison of Array-Based and Linked Stacks 4.2.4 Implementing Recursion 4.3 Queues 4.3.1 Array-Based Queues 4.3.2 Linked Queues 4.3.3 Comparison of Array-Based and Linked Queues 4.4 Dictionaries 4.5 Further Reading 4.6 Exercises 4.7 Projects 5 Binary Trees 5.1 Definitions and Properties 5.1.1 The Full Binary Tree Theorem 5.1.2 A Binary Tree Node ADT 5.2 Binary Tree Traversals 5.3 Binary Tree Node Implementations 5.3.1 Pointer-Based Node Implementations 5.3.2 Space Requirements 5.3.3 Array Implementation for Complete Binary Trees 5.4 Binary Search Trees 5.5 Heaps and Priority Queues 5.6 Huffman Coding Trees 5.6.1 Building Huffman Coding Trees 5.6.2 Assigning and Using Huffman Codes 5.6.3 Search in Huffman Trees 5.7 Further Reading 5.8 Exercises 5.9 Projects 6 Non-Binary Trees 6.1 General Tree Definitions and Terminology 6.1.1 An ADT for General Tree Nodes 6.1.2 General Tree Traversals 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.3.1 List of Children 6.3.2 The Left-Child/Right-Sibling Implementation 6.3.3 Dynamic Node Implementations 6.3.4 Dynamic ``Left-Child/Right-Sibling'' Implementation 6.4 K-ary Trees 6.5 Sequential Tree Implementations 6.6 Further Reading 6.7 Exercises 6.8 Projects III Sorting and Searching 7 Internal Sorting 7.1 Sorting Terminology and Notation 7.2 Three (n2) Sorting Algorithms 7.2.1 Insertion Sort 7.2.2 Bubble Sort 7.2.3 Selection Sort 7.2.4 The Cost of Exchange Sorting 7.3 Shellsort 7.4 Mergesort 7.5 Quicksort 7.6 Heapsort 7.7 Binsort and Radix Sort 7.8 An Empirical Comparison of Sorting Algorithms 7.9 Lower Bounds for Sorting 7.10 Further Reading 7.11 Exercises 7.12 Projects 8 File Processing and External Sorting 8.1 Primary versus Secondary Storage 8.2 Disk Drives 8.2.1 Disk Drive Architecture 8.2.2 Disk Access Costs 8.3 Buffers and Buffer Pools 8.4 The Programmer's View of Files 8.5 External Sorting 8.5.1 Simple Approaches to External Sorting 8.5.2 Replacement Selection 8.5.3 Multiway Merging 8.6 Further Reading 8.7 Exercises 8.8 Projects 9 Searching 9.1 Searching Unsorted and Sorted Arrays 9.2 Self-Organizing Lists 9.3 Bit Vectors for Representing Sets 9.4 Hashing 9.4.1 Hash Functions 9.4.2 Open Hashing 9.4.3 Closed Hashing 9.4.4 Analysis of Closed Hashing 9.4.5 Deletion 9.5 Further Reading 9.6 Exercises 9.7 Projects 10 Indexing 10.1 Linear Indexing 10.2 ISAM 10.3 Tree-based Indexing 10.4 2-3 Trees 10.5 B-Trees 10.5.1 B+-Trees 10.5.2 B-Tree Analysis 10.6 Further Reading 10.7 Exercises 10.8 Projects IV Advanced Data Structures 11 Graphs 11.1 Terminology and Representations 11.2 Graph Implementations 11.3 Graph Traversals 11.3.1 Depth-First Search 11.3.2 Breadth-First Search 11.3.3 Topological Sort 11.4 Shortest-Paths Problems 11.4.1 Single-Source Shortest Paths 11.5 Minimum-Cost Spanning Trees 11.5.1 Prim's Algorithm 11.5.2 Kruskal's Algorithm 11.6 Further Reading 11.7 Exercises 11.8 Projects 12 Lists and Arrays Revisited 12.1 Multilists 12.2 Matrix Representations 12.3 Memory Management 12.3.1 Dynamic Storage Allocation 12.3.2 Failure Policies and Garbage Collection 12.4 Further Reading 12.5 Exercises 12.6 Projects 13 Advanced Tree Structures 13.1 Tries 13.2 Balanced Trees 13.2.1 The AVL Tree 13.2.2 The Splay Tree 13.3 Spatial Data Structures 13.3.1 The K-D Tree 13.3.2 The PR quadtree 13.3.3 Other Point Data Structures 13.3.4 Other Spatial Data Structures 13.4 Further Reading 13.5 Exercises 13.6 Projects V Theory of Algorithms 14 Analysis Techniques 14.1 Summation Techniques 14.2 Recurrence Relations 14.2.1 Estimating Upper and Lower Bounds 14.2.2 Expanding Recurrences 14.2.3 Divide and Conquer Recurrences 14.2.4 Average-Case Analysis of Quicksort 14.3 Amortized Analysis 14.4 Further Reading 14.5 Exercises 14.6 Projects 15 Lower Bounds 15.1 Introduction to Lower Bounds Proofs 15.2 Lower Bounds on Searching Lists 15.2.1 Searching in Unsorted Lists 15.2.2 Searching in Sorted Lists 15.3 Finding the Maximum Value 15.4 Adversarial Lower Bounds Proofs 15.5 State Space Lower Bounds Proofs 15.6 Finding the ith Best Element 15.7 Optimal Sorting 15.8 Further Reading 15.9 Exercises 15.10 Projects 16 Patterns of Algorithms 16.1 Dynamic Programming 16.1.1 The Knapsack Problem 16.1.2 All-Pairs Shortest Paths 16.2 Randomized Algorithms 16.2.1 Randomized algorithms for finding large values 16.2.2 Skip Lists 16.3 Numerical Algorithms 16.3.1 Exponentiation 16.3.2 Largest Common Factor 16.3.3 Matrix Multiplication 16.3.4 Random Numbers 16.3.5 The Fast Fourier Transform 16.4 Further Reading 16.5 Exercises 16.6 Projects 17 Limits to Computation 17.1 Reductions 17.2 Hard Problems 17.2.1 The Theory of NP-Completeness 17.2.2 NP-Completeness Proofs 17.2.3 Coping with NP-Complete Problems 17.3 Impossible Problems 17.3.1 Uncountability 17.3.2 The Halting Problem Is Unsolvable 17.4 Further Reading 17.5 Exercises 17.6 Projects Bibliography Index "A comprehensive treatment that focuses on how to create efficient data structures and algorithms, this text helps readers understand how to select or design the data structure that will best solve a specific problem. Utilizing Java as the programming language, this edition is suitable for second-year data structure courses and computer science courses in algorithmic analysis"-- Provided by publisher " A comprehensive treatment that focuses on how to create efficient data structures and algorithms, this text helps readers understand how to select or design the data structure that will best solve a specific problem. Utilizing Java as the programming language, this edition is suitable for second-year data structure courses and computer science courses in algorithmic analysis"--