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