Problem Solving with Algorithms and Data Structures using C++

By Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College

• Assignments

• 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.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.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.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.13. Inheritance in C++
    • 1.13.1. Logic Gates and Circuits
    • 1.13.2. Building Circuits
  • 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.15. Summary
  • 1.16. Discussion Questions
  • 1.17. Programming Exercises
  • 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.3. Big-O Notation
  • 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.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
  • 2.14. Matching
• 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.9.1. Conversion of Infix Expressions to Prefix and Postfix
    • 3.9.2. General Infix-to-Postfix Conversion
    • 3.9.3. Postfix Evaluation
  • 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.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.19. Summary
  • 3.20. Discussion Questions
  • 3.21. Programming Exercises
  • 3.22. Glossary
  • 3.23. Matching
  • 3.24. 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.12. Matching
• 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
  • 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.4. The Binary Search
    • 6.4.1. Analysis of Binary Search
  • 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.6. Self Check
  • 6.7. Summary
  • 6.8. Discussion Questions
  • 6.9. Programming Exercises
  • 6.10. Glossary
  • 6.11. Matching
• 7. Sorting
  • 7.1. Objectives
  • 7.2. Sorting
  • 7.3. The Bubble Sort
  • 7.4. The Selection Sort
  • 7.5. The Insertion Sort
  • 7.6. The Shell Sort
  • 7.7. The Merge Sort
  • 7.8. The Quick Sort
  • 7.9. Self Check
  • 7.10. Summary
  • 7.11. Discussion Questions
  • 7.12. Programming Exercises
  • 7.13. Glossary
  • 7.14. Matching
• 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. 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.11. Binary Search Trees
  • 8.12. Search Tree Operations
  • 8.13. Search Tree Implementation
  • 8.14. Search Tree Analysis
  • 8.15. Balanced Binary Search Trees
  • 8.16. AVL Tree Performance
  • 8.17. AVL Tree Implementation
  • 8.18. Summary of Map ADT Implementations
  • 8.19. Summary
  • 8.20. Discussion Questions
  • 8.21. Programming Exercises
  • 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.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. Discussion Questions
  • 9.25. Programming Exercises
  • 9.26. Glossary
  • 9.27. Matching

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

• Index

• Module Index

• Search Page

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.

You have attempted of activities on this page