Format:
1 Online-Ressource (xix, 748 pages)
Edition:
1st edition
ISBN:
9781118476734
Content:
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
Content:
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
Content:
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
Content:
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
Content:
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
Content:
14.2.3 Adjacency Map Structure
Additional Edition:
ISBN 9781118290279
Additional Edition:
Erscheint auch als Druck-Ausgabe Goodrich, Michael T Data Structures and Algorithms in Python Somerset : Wiley,c2013 ISBN 9781118290279
Language:
English
Subjects:
Computer Science
Keywords:
Datenstruktur
;
Algorithmus
;
Python
URL:
Volltext
(lizenzpflichtig)
Author information:
Tamassia, Roberto 1960-
Author information:
Goodrich, Michael T. 1961-
