Data Structures and Algorithms Made Easy in Java

Title Page......Page 2
Copyright Page......Page 3
Acknowledgements......Page 4
Preface......Page 5
Table of Contents......Page 8
1.1 Variables......Page 16
1.2 Data Types......Page 17
1.4 Abstract Data Types (ADTs)......Page 18
1.6 Why the Analysis of Algorithms?......Page 19
1.10 What is Rate of Growth?......Page 20
1.11 Commonly used Rates of Growth......Page 21
1.12 Types of Analysis......Page 22
1.14 Big-O Notation......Page 23
1.15 Omega-Ω Notation......Page 26
1.16 Theta-Θ Notation......Page 27
1.19 Guidelines for Asymptotic Analysis......Page 29
1.20 Properties of Notations......Page 31
1.21 Commonly used Logarithms and Summations......Page 32
1.23 Divide and Conquer Master Theorem: Problems & Solutions......Page 33
1.26 Method of Guessing and Confirming......Page 35
1.28 Algorithms Analysis: Problems & Solutions......Page 38
2.2 What is Recursion?......Page 60
2.4 Format of a Recursive Function......Page 61
2.5 Recursion and Memory (Visualization)......Page 62
2.6 Recursion versus Iteration......Page 63
2.9 Recursion: Problems & Solutions......Page 64
2.10 What is Backtracking?......Page 66
2.12 Backtracking: Problems & Solutions......Page 67
3.1 What is a Linked List?......Page 69
3.4 Arrays Overview......Page 70
3.5 Comparison of Linked Lists with Arrays & Dynamic Arrays......Page 72
3.6 Singly Linked Lists......Page 73
3.7 Doubly Linked Lists......Page 85
3.8 Circular Linked Lists......Page 98
3.9 A Memory-efficient Doubly Linked List......Page 109
3.10 Unrolled Linked Lists......Page 111
3.11 Skip Lists......Page 125
3.12 Linked Lists: Problems & Solutions......Page 130
4.1 What is a Stack?......Page 171
4.3 Stack ADT......Page 172
4.6 Implementation......Page 173
4.7 Comparison of Implementations......Page 182
4.8 Stacks: Problems & Solutions......Page 183
5.1 What is a Queue?......Page 218
5.3 Queue ADT......Page 219
5.6 Implementation......Page 220
5.7 Queues: Problems & Solutions......Page 230
6.2 Glossary......Page 239
6.3 Binary Trees......Page 242
6.4 Binary Tree Traversals......Page 247
6.5 Generic Trees (N-ary Trees)......Page 291
6.6 Threaded Binary Tree Traversals (Stack or Queue-less Traversals)......Page 303
6.7 Expression Trees......Page 313
6.8 XOR Trees......Page 317
6.9 Binary Search Trees (BSTs)......Page 319
6.10 Balanced Binary Search Trees......Page 343
6.11 AVL (Adelson-Velskii and Landis) Trees......Page 344
6.12 Other Variations on Trees......Page 367
7.1 What is a Priority Queue?......Page 374
7.3 Priority Queue Applications......Page 375
7.4 Priority Queue Implementations......Page 376
7.5 Heaps and Binary Heaps......Page 377
7.6 Binary Heaps......Page 379
7.7 Priority Queues [Heaps]: Problems & Solutions......Page 390
8.2 Equivalence Relations and Equivalence Classes......Page 410
8.3 Disjoint Sets ADT......Page 411
8.5 Tradeoffs in Implementing Disjoint Sets ADT......Page 412
8.6 Fast UNION Implementation (Slow FIND)......Page 413
8.7 Fast UNION Implementations (Quick FIND)......Page 419
8.8 Path Compression......Page 423
8.9 Summary......Page 424
8.10 Disjoint Sets: Problems & Solutions......Page 425
9.2 Glossary......Page 428
9.3 Applications of Graphs......Page 433
9.4 Graph Representation......Page 434
9.5 Graph Traversals......Page 439
9.6 Topological Sort......Page 452
9.7 Shortest Path Algorithms......Page 454
9.8 Minimal Spanning Tree......Page 464
9.9 Graph Algorithms: Problems & Solutions......Page 473
10.3 Classification of Sorting Algorithms......Page 507
10.5 Bubble Sort......Page 509
10.6 Selection Sort......Page 511
10.7 Insertion Sort......Page 512
10.8 Shell Sort......Page 516
10.9 Merge Sort......Page 518
10.10 Heap Sort......Page 520
10.11 Quick Sort......Page 521
10.12 Tree Sort......Page 525
10.14 Linear Sorting Algorithms......Page 526
10.15 Counting Sort......Page 527
10.16 Bucket Sort (or Bin Sort)......Page 528
10.19 External Sorting......Page 529
10.20 Sorting: Problems & Solutions......Page 531
11.2 Why do we need Searching?......Page 552
11.5 Sorted/Ordered Linear Search......Page 553
11.6 Binary Search......Page 554
11.7 Interpolation Search......Page 555
11.8 Comparing Basic Searching Algorithms......Page 558
11.11 Searching: Problems & Solutions......Page 559
12.2 Selection by Sorting......Page 600
12.6 Selection Algorithms: Problems & Solutions......Page 601
13.2 What are Symbol Tables?......Page 617
13.3 Symbol Table Implementations......Page 618
13.4 Comparison Table of Symbols for Implementations......Page 619
14.3 HashTable ADT......Page 621
14.4 Understanding Hashing......Page 622
14.5 Components of Hashing......Page 624
14.7 Hash Function......Page 625
14.8 Load Factor......Page 626
14.11 Separate Chaining......Page 627
14.12 Open Addressing......Page 628
14.13 Comparison of Collision Resolution Techniques......Page 631
14.15 Hashing Techniques......Page 632
14.17 Bloom Filters......Page 633
14.18 Hashing: Problems & Solutions......Page 636
15.1 Introduction......Page 652
15.3 Brute Force Method......Page 653
15.4 Rabin-Karp String Matching Algorithm......Page 654
15.5 String Matching with Finite Automata......Page 655
15.6 KMP Algorithm......Page 657
15.8 Data Structures for Storing Strings......Page 663
15.10 Binary Search Trees for Strings......Page 664
15.11 Tries......Page 665
15.12 Ternary Search Trees......Page 668
15.13 Comparing BSTs, Tries and TSTs......Page 675
15.14 Suffix Trees......Page 676
15.15 String Algorithms: Problems & Solutions......Page 681
16.2 Classification......Page 702
16.3 Classification by Implementation Method......Page 703
16.4 Classification by Design Method......Page 704
16.5 Other Classifications......Page 705
17.2 Greedy Strategy......Page 707
17.6 Greedy Applications......Page 708
17.7 Understanding Greedy Technique......Page 709
17.8 Greedy Algorithms: Problems & Solutions......Page 713
18.2 What is Divide and Conquer Strategy?......Page 724
18.4 Divide and Conquer Visualization......Page 725
18.5 Understanding Divide and Conquer......Page 726
18.8 Master Theorem......Page 727
18.10 Divide and Conquer: Problems & Solutions......Page 728
19.2 What is Dynamic Programming Strategy?......Page 754
19.5 Dynamic Programming Approaches......Page 755
19.7 Understanding Dynamic Programming......Page 756
19.8 Dynamic Programming: Problems & Solutions......Page 766
20.1 Introduction......Page 816
20.3 What is a Decision Problem?......Page 817
20.6 Types of Complexity Classes......Page 818
20.7 Reductions......Page 822
20.8 Complexity Classes: Problems & Solutions......Page 826
21.2 Hacks on Bitwise Programming......Page 830
21.3 Other Programming Questions......Page 838
22. References......Page 848