Problem Solving with Algorithms and Data Structures using Python

By Brad Miller and David Ranum, Luther College

• Assignments

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.

• 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. Review of Basic Python
  • 1.8. Getting Started with Data
    • 1.8.1. Built-in Atomic Data Types
    • 1.8.2. Built-in Collection Data Types
  • 1.9. Input and Output
    • 1.9.1. String Formatting
  • 1.10. Control Structures
  • 1.11. Exception Handling
  • 1.12. Defining Functions
  • 1.13. Object-Oriented Programming in Python: Defining Classes
    • 1.13.1. A Fraction Class
    • 1.13.2. Inheritance: Logic Gates and Circuits
  • 1.14. Summary
  • 1.15. Key Terms
  • 1.16. Discussion Questions
  • 1.17. Programming Exercises
• 2. A Proper Class
  • 2.1. Writing a Proper Python Class
    • 2.1.1. A Basic implementation of the MSDie class
  • 2.2. Making your Class Comparable
• 3. Analysis
  • 3.1. Objectives
  • 3.2. What Is Algorithm Analysis?
  • 3.3. Big-O Notation
  • 3.4. An Anagram Detection Example
    • 3.4.1. Solution 1: Checking Off
    • 3.4.2. Solution 2: Sort and Compare
    • 3.4.3. Solution 3: Brute Force
    • 3.4.4. Solution 4: Count and Compare
  • 3.5. Performance of Python Data Structures
  • 3.6. Lists
  • 3.7. Dictionaries
  • 3.8. Summary
  • 3.9. Key Terms
  • 3.10. Discussion Questions
  • 3.11. Programming Exercises
• 4. Basic Data Structures
  • 4.1. Objectives
  • 4.2. What Are Linear Structures?
  • 4.3. What is a Stack?
  • 4.4. The Stack Abstract Data Type
  • 4.5. Implementing a Stack in Python
  • 4.6. Simple Balanced Parentheses
  • 4.7. Balanced Symbols (A General Case)
  • 4.8. Converting Decimal Numbers to Binary Numbers
  • 4.9. Infix, Prefix and Postfix Expressions
    • 4.9.1. Conversion of Infix Expressions to Prefix and Postfix
    • 4.9.2. General Infix-to-Postfix Conversion
    • 4.9.3. Postfix Evaluation
  • 4.10. What Is a Queue?
  • 4.11. The Queue Abstract Data Type
  • 4.12. Implementing a Queue in Python
  • 4.13. Simulation: Hot Potato
  • 4.14. Simulation: Printing Tasks
    • 4.14.1. Main Simulation Steps
    • 4.14.2. Python Implementation
    • 4.14.3. Discussion
  • 4.15. What Is a Deque?
  • 4.16. The Deque Abstract Data Type
  • 4.17. Implementing a Deque in Python
  • 4.18. Palindrome-Checker
  • 4.19. Lists
  • 4.20. The Unordered List Abstract Data Type
  • 4.21. Implementing an Unordered List: Linked Lists
    • 4.21.1. The Node Class
    • 4.21.2. The Unordered List Class
  • 4.22. The Ordered List Abstract Data Type
  • 4.23. Implementing an Ordered List
    • 4.23.1. Analysis of Linked Lists
  • 4.24. Summary
  • 4.25. Key Terms
  • 4.26. Discussion Questions
  • 4.27. Programming Exercises
• 5. Recursion
  • 5.1. Objectives
  • 5.2. What Is Recursion?
  • 5.3. Calculating the Sum of a List 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. Key Terms
  • 5.15. Discussion Questions
  • 5.16. Glossary
  • 5.17. Programming Exercises
• 6. Sorting and Searching
  • 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. Sorting
  • 6.7. The Bubble Sort
  • 6.8. The Selection Sort
  • 6.9. The Insertion Sort
  • 6.10. The Shell Sort
  • 6.11. The Merge Sort
  • 6.12. The Quick Sort
  • 6.13. Summary
  • 6.14. Key Terms
  • 6.15. Discussion Questions
  • 6.16. Programming Exercises
• 7. Trees and Tree Algorithms
  • 7.1. Objectives
  • 7.2. Examples of Trees
  • 7.3. Vocabulary and Definitions
  • 7.4. List of Lists Representation
  • 7.5. Nodes and References
  • 7.6. Parse Tree
  • 7.7. Tree Traversals
  • 7.8. Priority Queues with Binary Heaps
  • 7.9. Binary Heap Operations
  • 7.10. Binary Heap Implementation
    • 7.10.1. The Structure Property
    • 7.10.2. The Heap Order Property
    • 7.10.3. Heap Operations
  • 7.11. Binary Search Trees
  • 7.12. Search Tree Operations
  • 7.13. Search Tree Implementation
  • 7.14. Search Tree Analysis
  • 7.15. Balanced Binary Search Trees
  • 7.16. AVL Tree Performance
  • 7.17. AVL Tree Implementation
  • 7.18. Summary of Map ADT Implementations
  • 7.19. Summary
  • 7.20. Key Terms
  • 7.21. Discussion Questions
  • 7.22. Programming Exercises
• 8. Graphs and Graph Algorithms
  • 8.1. Objectives
  • 8.2. Vocabulary and Definitions
  • 8.3. The Graph Abstract Data Type
  • 8.4. An Adjacency Matrix
  • 8.5. An Adjacency List
  • 8.6. Implementation
  • 8.7. The Word Ladder Problem
  • 8.8. Building the Word Ladder Graph
  • 8.9. Implementing Breadth First Search
  • 8.10. Breadth First Search Analysis
  • 8.11. The Knight’s Tour Problem
  • 8.12. Building the Knight’s Tour Graph
  • 8.13. Implementing Knight’s Tour
  • 8.14. Knight’s Tour Analysis
  • 8.15. General Depth First Search
  • 8.16. Depth First Search Analysis
  • 8.17. Topological Sorting
  • 8.18. Strongly Connected Components
  • 8.19. Shortest Path Problems
  • 8.20. Dijkstra’s Algorithm
  • 8.21. Analysis of Dijkstra’s Algorithm
  • 8.22. Prim’s Spanning Tree Algorithm
  • 8.23. Summary
  • 8.24. Key Terms
  • 8.25. Discussion Questions
  • 8.26. Programming Exercises

Acknowledgements

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables

• Index

• Search Page

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

You have attempted of activities on this page