Data structures and algorithms in Java

Cover Page......Page 1
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Contents......Page 7
1.1.1 Variable Declarations......Page 19
1.1.2 Operators......Page 22
1.1.3 Decision Statements......Page 23
1.1.5 Exception Handling......Page 24
1.2.1 Encapsulation......Page 26
1.2.2 Abstract Data Types......Page 34
1.2.3 Inheritance......Page 36
1.2.4 Polymorphism......Page 39
1.3 Input and Output......Page 42
1.3.1 Reading and Writing Bytes......Page 44
1.3.2 Reading Lines......Page 45
1.3.3 Reading Tokens: Words and Numbers......Page 46
1.3.5 Reading and Writing Objects......Page 47
1.3.6 Random Access File......Page 48
1.4 Java and Pointers......Page 49
1.5 Vectors in java.util......Page 53
1.7 Case Study: Random Access File......Page 60
1.8 Exercises......Page 69
1.9 Programming Assignments......Page 71
Bibliography......Page 73
2.1 Computational and Asymptotic Complexity......Page 74
2.2 Big-O Notation......Page 75
2.3 Properties of Big-O Notation......Page 77
2.4 Ω and Θ Notations......Page 79
2.6 Examples of Complexities......Page 80
2.7 Finding Asymptotic Complexity: Examples......Page 82
2.8 The Best, Average, and Worst Cases......Page 84
2.9 Amortized Complexity......Page 87
2.10 NP-Completeness......Page 91
2.11 Exercises......Page 94
Bibliography......Page 97
3.1 Singly Linked Lists......Page 98
3.1.1 Insertion......Page 104
3.1.2 Deletion......Page 106
3.1.3 Search......Page 111
3.2 Doubly Linked Lists......Page 113
3.3 Circular Lists......Page 117
3.4 Skip Lists......Page 119
3.5 Self-Organizing Lists......Page 125
3.6 Sparse Tables......Page 129
3.7.1 LinkedList......Page 132
3.7.2 ArrayList......Page 138
3.8 Concluding Remarks......Page 141
3.9 Case Study: A Library......Page 142
3.10 Exercises......Page 152
3.11 Programming Assignments......Page 154
Bibliography......Page 157
4.1 Stacks......Page 158
4.1.1 Stacks in java.util......Page 166
4.2 Queues......Page 167
4.3 Priority Queues......Page 175
4.4 Case Study: Exiting a Maze......Page 176
4.5 Exercises......Page 182
4.6 Programming Assignments......Page 184
Bibliography......Page 186
5.1 Recursive Definitions......Page 187
5.2 Method Calls and Recursion Implementation......Page 190
5.3 Anatomy of a Recursive Call......Page 192
5.4 Tail Recursion......Page 196
5.5 Nontail Recursion......Page 197
5.6 Indirect Recursion......Page 203
5.7 Nested Recursion......Page 205
5.8 Excessive Recursion......Page 206
5.9 Backtracking......Page 209
5.10 Concluding Remarks......Page 216
5.11 Case Study: A Recursive Descent Interpreter......Page 217
5.12 Exercises......Page 225
5.13 Programming Assignments......Page 228
Bibliography......Page 230
6.1 Trees, Binary Trees, and Binary Search Trees......Page 232
6.2 Implementing Binary Trees......Page 237
6.3 Searching a Binary Search Tree......Page 239
6.4 Tree Traversal......Page 241
6.4.1 Breadth-First Traversal......Page 242
6.4.2 Depth-First Traversal......Page 243
6.4.3 Stackless Depth-First Traversal......Page 249
6.5 Insertion......Page 257
6.6 Deletion......Page 260
6.6.1 Deletion by Merging......Page 261
6.6.2 Deletion by Copying......Page 264
6.7 Balancing a Tree......Page 267
6.7.1 The DSW Algorithm......Page 270
6.7.2 AVL Trees......Page 273
6.8 Self-Adjusting Trees......Page 278
6.8.1 Self-Restructuring Trees......Page 279
6.8.2 Splaying......Page 280
6.9 Heaps......Page 285
6.9.1 Heaps as Priority Queues......Page 287
6.9.2 Organizing Arrays as Heaps......Page 290
6.10 Polish Notation and Expression Trees......Page 293
6.10.1 Operations on Expression Trees......Page 295
6.11 Case Study: Computing Word Frequencies......Page 298
6.12 Exercises......Page 307
6.13 Programming Assignments......Page 310
Bibliography......Page 314
7 MULTIWAY TREES......Page 317
7.1 The Family of B-Trees......Page 318
7.1.1 B-Trees......Page 319
7.1.2 B*-Trees......Page 330
7.1.3 B+-Trees......Page 331
7.1.4 Prefix B+-Trees......Page 334
7.1.5 Bit-Trees......Page 337
7.1.6 R-Trees......Page 338
7.1.7 2–4 Trees......Page 341
7.1.8 Trees in java.util......Page 356
7.2 Tries......Page 367
7.4 Case Study: Spell Checker......Page 376
7.5 Exercises......Page 387
7.6 Programming Assignments......Page 388
Bibliography......Page 392
8 GRAPHS......Page 394
8.1 Graph Representation......Page 395
8.2 Graph Traversals......Page 397
8.3 Shortest Paths......Page 401
8.3.1 All-to-All Shortest Path Problem......Page 408
8.4 Cycle Detection......Page 410
8.4.1 Union-Find Problem......Page 411
8.5 Spanning Trees......Page 413
8.6.1 Connectivity in Undirected Graphs......Page 417
8.6.2 Connectivity in Directed Graphs......Page 420
8.7 Topological Sort......Page 423
8.8.1 Maximum Flows......Page 425
8.8.2 Maximum Flows of Minimum Cost......Page 435
8.9 Matching......Page 439
8.9.1 Stable Matching Problem......Page 444
8.9.2 Assignment Problem......Page 446
8.9.3 Matching in Nonbipartite Graphs......Page 448
8.10.1 Eulerian Graphs......Page 450
8.10.2 Hamiltonian Graphs......Page 454
8.11 Graph Coloring......Page 460
8.12.1 The Clique Problem......Page 463
8.12.2 The 3-Colorability Problem......Page 464
8.12.3 The Vertex Cover Problem......Page 466
8.12.4 The Hamiltonian Cycle Problem......Page 467
8.13 Case Study: Distinct Representatives......Page 468
8.14 Exercises......Page 478
8.15 Programming Assignments......Page 482
Bibliography......Page 484
9 SORTING......Page 487
9.1.1 Insertion Sort......Page 488
9.1.2 Selection Sort......Page 492
9.1.3 Bubble Sort......Page 493
9.2 Decision Trees......Page 495
9.3.1 Shell Sort......Page 499
9.3.2 Heap Sort......Page 502
9.3.3 Quicksort......Page 506
9.3.4 Mergesort......Page 512
9.3.5 Radix Sort......Page 515
9.4 Sorting in java.util......Page 520
9.5 Concluding Remarks......Page 523
9.6 Case Study: Adding Polynomials......Page 525
9.7 Exercises......Page 533
9.8 Programming Assignments......Page 534
Bibliography......Page 535
10 HASHING......Page 537
10.1.2 Folding......Page 538
10.1.4 Extraction......Page 539
10.2.1 Open Addressing......Page 540
10.2.2 Chaining......Page 546
10.2.3 Bucket Addressing......Page 548
10.3 Deletion......Page 549
10.4 Perfect Hash Functions......Page 550
10.4.1 Cichelli’s Method......Page 551
10.4.2 The FHCD Algorithm......Page 554
10.5 Hash Functions for Extendible Files......Page 556
10.5.1 Extendible Hashing......Page 557
10.5.2 Linear Hashing......Page 559
10.6.1 HashMap......Page 562
10.6.2 HashSet......Page 565
10.6.3 HashTable......Page 570
10.7 Case Study: Hashing with Buckets......Page 575
10.8 Exercises......Page 584
10.9 Programming Assignments......Page 585
Bibliography......Page 586
11.1 Conditions for Data Compression......Page 588
11.2 Huffman Coding......Page 590
11.2.1 Adaptive Huffman Coding......Page 599
11.3 Run-Length Encoding......Page 604
11.4 Ziv-Lempel Code......Page 605
11.5 Case Study: Huffman Method with Run-Length Encoding......Page 608
11.7 Programming Assignments......Page 619
Bibliography......Page 621
12 MEMORY MANAGEMENT......Page 622
12.1 The Sequential-Fit Methods......Page 623
12.2 The Nonsequential-Fit Methods......Page 624
12.2.1 Buddy Systems......Page 626
12.3 Garbage Collection......Page 633
12.3.1 Mark-and-Sweep......Page 634
12.3.2 Copying Methods......Page 641
12.3.3 Incremental Garbage Collection......Page 643
12.4 Concluding Remarks......Page 651
12.5 Case Study: An In-Place Garbage Collector......Page 652
12.6 Exercises......Page 661
12.7 Programming Assignments......Page 662
Bibliography......Page 665
13.1.1 Straightforward Algorithms......Page 667
13.1.2 The Knuth-Morris-Pratt Algorithm......Page 670
13.1.3 The Boyer-Moore Algorithm......Page 678
13.1.4 Multiple Searches......Page 688
13.1.5 Bit-Oriented Approach......Page 690
13.1.6 Matching Sets of Words......Page 694
13.1.7 Regular Expression Matching......Page 700
13.1.8 Suffix Tries and Trees......Page 704
13.1.9 Suffix Arrays......Page 711
13.2 Approximate String Matching......Page 712
13.2.1 String Similarity......Page 713
13.2.2 String Matching with k Errors......Page 719
13.3 Case Study: Longest Common Substring......Page 722
13.4 Exercises......Page 731
13.5 Programming Assignments......Page 733
Bibliography......Page 734
A.2 Approximation of the Function lg(n!)......Page 736
A.3 Big-O for Average Case of Quicksort......Page 738
A.4 Average Path Length in a Random Binary Tree......Page 740
A.5 The Number of Nodes in an AVL Tree......Page 741
B.1 Cook’s Theorem......Page 742
Name Index......Page 755
Subject Index......Page 758