Data Structure and Algorithm with C++

Master your coding skills with C++ programming for Data Structures. Get ready to ace those technical rounds of job interviews.

(DS-ALGO-CPLUS.AP1) / ISBN : 978-1-64459-444-5
This course includes
Interactive Lessons
Gamified TestPrep
Lab
Get A Free Trial

About This Course

The Data Structure and Algorithm with C++ course offers a comprehensive learning of the advanced topics along with a rich collection of practice exercises for deeper understanding. Besides learning the fundamentals of basic data structures like arrays, linked lists, stacks, and queues, you’ll also be working with advanced data structures trees (binary, binary search, AVL, and heap), graphs, and hash tables. Learn how to measure the efficiency of an algorithm using time(how long it takes) and space(space/memory) complexity metrics. For the practical implications, you’ll be sorting algorithms (bubble, insertion, selection, merge, quick, heap) and searching techniques (linear, binary). The course further extends to dynamic programming, greedy algorithms, and advanced tree structures like B-trees. Get access to the C++ Standard Template Library (STL) that features containers (vector, list, deque, stack, queue, priority queue, map, set) and iterators. The course includes exercises and solutions that are useful for both students and professionals. It aims to help you prepare for technical job interviews that typically involve coding questions.

Skills You’ll Get

  • Implementing various data structures including arrays, linked lists, stacks, queues, trees, graphs, and hash tables
  • Optimizing algorithms through time and space complexities
  • Enhanced problem-solving skills
  • Sorting, searching, and computing via algorithms
  • Enhanced C++ programming skills
  • Using the Standard Template Library (STL)
  • Gain confidence to answer coding questions during technical interviews
  • Applying data structures and algorithms for analytical thinking.

1

Preface

  • Purpose/Goals
  • Approach
  • Summary of the Most Significant Changes in the Fourth Edition
  • Overview
  • Exercises
2

Programming: A General Overview

  • What’s This Course About?
  • Mathematics Review
  • A Brief Introduction to Recursion
  • C++ Classes
  • C++ Details
  • Templates
  • Using Matrices
  • Summary
  • Exercises
  • References
3

Algorithm Analysis

  • Mathematical Background
  • Model
  • What to Analyze
  • Running-Time Calculations
  • Summary
  • Exercises
  • References
4

Lists, Stacks, and Queues

  • Abstract Data Types (ADTs)
  • The List ADT
  • vector and list in the STL
  • Implementation of vector
  • Implementation of list
  • The Stack ADT
  • The Queue ADT
  • Summary
  • Exercises
5

Trees

  • Preliminaries
  • Binary Trees
  • The Search Tree ADT—Binary Search Trees
  • AVL Trees
  • Splay Trees
  • Tree Traversals (Revisited)
  • B-Trees
  • Sets and Maps in the Standard Library
  • Summary
  • Exercises
  • References
6

Hashing

  • General Idea
  • Hash Function
  • Separate Chaining
  • Hash Tables without Linked Lists
  • Rehashing
  • Hash Tables in the Standard Library
  • Hash Tables with Worst-Case O(1) Access
  • Universal Hashing
  • Extendible Hashing
  • Summary
  • Exercises
  • References
7

Priority Queues (Heaps)

  • Model
  • Simple Implementations
  • Binary Heap
  • Applications of Priority Queues
  • d-Heaps
  • Leftist Heaps
  • Skew Heaps
  • Binomial Queues
  • Priority Queues in the Standard Library
  • Summary
  • Exercises
  • References
8

Sorting

  • Preliminaries
  • Insertion Sort
  • A Lower Bound for Simple Sorting Algorithms
  • Shellsort
  • Heapsort
  • Mergesort
  • Quicksort
  • A General Lower Bound for Sorting
  • Decision-Tree Lower Bounds for Selection Problems
  • Adversary Lower Bounds
  • Linear-Time Sorts: Bucket Sort and Radix Sort
  • External Sorting
  • Summary
  • Exercises
  • References
9

The Disjoint Sets Class

  • Equivalence Relations
  • The Dynamic Equivalence Problem
  • Basic Data Structure
  • Smart Union Algorithms
  • Path Compression
  • Worst Case for Union-by-Rank and Path Compression
  • An Application
  • Summary
  • Exercises
  • References
10

Graph Algorithms

  • Definitions
  • Topological Sort
  • Shortest-Path Algorithms
  • Network Flow Problems
  • Minimum Spanning Tree
  • Applications of Depth-First Search
  • Introduction to NP-Completeness
  • Summary
  • Exercises
  • References
11

Algorithm Design Techniques

  • Greedy Algorithms
  • Divide and Conquer
  • Dynamic Programming
  • Randomized Algorithms
  • Backtracking Algorithms
  • Summary
  • Exercises
  • References
12

Amortized Analysis

  • An Unrelated Puzzle
  • Binomial Queues
  • Skew Heaps
  • Fibonacci Heaps
  • Splay Trees
  • Summary
  • Exercises
  • References
13

Advanced Data Structures and Implementation

  • Top-Down Splay Trees
  • Red-Black Trees
  • Treaps
  • Suffix Arrays and Suffix Trees
  • k-d Trees
  • Pairing Heaps
  • Summary
  • Exercises
  • References
A

Appendix A: Separate Compilation of Class Templates

  • Everything in the Header
  • Explicit Instantiation

Programming: A General Overview

  • Using Recursive Function
  • Resizing a Matrix

Algorithm Analysis

  • Implementing the Bisection Method
  • Finding Minimum Subsequence Sum
  • Implementing Binary Search

Lists, Stacks, and Queues

  • Implementing the STL find Routine
  • Working with Lists
  • Converting an Infix Expression to Postfix
  • Checking for Balancing Brackets
  • Reversing a Singly Linked List
  • Implementing a Stack Class
  • Implementing a Dequeue using a Linked List

Trees

  • Implementing a Depth-First Traversal in the Child-Sibling Tree
  • Converting a Tree into Graph-Assembler Instructions
  • Using the findMax Function
  • Generating an AVL Tree
  • Inserting a Node into an AVL Tree
  • Implementing a Splay Tree
  • Working with Binary Tree
  • Implementing a B-Tree
  • Inserting Keys into the B-Tree
  • Implementing the map Class
  • Implementing a Splay Tree

Hashing

  • Counting Number of Collisions
  • Implementing Hopscotch Hashing
  • Implementing Cuckoo Hashing
  • Implementing Extendible Hashing

Priority Queues (Heaps)

  • Merging Two Max Heaps
  • Implementing Insert Operation in a Binomial Queue

Sorting

  • Implementing Insertion Sort using STL
  • Implementing Mergesort without Recursion
  • Implementing the Selection Sort Algorithm

The Disjoint Sets Class

  • Printing a Maze

Graph Algorithms

  • Implementing a Topological Sorting Algorithm
  • Solving a Single Source Shortest Path Problem
  • Implementing Union Function in Kruskal's Algorithm

Algorithm Design Techniques

  • Solving the Longest Common Subsequence Problem

Any questions?
Check out the FAQs

Still have unanswered questions and need to get in touch?

Contact Us Now

Data structure refers to the organization and arrangement of data in an IT setup whereas Algorithm is the step-by-step process of using this stored data for desired results. Deep understanding of both the concepts will enable you to write efficient, scalable, and well-structured C++ programs.

Yes, with C++ you can access the standard template library (STL) that facilitates the creation and manipulation of complex data structures.

This would typically depend on the type of data, operations, memory constraints, and time complexity. Once you have an understanding of these factors, you can choose the most appropriate data set for your application.

It will improve your problem-solving skills and enhance your C++ programming skills. With a solid foundation in DSA you’ll be able to crack the coding job interviews with ease and confidently place yourself in high-paid jobs.

Essential Algorithms: A practical Approach to Computer Algorithms Using Python and C#. It teaches you how to write codes in both the programming languages.

Related Courses

All Course
scroll to top