Data Structures and Algorithms in Python (Instructor Resources, Solution Manual, Code Solutions)

Cover
Title Page
Copyright Page
Preface
Contents
1 Python Primer
	1.1 Python Overview
		1.1.1 The Python Interpreter
		1.1.2 Preview of a Python Program
	1.2 Objects in Python
		1.2.1 Identifiers, Objects, and the Assignment Statement
		1.2.2 Creating and Using Objects
		1.2.3 Python’s Built-In Classes
	1.3 Expressions, Operators, and Precedence
		1.3.1 Compound Expressions and Operator Precedence
	1.4 Control Flow
		1.4.1 Conditionals
		1.4.2 Loops
	1.5 Functions
		1.5.1 Information Passing
		1.5.2 Python’s Built-In Functions
	1.6 Simple Input and Output
		1.6.1 Console Input and Output
		1.6.2 Files
	1.7 Exception Handling
		1.7.1 Raising an Exception
		1.7.2 Catching an Exception
	1.8 Iterators and Generators
	1.9 Additional Python Conveniences
		1.9.1 Conditional Expressions
		1.9.2 Comprehension Syntax
		1.9.3 Packing and Unpacking of Sequences
	1.10 Scopes and Namespaces
	1.11 Modules and the Import Statement
		1.11.1 Existing Modules
	1.12 Exercises
2 Object-Oriented Programming
	2.1 Goals, Principles, and Patterns
		2.1.1 Object-Oriented Design Goals
		2.1.2 Object-Oriented Design Principles
		2.1.3 Design Patterns
	2.2 Software Development
		2.2.1 Design
		2.2.2 Pseudo-Code
		2.2.3 Coding Style and Documentation
		2.2.4 Testing and Debugging
	2.3 Class Definitions
		2.3.1 Example: CreditCard Class
		2.3.2 Operator Overloading and Python’s Special Methods
		2.3.3 Example: Multidimensional Vector Class
		2.3.4 Iterators
		2.3.5 Example: Range Class
	2.4 Inheritance
		2.4.1 Extending the CreditCard Class
		2.4.2 Hierarchy of Numeric Progressions
		2.4.3 Abstract Base Classes
	2.5 Namespaces and Object-Orientation
		2.5.1 Instance and Class Namespaces
		2.5.2 Name Resolution and Dynamic Dispatch
	2.6 Shallow and Deep Copying
	2.7 Exercises
3 Algorithm Analysis
	3.1 Experimental Studies
		3.1.1 Moving Beyond Experimental Analysis
	3.2 The Seven Functions Used in This Book
		3.2.1 Comparing Growth Rates
	3.3 Asymptotic Analysis
		3.3.1 The “Big-Oh” Notation
		3.3.2 Comparative Analysis
		3.3.3 Examples of Algorithm Analysis
	3.4 Simple Justification Techniques
		3.4.1 By Example
		3.4.2 The “Contra” Attack
		3.4.3 Induction and Loop Invariants
	3.5 Exercises
4 Recursion
	4.1 Illustrative Examples
		4.1.1 The Factorial Function
		4.1.2 Drawing an English Ruler
		4.1.3 Binary Search
		4.1.4 File Systems
	4.2 Analyzing Recursive Algorithms
	4.3 Recursion Run Amok
		4.3.1 Maximum Recursive Depth in Python
	4.4 Further Examples of Recursion
		4.4.1 Linear Recursion
		4.4.2 Binary Recursion
		4.4.3 Multiple Recursion
	4.5 Designing Recursive Algorithms
	4.6 Eliminating Tail Recursion
	4.7 Exercises
5 Array-Based Sequences
	5.1 Python’s Sequence Types
	5.2 Low-Level Arrays
		5.2.1 Referential Arrays
		5.2.2 Compact Arrays in Python
	5.3 Dynamic Arrays and Amortization
		5.3.1 Implementing a Dynamic Array
		5.3.2 Amortized Analysis of Dynamic Arrays
		5.3.3 Python’s List Class
	5.4 Efficiency of Python’s Sequence Types
		5.4.1 Python’s List and Tuple Classes
		5.4.2 Python’s String Class
	5.5 Using Array-Based Sequences
		5.5.1 Storing High Scores for a Game
		5.5.2 Sorting a Sequence
		5.5.3 Simple Cryptography
	5.6 Multidimensional Data Sets
	5.7 Exercises
6 Stacks, Queues, and Deques
	6.1 Stacks
		6.1.1 The Stack Abstract Data Type
		6.1.2 Simple Array-Based Stack Implementation
		6.1.3 Reversing Data Using a Stack
		6.1.4 Matching Parentheses and HTML Tags
	6.2 Queues
		6.2.1 The Queue Abstract Data Type
		6.2.2 Array-Based Queue Implementation
	6.3 Double-Ended Queues
		6.3.1 The Deque Abstract Data Type
		6.3.2 Implementing a Deque with a Circular Array
		6.3.3 Deques in the Python Collections Module
	6.4 Exercises
7 Linked Lists
	7.1 Singly Linked Lists
		7.1.1 Implementing a Stack with a Singly Linked List
		7.1.2 Implementing a Queue with a Singly Linked List
	7.2 Circularly Linked Lists
		7.2.1 Round-Robin Schedulers
		7.2.2 Implementing a Queue with a Circularly Linked List
	7.3 Doubly Linked Lists
		7.3.1 Basic Implementation of a Doubly Linked List
		7.3.2 Implementing a Deque with a Doubly Linked List
	7.4 The Positional List ADT
		7.4.1 The Positional List Abstract Data Type
		7.4.2 Doubly Linked List Implementation
	7.5 Sorting a Positional List
	7.6 Case Study: Maintaining Access Frequencies
		7.6.1 Using a Sorted List
		7.6.2 Using a List with the Move-to-Front Heuristic
	7.7 Link-Based vs. Array-Based Sequences
	7.8 Exercises
8 Trees
	8.1 General Trees
		8.1.1 Tree Definitions and Properties
		8.1.2 The Tree Abstract Data Type
		8.1.3 Computing Depth and Height
	8.2 Binary Trees
		8.2.1 The Binary Tree Abstract Data Type
		8.2.2 Properties of Binary Trees
	8.3 Implementing Trees
		8.3.1 Linked Structure for Binary Trees
		8.3.2 Array-Based Representation of a Binary Tree
		8.3.3 Linked Structure for General Trees
	8.4 Tree Traversal Algorithms
		8.4.1 Preorder and Postorder Traversals of General Trees
		8.4.2 Breadth-First Tree Traversal
		8.4.3 Inorder Traversal of a Binary Tree
		8.4.4 Implementing Tree Traversals in Python
		8.4.5 Applications of Tree Traversals
		8.4.6 Euler Tours and the Template Method Pattern
	8.5 Case Study: An Expression Tree
	8.6 Exercises
9 Priority Queues
	9.1 The Priority Queue Abstract Data Type
		9.1.1 Priorities
		9.1.2 The Priority Queue ADT
	9.2 Implementing a Priority Queue
		9.2.1 The Composition Design Pattern
		9.2.2 Implementation with an Unsorted List
		9.2.3 Implementation with a Sorted List
	9.3 Heaps
		9.3.1 The Heap Data Structure
		9.3.2 Implementing a Priority Queue with a Heap
		9.3.3 Array-Based Representation of a Complete Binary Tree
		9.3.4 Python Heap Implementation
		9.3.5 Analysis of a Heap-Based Priority Queue
		9.3.6 Bottom-Up Heap Construction
		9.3.7 Python’s heapq Module
	9.4 Sorting with a Priority Queue
		9.4.1 Selection-Sort and Insertion-Sort
		9.4.2 Heap-Sort
	9.5 Adaptable Priority Queues
		9.5.1 Locators
		9.5.2 Implementing an Adaptable Priority Queue
	9.6 Exercises
10 Maps, Hash Tables, and Skip Lists
	10.1 Maps and Dictionaries
		10.1.1 The Map ADT
		10.1.2 Application: Counting Word Frequencies
		10.1.3 Python’s MutableMapping Abstract Base Class
		10.1.4 Our MapBase Class
		10.1.5 Simple Unsorted Map Implementation
	10.2 Hash Tables
		10.2.1 Hash Functions
		10.2.2 Collision-Handling Schemes
		10.2.3 Load Factors, Rehashing, and Efficiency
		10.2.4 Python Hash Table Implementation
	10.3 Sorted Maps
		10.3.1 Sorted Search Tables
		10.3.2 Two Applications of Sorted Maps
	10.4 Skip Lists
		10.4.1 Search and Update Operations in a Skip List
		10.4.2 Probabilistic Analysis of Skip Lists
	10.5 Sets, Multisets, and Multimaps
		10.5.1 The Set ADT
		10.5.2 Python’s MutableSet Abstract Base Class
		10.5.3 Implementing Sets, Multisets, and Multimaps
	10.6 Exercises
11 Search Trees
	11.1 Binary Search Trees
		11.1.1 Navigating a Binary Search Tree
		11.1.2 Searches
		11.1.3 Insertions and Deletions
		11.1.4 Python Implementation
		11.1.5 Performance of a Binary Search Tree
	11.2 Balanced Search Trees
		11.2.1 Python Framework for Balancing Search Trees
	11.3 AVL Trees
		11.3.1 Update Operations
	11.3.2 Python Implementation
	11.4 Splay Trees
		11.4.1 Splaying
		11.4.2 When to Splay
		11.4.3 Python Implementation
		11.4.4 Amortized Analysis of Splaying
	11.5 (2,4) Trees
		11.5.1 Multiway Search Trees
		11.5.2 (2,4)-Tree Operations
	11.6 Red-Black Trees
		11.6.1 Red-Black Tree Operations
		11.6.2 Python Implementation
	11.7 Exercises
12 Sorting and Selection
	12.1 Why Study Sorting Algorithms?
	12.2 Merge-Sort
		12.2.1 Divide-and-Conquer
		12.2.2 Array-Based Implementation of Merge-Sort
		12.2.3 The Running Time of Merge-Sort
		12.2.4 Merge-Sort and Recurrence Equations
		12.2.5 Alternative Implementations of Merge-Sort
	12.3 Quick-Sort
		12.3.1 Randomized Quick-Sort
		12.3.2 Additional Optimizations for Quick-Sort
	12.4 Studying Sorting through an Algorithmic Lens
		12.4.1 Lower Bound for Sorting
		12.4.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort
	12.5 Comparing Sorting Algorithms
	12.6 Python’s Built-In Sorting Functions
		12.6.1 Sorting According to a Key Function
	12.7 Selection
		12.7.1 Prune-and-Search
		12.7.2 Randomized Quick-Select
		12.7.3 Analyzing Randomized Quick-Select
	12.8 Exercises
13 Text Processing
	13.1 Abundance of Digitized Text
		13.1.1 Notations for Strings and the Python str Class
	13.2 Pattern-Matching Algorithms
		13.2.1 Brute Force
		13.2.2 The Boyer-Moore Algorithm
		13.2.3 The Knuth-Morris-Pratt Algorithm
	13.3 Dynamic Programming
		13.3.1 Matrix Chain-Product
		13.3.2 DNA and Text Sequence Alignment
	13.4 Text Compression and the Greedy Method
		13.4.1 The Huffman Coding Algorithm
		13.4.2 The Greedy Method
	13.5 Tries
		13.5.1 Standard Tries
		13.5.2 Compressed Tries
		13.5.3 Suffix Tries
		13.5.4 Search Engine Indexing
	13.6 Exercises
14 Graph Algorithms
	14.1 Graphs
		14.1.1 The Graph ADT
	14.2 Data Structures for Graphs
		14.2.1 Edge List Structure
		14.2.2 Adjacency List Structure
		14.2.3 Adjacency Map Structure
		14.2.4 Adjacency Matrix Structure
		14.2.5 Python Implementation
	14.3 Graph Traversals
		14.3.1 Depth-First Search
		14.3.2 DFS Implementation and Extensions
		14.3.3 Breadth-First Search
	14.4 Transitive Closure
	14.5 Directed Acyclic Graphs
		14.5.1 Topological Ordering
	14.6 Shortest Paths
		14.6.1 Weighted Graphs
		14.6.2 Dijkstra’s Algorithm
	14.7 Minimum Spanning Trees
		14.7.1 Prim-Jarník Algorithm
		14.7.2 Kruskal’s Algorithm
		14.7.3 Disjoint Partitions and Union-Find Structures
	14.8 Exercises
15 Memory Management and B-Trees
	15.1 Memory Management
		15.1.1 Memory Allocation
		15.1.2 Garbage Collection
		15.1.3 Additional Memory Used by the Python Interpreter
	15.2 Memory Hierarchies and Caching
		15.2.1 Memory Systems
		15.2.2 Caching Strategies
	15.3 External Searching and B-Trees
		15.3.1 (a,b) Trees
		15.3.2 B-Trees
	15.4 External-Memory Sorting
		15.4.1 Multiway Merging
	15.5 Exercises
A Character Strings in Python
B Useful Mathematical Facts
Bibliography
Index