C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications. Code

Cover
FM
Copyright
Table of Contents
Preface
Chapter 1: Lists, Stacks, and Queues
	Introduction
	Contiguous Versus Linked Data Structures
		Contiguous Data Structures
		Linked Data Structures
		Comparison
		Limitations of C-style Arrays
	std::array
		Exercise 1: Implementing a Dynamic Sized Array
		Exercise 2: A General-Purpose and Fast Data Storage Container Builder
	std::vector
		std::vector – Variable Length Array
		Allocators for std::vector
	std::forward_list
		Inserting and Deleting Elements in forward_list
		Other Operations on forward_list
		Exercise 3: Conditional Removal of Elements from a Linked List Using remove_if
	Iterators
		Exercise 4: Exploring Different Types of Iterators
		Exercise 5: Building a Basic Custom Container
		Activity 1: Implementing a Song Playlist
	std::list
		Common Functions for std::list
		Exercise 6: Insertion and Deletion Functions for std::list
		Bidirectional Iterators
		Iterator Invalidation for Different Containers
		Activity 2: Simulating a Card Game
	std::deque – Special Version of std::vector
		The Structure of Deque
	Container Adaptors
		std::stack
		std::queue
		std::priority_queue
		Iterators for Adaptors
	Benchmarking
		Activity 3: Simulating a Queue for a Shared Printer in an Office
	Summary
Chapter 2: Trees, Heaps, and Graphs
	Introduction
	Non-Linear Problems
		Hierarchical Problems
		Cyclic Dependencies
	Tree – It\'s Upside Down!
		Exercise 7: Creating an Organizational Structure
		Traversing Trees
		Exercise 8: Demonstrating Level Order Traversal
	Variants of Trees
		Binary Search Tree
		Time Complexities of Operations on a Tree
		Exercise 9: Implementing a Binary Search Tree
		Balanced Tree
		N-ary Tree
		Activity 4: Create a Data Structure for a Filesystem
	Heaps
		Heap Operations
		Exercise 10: Streaming Median
		Activity 5: K-Way Merge Using Heaps
	Graphs
		Representing a Graph as an Adjacency Matrix
		Exercise 11: Implementing a Graph and Representing it as an Adjacency Matrix
		Representing a Graph as an Adjacency List
		Exercise 12: Implementing a Graph and Representing it as an Adjacency List
	Summary
Chapter 3: Hash Tables and Bloom Filters
	Introduction
	Hash Tables
		Hashing
		Exercise 13: Basic Dictionary for Integers
	Collisions in Hash Tables
		Close Addressing – Chaining
		Exercise 14: Hash Table with Chaining
		Open Addressing
		Perfect Hashing – Cuckoo Hashing
		Exercise 15: Cuckoo Hashing
	C++ Hash Tables
		Exercise 16: Hash Tables Provided by STL
		Activity 6: Mapping Long URLs to Short URLs
	Bloom Filters
		Exercise 17: Creating Bloom Filters
		Activity 7: Email Address Validator
	Summary
Chapter 4: Divide and Conquer
	Introduction
	Binary Search
		Exercise 18: Binary Search Benchmarks
		Activity 8: Vaccinations
	Understanding the Divide-and-Conquer Approach
	Sorting Using Divide and Conquer
		Merge Sort
		Exercise 19: Merge Sort
		Quicksort
		Exercise 20: Quicksort
		Activity 9: Partial Sorting
		Linear Time Selection
		Exercise 21: Linear Time Selection
	C++ Standard Library Tools for Divide and Conquer
	Dividing and Conquering at a Higher Abstraction Level – MapReduce
		The Map and Reduce Abstractions
		Exercise 22: Map and Reduce in the C++ Standard Library
		Integrating the Parts – Using a MapReduce Framework
		Exercise 23: Checking Primes Using MapReduce
		Activity 10: Implementing WordCount in MapReduce
	Summary
Chapter 5: Greedy Algorithms
	Introduction
	Basic Greedy Algorithms
		Shortest-Job-First Scheduling
		Exercise 24: Shortest-Job-First Scheduling
	The Knapsack Problem(s)
		The Knapsack Problem
		The Fractional Knapsack Problem
		Exercise 25: Fractional Knapsack Problem
		Activity 11: The Interval Scheduling Problem
		Requirements for Greedy Algorithms
		The Minimum Spanning Tree (MST) Problem
		Disjoint-Set (or Union-Find) Data Structures
		Exercise 26: Kruskal\'s MST Algorithm
	The Vertex Coloring Problem
		Exercise 27: Greedy Graph Coloring
		Activity 12: The Welsh-Powell Algorithm
	Summary
Chapter 6: Graph Algorithms I
	Introduction
	The Graph Traversal Problem
		Breadth-First Search
		Exercise 28: Implementing BFS
		Depth-First Search
		Exercise 29: Implementing DFS
		Activity 13: Finding out Whether a Graph is Bipartite Using DFS
	Prim\'s MST Algorithm
		Exercise 30: Prim\'s Algorithm
	Dijkstra\'s Shortest Path Algorithm
		Exercise 31: Implementing Dijkstra\'s Algorithm
		Activity 14: Shortest Path in New York
	Summary
Chapter 7: Graph Algorithms II
	Introduction
	Revisiting the Shortest Path Problem
	The Bellman-Ford Algorithm
		Exercise 32: Implementing the Bellman-Ford Algorithm (Part I)
	The Bellman-Ford Algorithm (Part II) – Negative Weight Cycles
		Exercise 33: Implementing the Bellman-Ford Algorithm (Part II)
		Activity 15: Greedy Robot
	Johnson\'s Algorithm
		Exercise 34: Implementing Johnson\'s Algorithm
		Activity 16: Randomized Graph Statistics
	Strongly Connected Components
		Connectivity in Directed and Undirected Graphs
	Kosaraju\'s Algorithm
		Exercise 35: Implementing Kosaraju\'s Algorithm
		Activity 17: Maze-Teleportation Game
	Choosing the Right Approach
	Summary
Chapter 8: Dynamic Programming I
	Introduction
	What Is Dynamic Programming?
	Memoization – The Top-Down Approach
	Tabulation – the Bottom-Up Approach
	Subset Sum Problem
		Solving the Subset Sum Problem – Step 1: Evaluating the Need for DP
		Step 2 – Defining the States and the Base Cases
		Step 2.a: Brute Force
		Exercise 36: Solving the Subset Sum Problem by Using the Brute-Force Approach
		Step 2.b: Optimizing Our Approach – Backtracking
		Exercise 37: Solving the Subset Sum Problem by Using Backtracking
		Step 3: Memoization
		Devising a Caching Scheme
		Exercise 38: Solving the Subset Sum Problem by Using Memoization
		Step 4: Tabulation
		Exercise 39: Solving the Subset Sum Problem by Using Tabulation
		Activity 18: Travel Itinerary
	Dynamic Programming on Strings and Sequences
		The Longest Common Subsequence Problem
		Exercise 40: Finding the Longest Common Subsequence by Using the Brute-Force Approach
		First Steps Toward Optimization – Finding the Optimal Substructure
		Activity 19: Finding the Longest Common Subsequence by Using Memoization
		From Top-Down to Bottom-Up – Converting the Memoized Approach into a Tabulated Approach
		Activity 20: Finding the Longest Common Subsequence Using Tabulation
	Activity 21: Melodic Permutations
	Summary
Chapter 9: Dynamic Programming II
	Introduction
	An Overview of P versus NP
	Reconsidering the Subset Sum Problem
	The Knapsack Problem
		0-1 Knapsack – Extending the Subset Sum Algorithm
		Exercise 41: 0-1 Knapsack Problem
		Unbounded Knapsack
		State Space Reduction
		Exercise 42: Unbounded Knapsack
		Activity 22: Maximizing Profit
	Graphs and Dynamic Programming
		Reconsidering the Bellman-Ford Algorithm
		Approaching the Shortest Path Problem as a DP Problem
		Exercise 43: Single-Source Shortest Paths (Memoization)
		All-Pairs Shortest Path
		The Floyd-Warshall Algorithm
		Exercise 44: Implementing the Floyd-Warshall Algorithm
		Activity 23: Residential Roads
	Summary
Appendix
Index