Efnisyfirlit

• 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