# Data Structure and Algorithm with C

(DS-ALGO-CPLUS.AP1)/ISBN:978-1-64459-444-5

This course includes
Lessons
TestPrep
Lab

Master data structures and algorithm analysis with the Data Structure and Algorithm with C++ course. Gain insight into efficient data handling, algorithmic analysis, and programming in C++. This course offers interactive lessons and hands-on labs, making complex algorithms and data structures accessible. Whether you're an advanced learner or a first-year graduate student, you'll enhance your programming skills and tackle real-world challenges with maximum efficiency.

### Lessons

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

### TestPrep

37+ Pre Assessment Questions | 37+ Post Assessment Questions |

## Here's what you will learn

### Lessons 1: Preface

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

### Lessons 2: Programming: A General Overview

• 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

• vector and list in the STL
• Implementation of vector
• Implementation of list
• 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
• 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

• Explicit Instantiation

## Hands-on LAB Activities (Performance Labs)

### 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