Browse Library
Sign In Start Free Trial
Close icon Search icon
Account
Browse Library Advanced Search Sign In Start Free Trial

Add to playlist

Create a Playlist

Modal Close icon
You need to login to use this feature.
  • Book Overview & Buying C++ Data Structures and Algorithm Design Principles
  • Table Of Contents Toc
  • Feedback & Rating feedback
C++ Data Structures and Algorithm Design Principles

C++ Data Structures and Algorithm Design Principles

By : John Carey, Anil Achary, Shreyans Doshi, Payas Rajan
2.3 (4)
Buy this Book
close
close
C++ Data Structures and Algorithm Design Principles

C++ Data Structures and Algorithm Design Principles

2.3 (4)
By: John Carey, Anil Achary, Shreyans Doshi, Payas Rajan
Buy this Book

Overview of this book

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.
Table of Contents (11 chapters)
close
close
close
About the Book
Icon
About the Book
Icon
About the Authors
Icon
Learning Objectives
Icon
Audience
Icon
Approach
Icon
Hardware Requirements
Icon
Software Requirements
Icon
Installation and Setup
Icon
Installing the Code Bundle
Icon
Additional Resources
Lock Free Chapter
1
1. Lists, Stacks, and Queues
Icon
1. Lists, Stacks, and Queues
Icon
Introduction
Icon
Contiguous Versus Linked Data Structures
Icon
std::array
Icon
std::vector
Icon
std::forward_list
Icon
Iterators
Icon
std::list
Icon
std::deque – Special Version of std::vector
Icon
Container Adaptors
Icon
Benchmarking
Icon
Summary
2
2. Trees, Heaps, and Graphs
Icon
2. Trees, Heaps, and Graphs
Icon
Introduction
Icon
Non-Linear Problems
Icon
Tree – It's Upside Down!
Icon
Variants of Trees
Icon
Heaps
Icon
Graphs
Icon
Summary
3
3. Hash Tables and Bloom Filters
Icon
3. Hash Tables and Bloom Filters
Icon
Introduction
Icon
Hash Tables
Icon
Collisions in Hash Tables
Icon
C++ Hash Tables
Icon
Bloom Filters
Icon
Summary
4
4. Divide and Conquer
Icon
4. Divide and Conquer
Icon
Introduction
Icon
Binary Search
Icon
Understanding the Divide-and-Conquer Approach
Icon
Sorting Using Divide and Conquer
Icon
C++ Standard Library Tools for Divide and Conquer
Icon
Dividing and Conquering at a Higher Abstraction Level – MapReduce
Icon
Summary
5
5. Greedy Algorithms
Icon
5. Greedy Algorithms
Icon
Introduction
Icon
Basic Greedy Algorithms
Icon
The Knapsack Problem(s)
Icon
The Vertex Coloring Problem
Icon
Summary
6
6. Graph Algorithms I
Icon
6. Graph Algorithms I
Icon
Introduction
Icon
The Graph Traversal Problem
Icon
Prim's MST Algorithm
Icon
Dijkstra's Shortest Path Algorithm
Icon
Summary
7
7. Graph Algorithms II
chevron up
Icon
7. Graph Algorithms II
Icon
Introduction
Icon
Revisiting the Shortest Path Problem
Icon
The Bellman-Ford Algorithm
Icon
The Bellman-Ford Algorithm (Part II) – Negative Weight Cycles
Icon
Johnson's Algorithm
Icon
Strongly Connected Components
Icon
Kosaraju's Algorithm
Icon
Choosing the Right Approach
Icon
Summary
8
8. Dynamic Programming I
Icon
8. Dynamic Programming I
Icon
Introduction
Icon
What Is Dynamic Programming?
Icon
Memoization – The Top-Down Approach
Icon
Tabulation – the Bottom-Up Approach
Icon
Subset Sum Problem
Icon
Dynamic Programming on Strings and Sequences
Icon
Activity 21: Melodic Permutations
Icon
Summary
9
9. Dynamic Programming II
Icon
9. Dynamic Programming II
Icon
Introduction
Icon
An Overview of P versus NP
Icon
Reconsidering the Subset Sum Problem
Icon
The Knapsack Problem
Icon
Graphs and Dynamic Programming
Icon
Summary
1
Appendix
Icon
Appendix
Icon
Chapter 1: Lists, Stacks, and Queues
Icon
Chapter 2: Trees, Heaps, and Graphs
Icon
Chapter 3: Hash Tables and Bloom Filters
Icon
Chapter 4: Divide and Conquer
Icon
Chapter 5: Greedy Algorithms
Icon
Chapter 6: Graph Algorithms I
Icon
Chapter 7: Graph Algorithms II
Icon
Chapter 8: Dynamic Programming I
Icon
Chapter 9: Dynamic Programming II

Johnson's Algorithm

Having compared the relative merits and disadvantages of the Bellman-Ford algorithm and Dijkstra's algorithm, we will now discuss an algorithm that combines both of them to retrieve the shortest paths between every pair of vertices in a graph. Johnson's algorithm provides us with the advantage of being able to utilize the efficiency of Dijkstra's algorithm while still producing correct results for graphs with negative edge weights.

The concept behind Johnson's algorithm is quite novel – to contend with Dijkstra's limitations when dealing with negative weights, Johnson's algorithm simply reweights the edges in the graph so they are uniformly non-negative. This is accomplished with the rather creative use of Bellman-Ford combined with some particularly elegant mathematical logic.

The first step in Johnson's algorithm is to add a new 'dummy' vertex to the graph, which is subsequently connected to every other vertex...

Visually different images
CONTINUE READING
83
Tech Concepts
36
Programming languages
73
Tech Tools
Icon Unlimited access to the largest independent learning library in tech of over 8,000 expert-authored tech books and videos.
Icon Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.
Icon 50+ new titles added per month and exclusive early access to books as they are being written.
C++ Data Structures and Algorithm Design Principles
End of Section 7
Next Section
notes
bookmark Notes and Bookmarks search Search in title playlist Add to playlist font-size Font size

Change the font size

margin-width Margin width

Change margin width

day-mode Day/Sepia/Night Modes

Change background colour

Close icon Search
Country selected
Close icon Your notes and bookmarks

Confirmation

Modal Close icon
claim successful
Order Page Read Now

Buy this book with your credits?

Modal Close icon
Are you sure you want to buy this book with one of your credits?
Close
YES, BUY

Submit Your Feedback

Modal Close icon
Modal Close icon
Modal Close icon