Data Structures and Algorithms Made Easy in Java

Description

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