Data Structures and Algorithms in JavaScript

Cover
Praise for Data Structures and Algorithms in Javascript
Title Page
Copyright
Dedication
About the Author
About the Technical Reviewer
Brief Contents
Contents in Detail
Preface
Acknowledgments
Introduction
	Who Should Read This Book?
	What’s the Book’s Approach?
	What’s in the Book?
Part I: The Basics
	1. Using Javascript
		Modern JavaScript Features
			Arrow Functions
			Classes
			The Spread Operator
			The Destructuring Statement
			Modules
			Closures and Immediately Invoked Function Expressions
		JavaScript Development Tools
			Visual Studio Code
			Fira Code Font
			Prettier Formatting
			JSDoc Documentation
			ESLint
			Flow and TypeScript
			Online Feature Availability Resources
		Summary
	2. Functional Programming in Javascript
		Why Use Functional Programming?
		JavaScript as a Functional Language
			Functions as First-Class Objects
			Declarative-Style Programming
			Higher-Order Functions
			Side Effects
			Impure Functions
		Summary
		Questions
	3. Abstract Data Types
		The Theory
			Data Types
			Abstraction
			Operations and Mutations
		Implementing an ADT
			Implementing ADTs Using Classes
			Implementing ADTs Using Functions (Mutable Version)
			Implementing ADTs Using Functions (Immutable Version)
		Summary
		Questions
	4. Analyzing Algorithms
		Performance
		Complexity
			Notations for Complexity
			Complexity Classes
			Performance Measurements
			Analysis of Algorithms in Practice
			Time and Space Complexity Trade-offs
		Summary
		Questions
Part II: Algorithms
	5. Designing Algorithms
		Recursion
			The Divide-and-Conquer Strategy
			The Backtracking Technique
		Dynamic Programming
			Calculating Fibonacci Series with Top-Down DP
			Line Breaking with Top-Down DP
			Calculating Fibonacci Series with Bottom-Up DP
			Summing Ranges Recursively with Bottom-Up DP
			Summing Ranges by Precomputing with Bottom-Up DP
		Brute-Force Search
			Detecting Tautologies
			Solving Cryptarithmetic Puzzles
		Greedy Algorithms
			How to Make Change
			The Traveling Salesman Problem
			Minimum Spanning Tree
		Summary
		Questions
	6. Sorting
		The Sorting Problem
			Internal vs. External Sorting
			Adaptive Sorting
			In-Place and Out-of-Place Sorting
			Online and Offline Sorting
			Sorting Stability
			JavaScript’s Own Sort Method
			Sort Performance
		Sorting with Comparisons
			Bubbling Up and Down
			Sorting Strategies for Playing Cards
			Making Bigger Jumps with Comb and Shell Sort
			Going for Speed with Quicksort
			Merging for Performance with Merge Sort
		Sorting Without Comparisons
			Bitmap Sort
			Counting Sort
			Radix Sort
		Inefficient Sorting Algorithms
			Stooge Sort
			Slow Sort
			Permutation Sort
			Bogosort
			Sleep Sort
		Summary
		Questions
	7. Selecting
		Selection Without Comparisons
			Bitmap Selection
			Counting Selection
		Selecting with Comparisons
		The Quickselect Family
			Quickselect
			Median of Medians
			Repeated Step
		Finding the Median with Lazy Select
		Summary
		Questions
	8. Shuffling and Sampling
		Choosing Numbers Randomly
		Shuffling
			Shuffling by Sorting
			Shuffling by Coin Tossing
			Shuffling in Linear Time
		Sampling
			Sampling with Repetition
			Sampling Without Repetition
		Summary
		Questions
	9. Searching
		Search Definition
		Searching Unsorted Arrays
			JavaScript’s Methods
			Linear Search
			Linear Search with Sentinels
		Searching Ordered Arrays
			Jump Search
			Binary Search
			Exponential Search
			Interpolation Search
		Summary
		Questions
Part III: Data Structures
	10. Lists
		Basic Lists
			Implementing Lists with Arrays
			Implementing Lists with Dynamic Memory
		Varieties of Lists
			Stacks
			Queues
			Deques
			Circular Lists
		Summary
		Questions
	11. Bags, Sets, and Maps
		Introducing Bags, Sets, and Maps
		JavaScript’s Solutions for Sets
			Objects as Sets
			Set Objects
		Bitmaps
		Using Lists
			Ordered Lists
			Skip Lists
			Self-Organizing Lists
		Hashing
			Hashing with Chaining
			Hashing with Open Addressing
			Double Hashing
			Double Hashing with Prime Lengths
		Summary
		Questions
	12. Binary Trees
		What Are Trees?
			General Trees
			Binary Trees
			Binary Search Trees
		Assured Balanced Binary Search Trees
			AVL Trees
			Weight-Bounded Balanced Trees
		Probabilistic Balance Binary Search Trees
			Randomized Binary Search Trees
			Splay Trees
		Summary
		Questions
	13. Trees and Forests
		Defining Trees and Forests
			Representing Trees with Arrays
			Representing Trees with Binary Trees
			Representing Forests
			Traversing Trees
		B-trees
			Defining B-trees
			Finding a Key in a B-tree
			Traversing a B-tree
			Adding a Key to a B-tree
			Removing a Key from a B-tree
			Considering Performance for B-trees
		Red-Black Trees
			Representing Red-Black Trees
			Adding a Key to a Red-Black Tree
			Restoring a Red-Black Tree Structure
			Removing a Key from a Red-Black Tree
			Considering Performance for Red-Black Trees
		Summary
		Questions
	14. Heaps
		Binary Heaps
			The Structure Property
			The Heap Property
			Heap Implementation
		Priority Queues and Heaps
		Heapsort
			Williams’ Original Heapsort
			Heapsort Analysis
			Floyd’s Heap-Building Enhancement
		Treaps
			Creating and Searching a Treap
			Adding a Key to a Treap
			Removing a Key from a Treap
			Considering the Performance of Treaps
		Ternary and D-ary Heaps
		Summary
		Questions
	15. Extended Heaps
		Meldable and Addressable Priority Queues
		Skew Heaps
			Representing a Skew Heap
			Merging Two Skew Heaps
			Adding a Key to a Skew Heap
			Removing the Top Key from a Skew Heap
			Considering Performance for Skew Heaps
		Binomial Heaps
			Binomial Trees
			Defining Binomial Heaps
			Adding a Value to a Binomial Heap
			Merging Two Binomial Heaps
			Removing a Value from a Binomial Heap
			Changing a Value in a Binomial Heap
			Considering Performance for Binomial Heaps
		Lazy Binomial Heaps
			Defining Lazy Binomial Heaps
			Adding a Value to a Lazy Binomial Heap
			Removing a Value from a Lazy Binomial Heap
			Changing a Value in a Lazy Binomial Heap
			Considering Performance for Lazy Binomial Heaps
		Fibonacci Heaps
			Representing a Fibonacci Heap
			Merging Two Fibonacci Trees
			Adding a Value to a Fibonacci Heap
			Removing a Value from a Fibonacci Heap
			Changing a Value in a Fibonacci Heap
			Considering Performance for Fibonacci Heaps
		Pairing Heaps
			Defining a Pairing Heap
			Melding Two Pairing Heaps
			Adding a Value to a Pairing Heap
			Removing the Top Value from a Pairing Heap
			Changing a Value in a Pairing Heap
			Considering Performance for Pairing Heaps
		Summary
		Questions
	16. Digital Search Trees
		The Classic Version of Tries
		Storing Extra Data in a Trie
			Searching a Trie
			Adding a Key to a Trie
			Removing a Key from a Trie
			Considering Performance for Tries
		An Enhanced Version of Tries
			Defining an Object-Based Trie
			Searching an Object-Based Trie
			Adding a Key to an Object-Based Trie
			Removing a Key from an Object-Based Trie
			Considering Performance for Object-Based Tries
		Radix Trees
			Defining a Radix Tree
			Searching a Radix Tree
			Adding a Key to a Radix Tree
			Removing a Key from a Radix Tree
			Considering Performance for Radix Trees
		Ternary Search Tries
			Defining Ternary Tries
			Storing Extra Data in a Ternary Trie
			Searching a Ternary Trie
			Adding a Key to a Ternary Trie
			Removing a Key from a Ternary Trie
			Considering Performance for Ternary Tries
		Summary
		Questions
	17. Graphs
		What Are Graphs?
		Representing Graphs
			Adjacency Matrix Representation for Graphs
			Adjacency List Representation for Graphs
			Adjacency Set Representation for Graphs
		Finding the Shortest Paths
			Floyd-Warshall’s “All Paths” Algorithm
			Bellman-Ford Algorithm
			Dijkstra’s Algorithm
		Sorting a Graph
			Kahn’s Algorithm
			Tarjan’s Algorithm
		Detecting Cycles
		Detecting Connectivity
			Detecting Connectivity with Sets
			Detecting Connectivity with Searches
		Finding a Minimum Spanning Tree
			Prim’s Algorithm
			Kruskal’s Algorithm
		Summary
		Questions
	18. Immutability and Functional Data Structures
		Functional Data Structures
			Arrays (and Hash Tables
			Functional Lists
			Functional Trees
		Summary
		Questions
Answer Key
Bibliography
Index
Back Cover