Skip to main content
Problem Solving with Algorithms and Data Structures using C++
The PreTeXt Interactive Edition
Contents
Index
Search Book
close
Search Results:
No results.
dark_mode
Dark Mode
Prev
Up
Next
Scratch ActiveCode
Profile
Course Home
Assignments
Practice
Peer Instruction (Instructor)
Peer Instruction (Student)
Change Course
Instructor's Page
Progress Page
Edit Profile
Change Password
Log Out
1
Introduction
1.1
Objectives
1.2
Getting Started
1.3
What Is Computer Science?
1.4
What Is Programming?
1.5
Why Study Data Structures and Abstract Data Types?
1.6
Why Study Algorithms?
1.7
Reviewing Basic C++
1.8
Getting Started with Data
1.9
Built-in Atomic Data Types
1.9.1
Numeric Data
1.9.2
Boolean Data
1.9.3
Character Data
1.9.4
Pointers
1.9.4.1
Pointer Syntax
1.9.4.2
The address-of operator,
&
1.9.4.3
Accessing Values from Pointers
1.9.4.4
The null pointer
1.10
Collections
1.10.1
Arrays
1.10.2
Vectors
1.10.3
Strings
1.10.4
Hash Tables
1.10.5
Unordered Sets
1.10.5
Reading Questions
1.11
Defining C++ Functions
1.11.1
Parameter Passing: by Value versus by Reference
1.11.2
Arrays as Parameters in Functions
1.11.3
Function Overloading
1.11.3
Reading Questions
1.12
Object-Oriented Programming in C++: Defining Classes
1.12.1
A
Fraction
Class
1.12.2
Abstraction and Encapsulation
1.12.3
Polymorphism
1.12.4
Self-Check
1.12.4
Reading Questions
1.13
Inheritance in C++
1.13.1
Logic Gates and Circuits
1.13.2
Building Circuits
1.13.2
Reading Questions
1.13.3
Self Check Challenge
1.14
Optional
: Graphics in C++
1.14.1
Introduction to Turtles
1.14.2
Turtle & TurtleScreen
1.14.3
Geometry, Shapes, and Stamps
1.14.4
Advanced Features
1.14.4
Reading Questions
1.15
Summary
1.16
Discussion Questions
1.17
Programming Exercises
1.18
Glossary
1.18
Glossary
1.19
Matching
2
Analysis
2.1
Objectives
2.2
What Is Algorithm Analysis?
2.2.1
Some Needed Math Notation
2.2.2
Applying the Math Notation
2.2.2
Reading Questions
2.3
Big-O Notation
2.3
Reading Questions
2.4
An Anagram Detection Example
2.4.1
Solution 1: Checking Off
2.4.2
Solution 2: Sort and Compare
2.4.3
Solution 3: Brute Force
2.4.4
Solution 4: Count and Compare
2.4.4
Reading Questions
2.5
Performance of C++ Data Collections
2.6
Analysis of Array and Vector Operators
2.6
Reading Question
2.7
Analysis of String Operators
2.8
Analysis of Hash Tables
2.8
Reading Questions
2.9
Summary
2.10
Self Check
2.11
Discussion Questions
2.12
Programming Exercises
2.13
Glossary
2.13
Glossary
2.14
Matching
3
Linear Structures
3.1
Objectives
3.2
What Are Linear Structures?
3.3
What is a Stack?
3.3
Reading Question
3.4
The Stack Abstract Data Type
3.4
Reading Question
3.5
Using a Stack in C++
3.5
Reading Questions
3.6
Simple Balanced Parentheses
3.7
Balanced Symbols - A General Case
3.7
Reading Question
3.8
Converting Decimal Numbers to Binary Numbers
3.8
Reading Questions
3.9
Infix, Prefix and Postfix Expressions
3.9.1
Conversion of Infix Expressions to Prefix and Postfix
3.9.2
General Infix-to-Postfix Conversion
3.9.3
Postfix Evaluation
3.9.3
Reading Questions
3.10
What Is a Queue?
3.11
The Queue Abstract Data Type
3.12
Using a Queue in C++
3.12
Reading Question
3.13
Simulation: Hot Potato
3.14
Simulation: Printing Tasks
3.14.1
Main Simulation Steps
3.14.2
C++ Implementation
3.14.3
Discussion
3.15
What Is a Deque?
3.16
The Deque Abstract Data Type
3.17
Using a Deque in C++
3.18
Palindrome-Checker
3.18
Reading Questions
3.19
Summary
3.20
Discussion Questions
3.21
Programming Exercises
3.22
Glossary
3.22
Glossary
3.23
Matching
4
Linear Linked Structures
4.1
Objectives
4.2
What Are Linked Structures?
4.3
Implementing an Unordered Linked List
4.4
The
Node
Class
4.5
The
Unordered Linked List
Class
4.6
Implementing an Ordered Linked List
4.6.1
Analysis of Linked Lists
4.7
The Ordered List Abstract Data Type
4.7.1
Forward lists
4.7.2
Lists
4.8
Summary
4.9
Discussion Questions
4.10
Programming Exercises
4.11
Glossary
4.11
Glossary
5
Recursion
5.1
Objectives
5.2
What Is Recursion?
5.3
Calculating the Sum of a Vector of Numbers
5.4
The Three Laws of Recursion
5.4
Reading Questions
5.5
Converting an Integer to a String in Any Base
5.5
Reading Questions
5.6
Stack Frames: Implementing Recursion
5.7
Introduction: Visualizing Recursion
5.7
Reading Questions
5.8
Sierpinski Triangle
5.9
Complex Recursive Problems
5.10
Tower of Hanoi
5.10
Reading Questions
5.11
Exploring a Maze
5.12
Dynamic Programming
5.13
Summary
5.14
Self-check
5.15
Discussion Questions
5.16
Programming Exercises
5.17
Glossary
5.17
Glossary
5.18
Matching
6
Searching and Hashing
6.1
Objectives
6.2
Searching
6.3
The Sequential Search
6.3.1
Analysis of Sequential Search
6.3.1
Reading Questions
6.4
The Binary Search
6.4.1
Analysis of Binary Search
6.4.1
Reading Questions
6.5
Hashing
6.5.1
Hash Functions
6.5.2
Collision Resolution
6.5.3
Implementing the
Map
Abstract Data Type
6.5.4
Analysis of Hashing
6.5.4
Reading Questions
6.6
Self Check
6.7
Summary
6.8
Discussion Questions
6.9
Programming Exercises
6.10
Glossary
6.10
Glossary
6.11
Matching
7
Sorting
7.1
Objectives
7.2
Sorting
7.3
The Bubble Sort
7.3
Reading Questions
7.4
The Selection Sort
7.4
Reading Questions
7.5
The Insertion Sort
7.5
Reading Questions
7.6
The Shell Sort
7.6
Reading Questions
7.7
The Merge Sort
7.7
Reading Questions
7.8
The Quick Sort
7.8
Reading Questions
7.9
Self Check
7.10
Summary
7.11
Discussion Questions
7.12
Programming Exercises
7.13
Glossary
7.13
Glossary
7.14
Matching
8
Trees and Tree Algorithms
8.1
Objectives
8.2
Examples of Trees
8.2
Reading Question
8.3
Vocabulary and Definitions
8.3
Reading Question
8.4
Nodes and References
8.4
Reading Question
8.5
Parse Tree
8.5
Reading Question
8.6
Tree Traversals
8.6
Reading Questions
8.7
Priority Queues with Binary Heaps
8.8
Priority Queues with Binary Heaps Example
8.9
Binary Heap Operations
8.10
Binary Heap Implementation
8.10.1
The Structure Property
8.10.2
The Heap Order Property
8.10.3
Heap Operations
8.10.3
Reading Question
8.11
Binary Search Trees
8.12
Search Tree Operations
8.13
Search Tree Implementation
8.13
Reading Questions
8.14
Search Tree Analysis
8.14
Reading Question
8.15
Balanced Binary Search Trees
8.16
AVL Tree Performance
8.17
AVL Tree Implementation
8.17
Reading Question
8.18
Summary of Map ADT Implementations
8.19
Summary
8.20
Discussion Questions
8.21
Programming Exercises
8.22
Glossary
8.22
Glossary
8.23
Matching
9
Graphs and Graph Algorithms
9.1
Objectives
9.2
Vocabulary and Definitions
9.3
The Graph Abstract Data Type
9.3
Reading Question
9.4
An Adjacency Matrix
9.5
An Adjacency List
9.6
Implementation
9.7
The Word Ladder Problem
9.8
Building the Word Ladder Graph
9.9
Implementing Breadth First Search
9.10
Breadth First Search Analysis
9.11
The Knight’s Tour Problem
9.12
Building the Knight’s Tour Graph
9.13
Implementing Knight’s Tour
9.13
Reading Questions
9.14
Knight’s Tour Analysis
9.14
Reading Question
9.15
General Depth First Search
9.16
Depth First Search Analysis
9.17
Topological Sorting
9.18
Strongly Connected Components
9.19
Shortest Path Problems
9.20
Dijkstra’s Algorithm
9.20
Reading Question
9.21
Analysis of Dijkstra’s Algorithm
9.22
Prim’s Spanning Tree Algorithm
9.22
Reading Question
9.23
Summary
9.24
Discussion Questions
9.25
Programming Exercises
9.26
Glossary
9.26
Glossary
9.27
Matching
Back Matter
Index
Section
6.7
Summary
A sequential search is
O
(
n
)
for ordered and unordered lists.
🔗
🔗
A binary search of an ordered list is
O
(
log
n
)
in the worst case.
🔗
🔗
Hash tables can provide constant time searching.
🔗
🔗
🔗
🔗
You have attempted
1
of
1
activities on this page.
🔗
