book

C++ Data Structures and Algorithm Design Principles

Name: C++ Data Structures and Algorithm Design Principles
ISBN: 9781838828844

by John Carey, Anil Achary, Shreyans Doshi, Payas Rajan

October 2019

Beginner to intermediate

626 pages

10h 31m

English

Packt Publishing

Read now

Unlock full access

Preface
About the BookAbout the AuthorsLearning ObjectivesAudienceApproachHardware RequirementsSoftware RequirementsInstallation and SetupInstalling the Code BundleAdditional Resources
1. Lists, Stacks, and Queues
IntroductionContiguous Versus Linked Data StructuresContiguous Data StructuresLinked Data StructuresComparisonLimitations of C-style Arraysstd::arrayExercise 1: Implementing a Dynamic Sized ArrayExercise 2: A General-Purpose and Fast Data Storage Container Builderstd::vectorstd::vector – Variable Length ArrayAllocators for std::vectorstd::forward_listInserting and Deleting Elements in forward_listOther Operations on forward_listExercise 3: Conditional Removal of Elements from a Linked List Using remove_if IteratorsExercise 4: Exploring Different Types of IteratorsExercise 5: Building a Basic Custom ContainerActivity 1: Implementing a Song Playliststd::listCommon Functions for std::listExercise 6: Insertion and Deletion Functions for std::listBidirectional IteratorsIterator Invalidation for Different ContainersActivity 2: Simulating a Card Gamestd::deque – Special Version of std::vectorThe Structure of DequeContainer Adaptorsstd::stackstd::queuestd::priority_queueIterators for AdaptorsBenchmarkingActivity 3: Simulating a Queue for a Shared Printer in an OfficeSummary
2. Trees, Heaps, and Graphs
IntroductionNon-Linear ProblemsHierarchical ProblemsCyclic DependenciesTree – It's Upside Down!Exercise 7: Creating an Organizational StructureTraversing TreesExercise 8: Demonstrating Level Order TraversalVariants of TreesBinary Search TreeTime Complexities of Operations on a TreeExercise 9: Implementing a Binary Search TreeBalanced TreeN-ary TreeActivity 4: Create a Data Structure for a FilesystemHeapsHeap OperationsExercise 10: Streaming MedianActivity 5: K-Way Merge Using HeapsGraphsRepresenting a Graph as an Adjacency MatrixExercise 11: Implementing a Graph and Representing it as an Adjacency MatrixRepresenting a Graph as an Adjacency ListExercise 12: Implementing a Graph and Representing it as an Adjacency ListSummary
3. Hash Tables and Bloom Filters
IntroductionHash TablesHashingExercise 13: Basic Dictionary for IntegersCollisions in Hash TablesClose Addressing – ChainingExercise 14: Hash Table with ChainingOpen AddressingPerfect Hashing – Cuckoo HashingExercise 15: Cuckoo HashingC++ Hash TablesExercise 16: Hash Tables Provided by STLActivity 6: Mapping Long URLs to Short URLsBloom FiltersExercise 17: Creating Bloom FiltersActivity 7: Email Address ValidatorSummary
4. Divide and Conquer
IntroductionBinary SearchExercise 18: Binary Search BenchmarksActivity 8: VaccinationsUnderstanding the Divide-and-Conquer ApproachSorting Using Divide and ConquerMerge SortExercise 19: Merge SortQuicksortExercise 20: QuicksortActivity 9: Partial SortingLinear Time SelectionExercise 21: Linear Time SelectionC++ Standard Library Tools for Divide and ConquerDividing and Conquering at a Higher Abstraction Level – MapReduceThe Map and Reduce AbstractionsExercise 22: Map and Reduce in the C++ Standard LibraryIntegrating the Parts – Using a MapReduce FrameworkExercise 23: Checking Primes Using MapReduceActivity 10: Implementing WordCount in MapReduce Summary
5. Greedy Algorithms
IntroductionBasic Greedy AlgorithmsShortest-Job-First SchedulingExercise 24: Shortest-Job-First SchedulingThe Knapsack Problem(s)The Knapsack ProblemThe Fractional Knapsack ProblemExercise 25: Fractional Knapsack ProblemActivity 11: The Interval Scheduling ProblemRequirements for Greedy AlgorithmsThe Minimum Spanning Tree (MST) ProblemDisjoint-Set (or Union-Find) Data StructuresExercise 26: Kruskal's MST AlgorithmThe Vertex Coloring ProblemExercise 27: Greedy Graph ColoringActivity 12: The Welsh-Powell AlgorithmSummary
6. Graph Algorithms I
IntroductionThe Graph Traversal ProblemBreadth-First SearchExercise 28: Implementing BFSDepth-First SearchExercise 29: Implementing DFSActivity 13: Finding out Whether a Graph is Bipartite Using DFSPrim's MST AlgorithmExercise 30: Prim's AlgorithmDijkstra's Shortest Path AlgorithmExercise 31: Implementing Dijkstra's AlgorithmActivity 14: Shortest Path in New YorkSummary
7. Graph Algorithms II
IntroductionRevisiting the Shortest Path ProblemThe Bellman-Ford AlgorithmExercise 32: Implementing the Bellman-Ford Algorithm (Part I)The Bellman-Ford Algorithm (Part II) – Negative Weight CyclesExercise 33: Implementing the Bellman-Ford Algorithm (Part II)Activity 15: Greedy RobotJohnson's AlgorithmExercise 34: Implementing Johnson's AlgorithmActivity 16: Randomized Graph StatisticsStrongly Connected ComponentsConnectivity in Directed and Undirected GraphsKosaraju's AlgorithmExercise 35: Implementing Kosaraju's AlgorithmActivity 17: Maze-Teleportation GameChoosing the Right ApproachSummary
8. Dynamic Programming I
IntroductionWhat Is Dynamic Programming?Memoization – The Top-Down ApproachTabulation – the Bottom-Up ApproachSubset Sum ProblemSolving the Subset Sum Problem – Step 1: Evaluating the Need for DPStep 2 – Defining the States and the Base CasesStep 2.a: Brute ForceExercise 36: Solving the Subset Sum Problem by Using the Brute-Force ApproachStep 2.b: Optimizing Our Approach – BacktrackingExercise 37: Solving the Subset Sum Problem by Using BacktrackingStep 3: MemoizationDevising a Caching SchemeExercise 38: Solving the Subset Sum Problem by Using MemoizationStep 4: TabulationExercise 39: Solving the Subset Sum Problem by Using TabulationActivity 18: Travel ItineraryDynamic Programming on Strings and SequencesThe Longest Common Subsequence ProblemExercise 40: Finding the Longest Common Subsequence by Using the Brute-Force ApproachFirst Steps Toward Optimization – Finding the Optimal SubstructureActivity 19: Finding the Longest Common Subsequence by Using MemoizationFrom Top-Down to Bottom-Up – Converting the Memoized Approach into a Tabulated ApproachActivity 20: Finding the Longest Common Subsequence Using TabulationActivity 21: Melodic PermutationsSummary
9. Dynamic Programming II
IntroductionAn Overview of P versus NPReconsidering the Subset Sum ProblemThe Knapsack Problem0-1 Knapsack – Extending the Subset Sum AlgorithmExercise 41: 0-1 Knapsack ProblemUnbounded KnapsackState Space ReductionExercise 42: Unbounded KnapsackActivity 22: Maximizing ProfitGraphs and Dynamic ProgrammingReconsidering the Bellman-Ford AlgorithmApproaching the Shortest Path Problem as a DP ProblemExercise 43: Single-Source Shortest Paths (Memoization)All-Pairs Shortest PathThe Floyd-Warshall AlgorithmExercise 44: Implementing the Floyd-Warshall AlgorithmActivity 23: Residential RoadsSummary

Appendix
Chapter 1: Lists, Stacks, and QueuesActivity 1: Implementing a Song PlaylistActivity 2: Simulating a Card GameActivity 3: Simulating a Queue for a Shared Printer in an OfficeChapter 2: Trees, Heaps, and GraphsActivity 4: Create a Data Structure for a FilesystemActivity 5: K-Way Merge Using HeapsChapter 3: Hash Tables and Bloom FiltersActivity 6: Mapping Long URLs to Short URLsActivity 7: Email Address ValidatorChapter 4: Divide and ConquerActivity 8: VaccinationsActivity 9: Partial SortingActivity 10: Implementing WordCount in MapReduceChapter 5: Greedy AlgorithmsActivity 11: The Interval Scheduling ProblemActivity 12: The Welsh-Powell AlgorithmChapter 6: Graph Algorithms IActivity 13: Finding out Whether a Graph is Bipartite Using DFSActivity 14: Shortest Path in New YorkChapter 7: Graph Algorithms IIActivity 15: Greedy RobotActivity 16: Randomized Graph StatisticsActivity 17: Maze-Teleportation GameChapter 8: Dynamic Programming IActivity 18: Travel ItineraryActivity 19: Finding the Longest Common Subsequence by Using MemoizationActivity 20: Finding the Longest Common Subsequence Using TabulationActivity 21: Melodic PermutationsChapter 9: Dynamic Programming IIActivity 22: Maximizing ProfitActivity 23: Residential Roads

Content preview from C++ Data Structures and Algorithm Design Principles

5. Greedy Algorithms

Learning Objectives

By the end of this chapter, you will be able to:

Describe the greedy approach to algorithm design
Identify the optimal substructure and greedy choice properties of a problem
Implement greedy algorithms such as fractional knapsack and greedy graph coloring
Implement Kruskal's Minimum Spanning Tree algorithm using a disjoint-set data structure

In this chapter, we will look at various 'greedy' approaches to algorithm design and see how they can be applied in order to solve real-world problems.

Introduction

In the previous chapter, we discussed the divide-and-conquer algorithm design technique, which solves a given problem by dividing the input into smaller subproblems, solving each subproblem, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Data Structures and Algorithms Using C++

Publisher Resources

ISBN: 9781838828844

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design