Data Structure and Algorithm with C++

Lessons

14+ Lessons | 125+ Exercises | 56+ Quizzes | 53+ Flashcards | 53+ Glossary of terms

TestPrep

38+ Pre Assessment Questions | 36+ Post Assessment Questions |

Lessons 1: Preface

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

Lessons 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

Lessons 3: Algorithm Analysis

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

Lessons 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

Lessons 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

Lessons 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

Lessons 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

Lessons 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

Lessons 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

Lessons 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

Lessons 11: Algorithm Design Techniques

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

Lessons 12: Amortized Analysis

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

Lessons 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

Appendix A: Separate Compilation of Class Templates

• Everything in the Header
• Explicit Instantiation

Hands-on LAB Activities (Performance Labs)

Programming: A General Overview

• Using Recursive Function
• Resizing a Matrix

Algorithm Analysis

• Finding Minimum Subsequence Sum
• Implementing the Bisection Method
• 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