C++ Data Structures and Algorithm Design Principles by John Carey, Shreyans Doshi -- Read -- Imperial Library of Trantor

Index

Preface

About the Book

About the Authors Learning Objectives Audience Approach Hardware Requirements Software Requirements Installation and Setup Installing the Code Bundle Additional Resources

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

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

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

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

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

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

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

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

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

Chapter 1: Lists, Stacks, and Queues

Activity 1: Implementing a Song Playlist Activity 2: Simulating a Card Game Activity 3: Simulating a Queue for a Shared Printer in an Office

Chapter 2: Trees, Heaps, and Graphs

Activity 4: Create a Data Structure for a Filesystem Activity 5: K-Way Merge Using Heaps

Chapter 3: Hash Tables and Bloom Filters

Activity 6: Mapping Long URLs to Short URLs Activity 7: Email Address Validator

Chapter 4: Divide and Conquer

Activity 8: Vaccinations Activity 9: Partial Sorting Activity 10: Implementing WordCount in MapReduce

Chapter 5: Greedy Algorithms

Activity 11: The Interval Scheduling Problem Activity 12: The Welsh-Powell Algorithm

Chapter 6: Graph Algorithms I

Activity 13: Finding out Whether a Graph is Bipartite Using DFS Activity 14: Shortest Path in New York

Chapter 7: Graph Algorithms II

Activity 15: Greedy Robot Activity 16: Randomized Graph Statistics Activity 17: Maze-Teleportation Game

Chapter 8: Dynamic Programming I

Activity 18: Travel Itinerary Activity 19: Finding the Longest Common Subsequence by Using Memoization Activity 20: Finding the Longest Common Subsequence Using Tabulation Activity 21: Melodic Permutations

Chapter 9: Dynamic Programming II

Activity 22: Maximizing Profit Activity 23: Residential Roads

← Prev
Back
Next →

← Prev
Back
Next →