Skip to main content
Problem Solving with Algorithms and Data Structures using Python
The Interactive Edition
Bradley N. Miller, David L. Ranum, Roman Yasinovskyy
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
Front Matter
Preface to the Interactive Editions
Colophon
Acknowledgements
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.10
Self Check
1.10
Self Check
1.11
Exception Handling
1.12
Defining Functions
1.12
Self Check
1.12
Self Check Challenge
1.13
Object-Oriented Programming in Python: Defining Classes
1.13.1
A
Fraction
Class
1.13.1
Self Check
1.13.2
Inheritance: Logic Gates and Circuits
1.13.2
Self Check
1.14
Summary
1.15
Key Terms
2
Algorithm Analysis
2.1
Objectives
2.2
What Is Algorithm Analysis?
2.3
Big O Notation
2.3
Self Check
2.4
An Anagram Detection Example
2.4.1
Solution 1: Anagram Detection Checking Off
2.4.2
Anagram Detection Solution 2: Sort and Compare
2.4.3
Anagram Detection Solution 3: Brute Force
2.4.4
Anagram Detection Solution 4: Count and Compare
2.4.4
Self Check
2.5
Performance of Python Data Structures
2.6
Lists
2.7
Dictionaries
2.7
Self Check
2.8
Summary
2.9
Key Terms
3
Basic Data Structures
3.1
Objectives
3.2
What Are Linear Structures?
3.3
Stacks
3.4
The Stack Abstract Data Type
3.5
Implementing a Stack in Python
3.5
Exercises
3.5
Self Check
3.6
Simple Balanced Parentheses
3.7
Balanced Symbols (A General Case)
3.8
Converting Decimal Numbers to Binary Numbers
3.8
Self Check
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
Self Check
3.10
Queues
3.11
The Queue Abstract Data Type
3.12
Implementing a Queue in Python
3.12
Self Check
3.13
Queue Simulation: Hot Potato
3.14
Queue Simulation: Printing Tasks
3.14.1
Main Simulation Steps
3.14.2
Python Implementation
3.14.3
Discussion
3.14.3
Self Check
3.15
Deques
3.16
The Deque Abstract Data Type
3.17
Implementing a Deque in Python
3.18
Palindrome Checker
3.19
Lists
3.20
The Unordered List Abstract Data Type
3.21
Implementing an Unordered List: Linked Lists
3.21.1
The
Node
Class
3.21.2
The
UnorderedList
Class
3.21.2
Self Check
3.22
The Ordered List Abstract Data Type
3.23
Implementing an Ordered List
3.23.1
Analysis of Linked Lists
3.24
Summary
3.25
Key Terms
4
Recursion
4.1
Objectives
4.2
What Is Recursion?
4.3
Calculating the Sum of a List of Numbers
4.4
The Three Laws of Recursion
4.4
Self Check
4.5
Converting an Integer to a String in Any Base
4.5
Self Check
4.6
Stack Frames: Implementing Recursion
4.7
Visualizing Recursion
4.7
Self Check
4.8
Sierpinski Triangle
4.9
Complex Recursive Problems
4.10
Tower of Hanoi
4.11
Exploring a Maze
4.11
Self Check
4.12
Dynamic Programming
4.13
Summary
4.14
Key Terms
5
Searching and Sorting
5.1
Objectives
5.2
Searching
5.3
The Sequential Search
5.3.1
Analysis of Sequential Search
5.3.1
Self Check
5.4
The Binary Search
5.4.1
Analysis of Binary Search
5.4.1
Self Check
5.5
Hashing
5.5.1
Hash Functions
5.5.2
Collision Resolution
5.5.2
Self Check
5.5.3
Implementing the Map Abstract Data Type
5.5.4
Analysis of Hashing
5.6
Sorting
5.7
The Bubble Sort
5.7
Self Check
5.8
The Selection Sort
5.8
Self Check
5.9
The Insertion Sort
5.9
Self Check
5.10
The Shell Sort
5.10
Self Check
5.11
The Merge Sort
5.11
Self Check
5.12
The Quicksort
5.12
Self Check
5.13
Summary
5.14
Key Terms
6
Trees and Tree Algorithms
6.1
Objectives
6.2
Examples of Trees
6.3
Vocabulary and Definitions
6.4
Implementation
6.5
List of Lists Representation
6.5
Self Check
6.6
Nodes and References
6.6
Self Check
6.7
Parse Tree
6.8
Tree Traversals
6.9
Priority Queues with Binary Heaps
6.10
Binary Heap Operations
6.11
Binary Heap Implementation
6.11.1
The Structure Property
6.11.2
The Heap Order Property
6.11.3
Heap Operations
6.12
Binary Search Trees
6.13
Search Tree Operations
6.14
Search Tree Implementation
6.14
Self Check
6.15
Search Tree Analysis
6.16
Balanced Binary Search Trees
6.17
AVL Tree Performance
6.18
AVL Tree Implementation
6.19
Summary of Map ADT Implementations
6.20
Summary
6.21
Key Terms
7
Graphs and Graphing Algorithms
7.1
Objectives
7.2
Vocabulary and Definitions
7.3
The Graph Abstract Data Type
7.4
An Adjacency Matrix
7.5
An Adjacency List
7.6
Implementation
7.7
The Word Ladder Problem
7.8
Building the Word Ladder Graph
7.9
Implementing Breadth-First Search
7.10
Breadth-First Search Analysis
7.11
The Knight’s Tour Problem
7.12
Building the Knight’s Tour Graph
7.13
Implementing Knight’s Tour
7.14
Knight’s Tour Analysis
7.15
General Depth-First Search
7.16
Depth-First Search Analysis
7.17
Topological Sorting
7.18
Strongly Connected Components
7.19
Shortest Path Problems
7.20
Dijkstra’s Algorithm
7.21
Analysis of Dijkstra’s Algorithm
7.22
Prim’s Spanning Tree Algorithm
7.23
Summary
7.24
Key Terms
8
Advanced Topics
8.1
Objectives
8.2
Python Lists Revisited
8.3
Recursion Revisited
8.3.1
Modular Arithmetic Theorems
8.3.2
Modular Exponentiation
8.3.3
The Greatest Common Divisor and Multiplicative Inverses
8.3.4
RSA Algorithm
8.4
Dictionaries Revisited: Skip Lists
8.4.1
The Map Abstract Data Type
8.4.2
Implementing a Dictionary in Python
8.4.2.1
Searching a Skip List
8.4.2.2
Adding Key-Value Pairs to a Skip List
8.4.2.3
Building the Map
8.4.2.4
Analysis of a Skip List
8.5
Trees Revisited: Quantizing Images
8.5.1
A Quick Review of Digital Images
8.5.2
Quantizing an Image
8.5.3
An Improved Quantization Algorithm Using Octrees
8.6
Graphs Revisited: Pattern Matching
8.6.1
Biological Strings
8.6.2
Simple Comparison
8.6.3
Using Graphs: Finite State Automata
8.6.4
Using Graphs: Knuth-Morris-Pratt
8.7
Summary
8.8
Key Terms
8.9
Exercises
Back Matter
Index
Problem Solving with Algorithms and Data Structures using Python
The Interactive Edition
Bradley N. Miller
Runestone Academy
David L. Ranum
Roman Yasinovskyy
Luther College
Preface to the Interactive Editions
Colophon
Acknowledgements
