uCertify

Data Structure and Algorithm with C++

(DS-ALGO-CPLUS.AP1.E0T)
Lessons
TestPrep
Get A Free Trial

Skills You’ll Get

Download Course Outline

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

Related Courses

All Courses