Data Structures and Algorithms in Javascript: Optimizing perfomance and solving programming challenges

Cover....1 Praise for Data Structures and Algorithms in Javascript....3 Title Page....7 Copyright....8 Dedication....9 About the Author....11 About the Technical Reviewer....11 Brief Contents....13 Contents in Detail....15 Preface....23 Acknowledgments....25 Introduction....27 Who Should Read This Book?....28 Whats the Books Approach?....28 Whats in the Book?....28 Part I: The Basics....33 1. Using Javascript....35 Modern JavaScript Features....36 Arrow Functions....36 Classes....37 The Spread Operator....38 The Destructuring Statement....39 Modules....40 Closures and Immediately Invoked Function Expressions....43 JavaScript Development Tools....45 Visual Studio Code....45 Fira Code Font....47 Prettier Formatting....48 JSDoc Documentation....48 ESLint....50 Flow and TypeScript....50 Online Feature Availability Resources....51 Summary....53 2. Functional Programming in Javascript....55 Why Use Functional Programming?....56 JavaScript as a Functional Language....57 Functions as First-Class Objects....57 Declarative-Style Programming....58 Higher-Order Functions....62 Side Effects....64 Impure Functions....65 Summary....67 Questions....67 3. Abstract Data Types....69 The Theory....70 Data Types....70 Abstraction....71 Operations and Mutations....71 Implementing an ADT....72 Implementing ADTs Using Classes....73 Implementing ADTs Using Functions (Mutable Version)....75 Implementing ADTs Using Functions (Immutable Version)....77 Summary....78 Questions....78 4. Analyzing Algorithms....81 Performance....82 Complexity....82 Notations for Complexity....83 Complexity Classes....84 Performance Measurements....86 Analysis of Algorithms in Practice....87 Time and Space Complexity Trade-offs....89 Summary....90 Questions....90 Part II: Algorithms....93 5. Designing Algorithms....95 Recursion....96 The Divide-and-Conquer Strategy....97 The Backtracking Technique....101 Dynamic Programming....104 Calculating Fibonacci Series with Top-Down DP....104 Line Breaking with Top-Down DP....106 Calculating Fibonacci Series with Bottom-Up DP....111 Summing Ranges Recursively with Bottom-Up DP....112 Summing Ranges by Precomputing with Bottom-Up DP....113 Brute-Force Search....114 Detecting Tautologies....114 Solving Cryptarithmetic Puzzles....115 Greedy Algorithms....119 How to Make Change....119 The Traveling Salesman Problem....119 Minimum Spanning Tree....120 Summary....120 Questions....120 6. Sorting....123 The Sorting Problem....124 Internal vs. External Sorting....124 Adaptive Sorting....124 In-Place and Out-of-Place Sorting....125 Online and Offline Sorting....125 Sorting Stability....125 JavaScripts Own Sort Method....127 Sort Performance....128 Sorting with Comparisons....129 Bubbling Up and Down....129 Sorting Strategies for Playing Cards....132 Making Bigger Jumps with Comb and Shell Sort....135 Going for Speed with Quicksort....137 Merging for Performance with Merge Sort....142 Sorting Without Comparisons....144 Bitmap Sort....144 Counting Sort....146 Radix Sort....147 Inefficient Sorting Algorithms....148 Stooge Sort....148 Slow Sort....148 Permutation Sort....149 Bogosort....149 Sleep Sort....149 Summary....149 Questions....150 7. Selecting....153 Selection Without Comparisons....154 Bitmap Selection....154 Counting Selection....155 Selecting with Comparisons....156 The Quickselect Family....157 Quickselect....158 Median of Medians....159 Repeated Step....162 Finding the Median with Lazy Select....164 Summary....166 Questions....166 8. Shuffling and Sampling....169 Choosing Numbers Randomly....170 Shuffling....171 Shuffling by Sorting....171 Shuffling by Coin Tossing....172 Shuffling in Linear Time....174 Sampling....178 Sampling with Repetition....178 Sampling Without Repetition....179 Summary....186 Questions....187 9. Searching....191 Search Definition....191 Searching Unsorted Arrays....192 JavaScripts Methods....192 Linear Search....192 Linear Search with Sentinels....193 Searching Ordered Arrays....195 Jump Search....195 Binary Search....198 Exponential Search....200 Interpolation Search....201 Summary....203 Questions....204 Part III: Data Structures....207 10. Lists....209 Basic Lists....210 Implementing Lists with Arrays....211 Implementing Lists with Dynamic Memory....212 Varieties of Lists....216 Stacks....216 Queues....220 Deques....223 Circular Lists....227 Summary....232 Questions....232 11. Bags, Sets, and Maps....235 Introducing Bags, Sets, and Maps....235 JavaScripts Solutions for Sets....237 Objects as Sets....237 Set Objects....238 Bitmaps....238 Using Lists....239 Ordered Lists....239 Skip Lists....242 Self-Organizing Lists....247 Hashing....250 Hashing with Chaining....251 Hashing with Open Addressing....253 Double Hashing....258 Double Hashing with Prime Lengths....261 Summary....264 Questions....264 12. Binary Trees....267 What Are Trees?....268 General Trees....269 Binary Trees....269 Binary Search Trees....271 Assured Balanced Binary Search Trees....281 AVL Trees....281 Weight-Bounded Balanced Trees....287 Probabilistic Balance Binary Search Trees....293 Randomized Binary Search Trees....294 Splay Trees....302 Summary....310 Questions....311 13. Trees and Forests....315 Defining Trees and Forests....315 Representing Trees with Arrays....316 Representing Trees with Binary Trees....319 Representing Forests....320 Traversing Trees....320 B-trees....323 Defining B-trees....324 Finding a Key in a B-tree....325 Traversing a B-tree....326 Adding a Key to a B-tree....327 Removing a Key from a B-tree....330 Considering Performance for B-trees....335 Red-Black Trees....336 Representing Red-Black Trees....337 Adding a Key to a Red-Black Tree....338 Restoring a Red-Black Tree Structure....339 Removing a Key from a Red-Black Tree....341 Considering Performance for Red-Black Trees....345 Summary....346 Questions....346 14. Heaps....349 Binary Heaps....350 The Structure Property....350 The Heap Property....351 Heap Implementation....352 Priority Queues and Heaps....358 Heapsort....359 Williams Original Heapsort....359 Heapsort Analysis....361 Floyds Heap-Building Enhancement....361 Treaps....364 Creating and Searching a Treap....364 Adding a Key to a Treap....365 Removing a Key from a Treap....368 Considering the Performance of Treaps....371 Ternary and D-ary Heaps....372 Summary....373 Questions....373 15. Extended Heaps....377 Meldable and Addressable Priority Queues....378 Skew Heaps....379 Representing a Skew Heap....380 Merging Two Skew Heaps....380 Adding a Key to a Skew Heap....382 Removing the Top Key from a Skew Heap....382 Considering Performance for Skew Heaps....382 Binomial Heaps....383 Binomial Trees....383 Defining Binomial Heaps....385 Adding a Value to a Binomial Heap....386 Merging Two Binomial Heaps....388 Removing a Value from a Binomial Heap....390 Changing a Value in a Binomial Heap....392 Considering Performance for Binomial Heaps....394 Lazy Binomial Heaps....395 Defining Lazy Binomial Heaps....395 Adding a Value to a Lazy Binomial Heap....396 Removing a Value from a Lazy Binomial Heap....397 Changing a Value in a Lazy Binomial Heap....398 Considering Performance for Lazy Binomial Heaps....399 Fibonacci Heaps....399 Representing a Fibonacci Heap....400 Merging Two Fibonacci Trees....402 Adding a Value to a Fibonacci Heap....403 Removing a Value from a Fibonacci Heap....403 Changing a Value in a Fibonacci Heap....404 Considering Performance for Fibonacci Heaps....407 Pairing Heaps....408 Defining a Pairing Heap....409 Melding Two Pairing Heaps....409 Adding a Value to a Pairing Heap....410 Removing the Top Value from a Pairing Heap....410 Changing a Value in a Pairing Heap....414 Considering Performance for Pairing Heaps....416 Summary....417 Questions....417 16. Digital Search Trees....419 The Classic Version of Tries....420 Storing Extra Data in a Trie....422 Searching a Trie....422 Adding a Key to a Trie....426 Removing a Key from a Trie....429 Considering Performance for Tries....433 An Enhanced Version of Tries....433 Defining an Object-Based Trie....434 Searching an Object-Based Trie....434 Adding a Key to an Object-Based Trie....436 Removing a Key from an Object-Based Trie....437 Considering Performance for Object-Based Tries....438 Radix Trees....438 Defining a Radix Tree....439 Searching a Radix Tree....439 Adding a Key to a Radix Tree....442 Removing a Key from a Radix Tree....444 Considering Performance for Radix Trees....446 Ternary Search Tries....446 Defining Ternary Tries....447 Storing Extra Data in a Ternary Trie....448 Searching a Ternary Trie....448 Adding a Key to a Ternary Trie....449 Removing a Key from a Ternary Trie....451 Considering Performance for Ternary Tries....455 Summary....456 Questions....456 17. Graphs....457 What Are Graphs?....457 Representing Graphs....460 Adjacency Matrix Representation for Graphs....460 Adjacency List Representation for Graphs....461 Adjacency Set Representation for Graphs....462 Finding the Shortest Paths....462 Floyd-Warshalls All Paths Algorithm....462 Bellman-Ford Algorithm....466 Dijkstras Algorithm....470 Sorting a Graph....476 Kahns Algorithm....477 Tarjans Algorithm....480 Detecting Cycles....484 Detecting Connectivity....485 Detecting Connectivity with Sets....486 Detecting Connectivity with Searches....488 Finding a Minimum Spanning Tree....490 Prims Algorithm....491 Kruskals Algorithm....494 Summary....498 Questions....498 18. Immutability and Functional Data Structures....501 Functional Data Structures....502 Arrays (and Hash Tables....502 Functional Lists....502 Functional Trees....510 Summary....517 Questions....517 Answer Key....519 Bibliography....577 Index....581 Back Cover....595