C++ Data Structures and Algorithm Design Principles

C++ Data Structures and Algorithm Design Principles

by John Carey, Shreyans Doshi, Payas Rajan
Released October 2019
Publisher(s): Packt Publishing
ISBN: 9781838828844

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Get started with C++ programming by learning how to build applications using its data structures and algorithms

Key Features

  • Explore data structures such as arrays, stacks, and graphs with real-world examples
  • Study the trade-offs between algorithms and data structures and discover what works and what doesn't
  • Discover how techniques such as bloom filters and multi-way heaps boost real-world applications

Book Description

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++.

This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book.

By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.

What you will learn

  • Build applications using hash tables, dictionaries, and sets
  • Explore how modern hardware affects the actual run-time performance of programs
  • Apply common algorithms such as heapsort and merge sort for string data types
  • Use C++ template metaprogramming to write code libraries
  • Implement a URL shortening service using a bloom filter
  • Use appropriate modern C++ idioms such as std:: array instead of C-style arrays

Who this book is for

This book is for developers or students who want to revisit basic data structures and algorithm design techniques. Although no mathematical background is required, basic knowledge of complexity classes and Big O notation along with a qualification in an algorithms course will help you get the most out of this book. Familiarity with C++ 14 standard is assumed.

Table of contents

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

Product information

  • Title: C++ Data Structures and Algorithm Design Principles
  • Author(s): John Carey, Shreyans Doshi, Payas Rajan
  • Release date: October 2019
  • Publisher(s): Packt Publishing
  • ISBN: 9781838828844