Data Structures and Algorithms with Python: With an Introduction to Multiprocessing

Preface
For Teachers
Contents
1 Python Programming 101
	1.1 Chapter Goals
	1.2 Creating Objects
		1.2.1 Literal Values
		1.2.2 Non-literal Object Creation
	1.3 Calling Methods on Objects
	1.4 Implementing a Class
	1.5 Operator Overloading
	1.6 Importing Modules
	1.7 Indentation in Python Programs
	1.8 Python Program Structure
	1.9 Reading from a File
	1.10 Reading Multi-line Records from a File
	1.11 A Container Class
	1.12 Polymorphism
	1.13 The Accumulator Pattern
	1.14 Implementing a GUI with Tkinter
	1.15 XML Files
		1.15.1 The Truck XML File
	1.16 Reading XML Files
	1.17 Chapter Summary
	1.18 Review Questions
	1.19 Programming Problems
2 Computational Complexity
	2.1 Chapter Goals
	2.2 Computer Architecture
		2.2.1 Running a Program
	2.3 Accessing Elements in a Python List
	2.4 Big-O Notation
	2.5 The PyList Append Operation
	2.6 A Proof by Induction
	2.7 Making the PyList Append Efficient
	2.8 Commonly Occurring Computational Complexities
	2.9 More Asymptotic Notation
		2.9.1 Big-O Asymptotic Upper Bound
		2.9.2 Asymptotic Lower Bound
		2.9.3 Theta Asymptotic Tight Bound
	2.10 Amortized Complexity
		2.10.1 Proof of Append Complexity
	2.11 Chapter Summary
	2.12 Review Questions
	2.13 Programming Problems
3 Recursion
	3.1 Chapter Goals
	3.2 Scope
		3.2.1 Local Scope
		3.2.2 Enclosing Scope
		3.2.3 Global Scope
		3.2.4 Built-In Scope
		3.2.5 LEGB
	3.3 The Run-Time Stack and the Heap
	3.4 Writing a Recursive Function
	3.5 Tracing the Execution of a Recursive Function
	3.6 Recursion in Computer Graphics
	3.7 Recursion on Lists and Strings
	3.8 Using Type Reflection
	3.9 Chapter Summary
	3.10 Review Questions
	3.11 Programming Problems
4 Sequences
	4.1 Chapter Goals
	4.2 Lists
		4.2.1 The PyList Datatype
	4.3 Cloning Objects
	4.4 Item Ordering
	4.5 Selection Sort
	4.6 Merge Sort
	4.7 Quicksort
	4.8 Two-Dimensional Sequences
	4.9 The Minimax Algorithm
	4.10 Linked Lists
		4.10.1 LinkedList Concatenate
		4.10.2 Other Linked List Operations
	4.11 Stacks and Queues
		4.11.1 Infix Expression Evaluation
		4.11.2 Radix Sort
	4.12 Chapter Summary
	4.13 Review Questions
	4.14 Programming Problems
5 Sets and Maps
	5.1 Chapter Goals
	5.2 Playing Sudoku
	5.3 Sets
	5.4 Hashing
	5.5 The HashSet Class
		5.5.1 Storing an Item
		5.5.2 Collision Resolution
		5.5.3 The Load Factor
		5.5.4 Other HashSet Operations
	5.6 Solving Sudoku
	5.7 Maps
		5.7.1 The HashMap Class
	5.8 Memoization
	5.9 Correlating Two Sources of Information
	5.10 Chapter Summary
	5.11 Review Questions
	5.12 Programming Problems
6 Trees
	6.1 Chapter Goals
	6.2 Abstract Syntax Trees and Expressions
	6.3 Prefix and Postfix Expressions
	6.4 Parsing Prefix Expressions
		6.4.1 The Prefix Expression Grammar
		6.4.2 The Postfix Expression Grammar
	6.5 Binary Search Trees
	6.6 Search Spaces
	6.7 Chapter Summary
	6.8 Review Questions
	6.9 Programming Problems
7 Graphs
	7.1 Chapter Goals
	7.2 Graph Notation
	7.3 Searching a Graph
	7.4 Kruskal\'s Algorithm
		7.4.1 Proof of Correctness
		7.4.2 Kruskal\'s Complexity Analysis
		7.4.3 The Partition Data Structure
	7.5 Dijkstra\'s Algorithm
		7.5.1 Dijkstra\'s Complexity Analysis
	7.6 Graph Representations
	7.7 Chapter Summary
	7.8 Review Questions
	7.9 Programming Problems
8 Membership Structures
	8.1 Chapter Goals
	8.2 Bloom Filters
		8.2.1 The Hashing Functions
		8.2.2 The Bloom Filter Size
		8.2.3 Drawbacks of a Bloom Filter
	8.3 The Trie Datatype
		8.3.1 Inserting into a Trie
		8.3.2 Membership in a Trie
		8.3.3 Comparing Tries and Bloom Filters
	8.4 Chapter Summary
	8.5 Review Questions
	8.6 Programming Problems
9 Heaps
	9.1 Chapter Goals
	9.2 Key Ideas
	9.3 Building a Heap
	9.4 The Heapsort Algorithm Version 1
	9.5 Analysis of Version 1 Phase I
	9.6 Phase II
	9.7 Analysis of Phase II
	9.8 The Heapsort Algorithm Version 2
	9.9 Analysis of Heapsort Version 2
	9.10 Comparison to Other Sortling Algorithms
	9.11 Chapter Summary
	9.12 Review Questions
	9.13 Programming Problems
10 Balanced Binary Search Trees
	10.1 Chapter Goals
	10.2 Binary Search Trees
	10.3 AVL Trees
		10.3.1 Definitions
		10.3.2 Implementation Alternatives
		10.3.3 AVL Tree Iterative Insert
		10.3.4 Rotations
		10.3.5 AVL Tree Recursive Insert
		10.3.6 Maintaining Balance Versus Height
		10.3.7 Deleting an Item from an AVL Tree
	10.4 Splay Trees
		10.4.1 Splay Rotations
	10.5 Iterative Splaying
	10.6 Recursive Splaying
	10.7 Performance Analysis
	10.8 Chapter Summary
	10.9 Review Questions
	10.10 Programming Problems
11 B-Trees
	11.1 Chapter Goals
	11.2 Relational Databases
	11.3 B-Tree Organization
	11.4 The Advantages of B-Trees
	11.5 B-Tree Implementation
	11.6 B-Tree Insert
	11.7 B-Tree Delete
	11.8 Chapter Summary
	11.9 Review Questions
	11.10 Programming Problems
12 Heuristic Search
	12.1 Chapter Goals
	12.2 Depth First Search
		12.2.1 Maze Representation
		12.2.2 DFS Example
	12.3 Breadth First Search
		12.3.1 BFS Example
	12.4 Hill Climbing
		12.4.1 Hill Climbing Example
		12.4.2 Closed Knight\'s Tour
		12.4.3 The N-Queens Problem
	12.5 Best First Search
		12.5.1 Best First Example
	12.6 A* Search
		12.6.1 A* Example
	12.7 Minimax Revisited
	12.8 Chapter Summary
	12.9 Review Questions
	12.10 Programming Problems
13 Parallel Applications
	13.1 Chapter Goals
	13.2 What Parallel Programs Can\'t Do
	13.3 Parallel Applications
		13.3.1 Nuclear Fusion
		13.3.2 Covid-19
		13.3.3 CFD Simulations
		13.3.4 AI
		13.3.5 Large Language Models
	13.4 Chapter Summary
	13.5 Review Questions
14 Distributed Multiprocessing
	14.1 Chapter Goals
	14.2 Sequential Programming Model
	14.3 Shared Memory Parallel Programming Model
	14.4 Distributed Parallel Programming Model
	14.5 DragonHPC Multiprocessing
	14.6 Serialization
	14.7 Sharing State
	14.8 Pool
	14.9 Synchronization Primitives
	14.10 Chapter Summary
	14.11 Review Questions
	14.12 Programming Problems
15 Appendix A: Integer Operators
16 Appendix B: Float Operators
17 Appendix C: String Operators and Methods
18 Appendix D: List Operators and Methods
19 Appendix E: Dictionary Operators and Methods
20 Appendix F:Turtle Methods
21 Appendix G: TurtleScreen Methods
22 Appendix H: Complete Programs
	22.1 The Draw Program
	22.2 The Scope Program
	22.3 The Sort Animation
	22.4 The PlotData Program
	22.5 The Tic Tac Toe Application
	22.6 The Connect Four Front-End
References
Index