Problem Solving with Algorithms and Data Structures using C++¶
By Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College
- 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.10. Collections
- 1.11. Defining C++ Functions
- 1.12. Object-Oriented Programming in C++: Defining Classes
- 1.13. Inheritance in C++
- 1.14. Summary
- 1.15. Discussion Questions
- 1.16. Programming Exercises
- 1.17. Glossary
- 2. Analysis
- 2.1. Objectives
- 2.2. What Is Algorithm Analysis?
- 2.3. Big-O Notation
- 2.4. An Anagram Detection Example
- 2.5. Performance of C++ Data Collections
- 2.6. Analysis of Array and Vector Operators
- 2.7. Analysis of String Operators
- 2.8. Analysis of Hash Tables
- 2.9. Summary
- 2.10. Self Check
- 2.11. Discussion Questions
- 2.12. Programming Exercises
- 2.13. Glossary
- 3. Linear Structures
- 3.1. Objectives
- 3.2. What Are Linear Structures?
- 3.3. What is a Stack?
- 3.4. The Stack Abstract Data Type
- 3.5. Using a Stack in C++
- 3.6. Simple Balanced Parentheses
- 3.7. Balanced Symbols - A General Case
- 3.8. Converting Decimal Numbers to Binary Numbers
- 3.9. Infix, Prefix and Postfix Expressions
- 3.10. What Is a Queue?
- 3.11. The Queue Abstract Data Type
- 3.12. Using a Queue in C++
- 3.13. Simulation: Hot Potato
- 3.14. Simulation: Printing Tasks
- 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.19. Summary
- 3.20. Discussion Questions
- 3.21. Programming Exercises
- 3.22. Glossary
- 4. Linear Linked Structures
- 4.1. Objectives
- 4.2. What Are Linked Structures?
- 4.3. Implementing an Unordered Linked List
- 4.4. The
NodeClass - 4.5. The
Unordered Linked ListClass - 4.6. Implementing an Ordered Linked List
- 4.7. The Ordered List Abstract Data Type
- 4.8. Summary
- 4.9. Discussion Questions
- 4.10. Programming Exercises
- 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.5. Converting an Integer to a String in Any Base
- 5.6. Stack Frames: Implementing Recursion
- 5.7. Introduction: Visualizing Recursion
- 5.8. Sierpinski Triangle
- 5.9. Complex Recursive Problems
- 5.10. Tower of Hanoi
- 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
- 6. Searching and Hashing
- 7. Sorting
- 8. Trees and Tree Algorithms
- 8.1. Objectives
- 8.2. Examples of Trees
- 8.3. Vocabulary and Definitions
- 8.4. Nodes and References
- 8.5. Parse Tree
- 8.6. Tree Traversals
- 8.7. Priority Queues with Binary Heaps
- 8.8. Binary Heap Operations
- 8.9. Binary Heap Implementation
- 8.10. Binary Search Trees
- 8.11. Search Tree Operations
- 8.12. Search Tree Implementation
- 8.13. Search Tree Analysis
- 8.14. Balanced Binary Search Trees
- 8.15. AVL Tree Performance
- 8.16. AVL Tree Implementation
- 8.17. Summary of Map ADT Implementations
- 8.18. Summary
- 8.19. Discussion Questions
- 8.20. Programming Exercises
- 8.21. Glossary
- 9. Graphs and Graph Algorithms
- 9.1. Objectives
- 9.2. Vocabulary and Definitions
- 9.3. The Graph Abstract Data Type
- 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.14. Knight’s Tour Analysis
- 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.21. Analysis of Dijkstra’s Algorithm
- 9.22. Prim’s Spanning Tree Algorithm
- 9.23. Summary
- 9.24. Key Terms
- 9.25. Discussion Questions
- 9.26. Programming Exercises
Acknowledgements¶
We are very grateful to Franklin Beedle Publishers for allowing us to make the original Python version of this interactive textbook freely available. The original online version was dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”
Indices and tables¶
Problem Solving with Algorithms and Data Structures using C++ by Bradley N. Miller, David L. Ranum, and Janice L. Pearce is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.