Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Java is 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.

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).

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