uCertify

Data Structure and Algorithm with C

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

This course includes
Lessons
TestPrep
Lab
Data Structure and Algorithm with C

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 |

Need guidance and support? Click here to check our Instructor Led Course.

Here's what you will learn

Download Course Outline

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

  • 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