Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Javais an ;advanced algorithms ; book that fits between traditional CS2 and Algorithms Analysis courses. In the old ACM Curriculum Guidelines, this course was known as CS7. This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math.   As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs in Java.   Weiss clearly explains topics from binary heaps to sorting to NP-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weiss' careful, rigorous and in-depth analysis of each type of algorithm. A logical organization of topics and full access to source code complement the text's coverage.  

Mark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelor’s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.

Professor Weiss is the author of numerous publications in top-rated journals and was recipient of the University’s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually.

In addition to his Research Award in 1994, Professor Weiss is also the recipient of the University’s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007).

Chapter 1 Introduction 1
1.1 What’s the Book About? 1
1.2 Mathematics Review 2
1.2.1 Exponents 3
1.2.2 Logarithms 3
1.2.3 Series 4
1.2.4 Modular Arithmetic 5
1.2.5 The P Word 6
1.3 A Brief Introduction to Recursion 8
1.4 Implementing Generic Components Pre-Java 5 12
1.4.1 Using Object for Genericity 13
1.4.2 Wrappers for Primitive Types 14
1.4.3 Using Interface Types for Genericity 14
1.4.4 Compatibility of Array Types 16
1.5 Implementing Generic Components Using Java 5 Generics 16
1.5.1 Simple Generic Classes and Interfaces 17
1.5.2 Autoboxing/Unboxing 18
1.5.3 The Diamond Operator 18
1.5.4 Wildcards with Bounds 19
1.5.5 Generic Static Methods 20
1.5.6 Type Bounds 21
1.5.7 Type Erasure 22
1.5.8 Restrictions on Generics 23
1.6 Function Objects 24
Summary 26
Exercises 26
References 28

Chapter 2 Algorithm Analysis 29
2.1 Mathematical Background 29
2.2 Model 32
2.3 What to Analyze 33
2.4 Running Time Calculations 35
2.4.1 A Simple Example 36
2.4.2 General Rules 36
2.4.3 Solutions for the Maximum Subsequence Sum Problem 39
2.4.4 Logarithms in the Running Time 45
2.4.5 A Grain of Salt 49
Summary 49
Exercises 50
References 55

Chapter 3 Lists, Stacks, and Queues 57
3.1 Abstract Data Types (ADTs) 57
3.2 The List ADT 58
3.2.1 Simple Array Implementation of Lists 58
3.2.2 Simple Linked Lists 59
3.3 Lists in the Java Collections API 61
3.3.1 Collection Interface 61
3.3.2 Iterators 61
3.3.3 The List Interface, ArrayList, and LinkedList 63
3.3.4 Example: Using remove on a LinkedList 65
3.3.5 ListIterators 67
3.4 Implementation of ArrayList 67
3.4.1 The Basic Class 68
3.4.2 The Iterator and Java Nested and Inner Classes 71
3.5 Implementation of LinkedList 75
3.6 The Stack ADT 82
3.6.1 Stack Model 82
3.6.2 Implementation of Stacks 83
3.6.3 Applications 84
3.7 The Queue ADT 92
3.7.1 Queue Model 92
3.7.2 Array Implementation of Queues 92
3.7.3 Applications of Queues 95
Summary 96
Exercises 96

Chapter 4 Trees 101
4.1 Preliminaries 101
4.1.1 Implementation of Trees 102
4.1.2 Tree Traversals with an Application 103
4.2 Binary Trees 107
4.2.1 Implementation 108
4.2.2 An Example: Expression Trees 109
4.3 The Search Tree ADT–Binary Search Trees 112
4.3.1 contains 113
4.3.2 findMin and findMax 115
4.3.3 insert 116
4.3.4 remove 118
4.3.5 Average-Case Analysis 120
4.4 AVL Trees 123
4.4.1 Single Rotation 125
4.4.2 Double Rotation 128
4.5 Splay Trees 137
4.5.1 A Simple Idea (That Does Not Work) 137
4.5.2 Splaying 139
4.6 Tree Traversals (Revisited) 145
4.7 B-Trees 147
4.8 Sets and Maps in the Standard Library 152
4.8.1 Sets 152
4.8.2 Maps 153
4.8.3 Implementation of TreeSet and TreeMap 153
4.8.4 An Example That Uses Several Maps 154
Summary 160
Exercises 160
References 167

Chapter 5 Hashing 171
5.1 General Idea 171
5.2 Hash Function 172
5.3 Separate Chaining 174
5.4 Hash Tables Without Linked Lists 179
5.4.1 Linear Probing 179
5.4.2 Quadratic Probing 181
5.4.3 Double Hashing 183
5.5 Rehashing 188
5.6 Hash Tables in the Standard Library 189
5.7 Hash Tables with Worst-Case O(1) Access 192
5.7.1 Perfect Hashing 193
5.7.2 Cuckoo Hashing 195
5.7.3 Hopscotch Hashing 205
5.8 Universal Hashing 211
5.9 Extendible Hashing 214
Summary 217
Exercises 218
References 222

Chapter 6 Priority Queues (Heaps) 225
6.1 Model 225
6.2 Simple Implementations 226
6.3 Binary Heap 226
6.3.1 Structure Property 227
6.3.2 Heap-Order Property 229
6.3.3 Basic Heap Operations 229
6.3.4 Other Heap Operations 234
6.4 Applications of Priority Queues 238
6.4.1 The Selection Problem 238
6.4.2 Event Simulation 239
6.5 d-Heaps 240
6.6 Leftist Heaps 241
6.6.1 Leftist Heap Property 241
6.6.2 Leftist Heap Operations 242
6.7 Skew Heaps 249
6.8 Binomial Queues 252
6.8.1 Binomial Queue Structure 252
6.8.2 Binomial Queue Operations 253
6.8.3 Implementation of Binomial Queues 256
6.9 Priority Queues in the Standard Library 261
Summary 261
Exercises 263
References 267

Chapter 7 Sorting 271
7.1 Preliminaries 271
7.2 Insertion Sort 272
7.2.1 The Algorithm 272
7.2.2 Analysis of Insertion Sort 272
7.3 A Lower Bound for Simple Sorting Algorithms 273
7.4 Shellsort 274
7.4.1 Worst-Case Analysis of Shellsort 276
7.5 Heapsort 278
7.5.1 Analysis of Heapsort 279
7.6 Mergesort 282
7.6.1 Analysis of Mergesort 284
7.7 Quicksort 288
7.7.1 Picking the Pivot 290
7.7.2 Partitioning Strategy 292
7.7.3 Small Arrays 294
7.7.4 Actual Quicksort Routines 294
7.7.5 Analysis of Quicksort 297
7.7.6 A Linear-Expected-Time Algorithm for Selection 300
7.8 A General Lower Bound for Sorting 302
7.8.1 Decision Trees 302
7.9 Decision-Tree Lower Bounds for Selection Problems 304
7.10 Adversary Lower Bounds 307
7.11 Linear-Time Sorts: Bucket Sort and Radix Sort 310
7.12 External Sorting 315
7.12.1 Why We Need New Algorithms 316
7.12.2 Model for External Sorting 316
7.12.3 The Simple Algorithm 316
7.12.4 Multiway Merge 317
7.12.5 Polyphase Merge 318
7.12.6 Replacement Selection 319
Summary 321
Exercises 321
References 327

Chapter 8 The Disjoint Set Class 331
8.1 Equivalence Relations 331
8.2 The Dynamic Equivalence Problem 332
8.3 Basic Data Structure 333
8.4 Smart Union Algorithms 337
8.5 Path Compression 340
8.6 Worst Case for Union-by-Rank and Path Compression 341
8.6.1 Slowly Growing Functions 342
8.6.2 An Analysis By Recursive Decomposition 343
8.6.3 An O(M log * N) Bound 350
8.6.4 An O( M α (M, N) ) Bound 350
8.7 An Application 352
Summary 355
Exercises 355
References 357

Chapter 9 Graph Algorithms 359
9.1 Definitions 359
9.1.1 Representation of Graphs 360
9.2 Topological Sort 362
9.3 Shortest-Path Algorithms 366
9.3.1 Unweighted Shortest Paths 367
9.3.2 Dijkstra’s Algorithm 372
9.3.3 Graphs with Negative Edge Costs 380
9.3.4 Acyclic Graphs 380
9.3.5 All-Pairs Shortest Path 384
9.3.6 Shortest-Path Example 384
9.4 Network Flow Problems 386
9.4.1 A Simple Maximum-Flow Algorithm 388
9.5 Minimum Spanning Tree 393
9.5.1 Prim’s Algorithm 394
9.5.2 Kruskal’s Algorithm 397
9.6 Applications of Depth-First Search 399
9.6.1 Undirected Graphs 400
9.6.2 Biconnectivity 402
9.6.3 Euler Circuits 405
9.6.4 Directed Graphs 409
9.6.5 Finding Strong Components 411
9.7 Introduction to NP-Completeness 412
9.7.1 Easy vs. Hard 413
9.7.2 The Class NP 414
9.7.3 NP-Complete Problems 415
Summary 417
Exercises 417
References 425

Chapter 10 Algorithm Design
Techniques 429
10.1 Greedy Algorithms 429
10.1.1 A Simple Scheduling Problem 430
10.1.2 Huffman Codes 433
10.1.3 Approximate Bin Packing 439
10.2 Divide and Conquer 448
10.2.1 Running Time of Divide-and-Conquer Algorithms 449
10.2.2 Closest-Points Problem 451
10.2.3 The Selection Problem 455
10.2.4 Theoretical Improvements for Arithmetic Problems 458
10.3 Dynamic Programming 462
10.3.1 Using a Table Instead of Recursion 463
10.3.2 Ordering Matrix Multiplications 466
10.3.3 Optimal Binary Search Tree 469
10.3.4 All-Pairs Shortest Path 472
10.4 Randomized Algorithms 474
10.4.1 Random Number Generators 476
10.4.2 Skip Lists 480
10.4.3 Primality Testing 483
10.5 Backtracking Algorithms 486
10.5.1 The Turnpike Reconstruction Problem 487
10.5.2 Games 490
Summary 499
Exercises 499
References 508

Chapter 11 Amortized Analysis 513
11.1 An Unrelated Puzzle 514
11.2 Binomial Queues 514
11.3 Skew Heaps 519
11.4 Fibonacci Heaps 522
11.4.1 Cutting Nodes in Leftist Heaps 522
11.4.2 Lazy Merging for Binomial Queues 525
11.4.3 The Fibonacci Heap Operations 528
11.4.4 Proof of the Time Bound 529
11.5 Splay Trees 531
Summary 536
Exercises 536
References 538

Chapter 12 Advanced Data Structures
and Implementation 541
12.1 Top-Down Splay Trees 541
12.2 Red-Black Trees 549
12.2.1 Bottom-Up Insertion 549
12.2.2 Top-Down Red-Black Trees 551
12.2.3 Top-Down Deletion 556
12.3 Treaps 558
12.4 Suffix Arrays and Suffix Trees 560
12.4.1 Suffix Arrays 561
12.4.2 Suffix Trees 564
12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees 567
12.5 k-d Trees 578
12.6 Pairing Heaps 583
Summary 588
Exercises 590
References 594
Index 599