Data Structures and Algorithms with Python

Description

This textbook explains the concepts and techniques required to write programs that can handle large amounts of data efficiently. Project-oriented and classroom-tested, the book presents a number of important algorithms supported by examples that bring meaning to the problems faced by computer programmers. The idea of computational complexity is also introduced, demonstrating what can and cannot be computed efficiently so that the programmer can make informed judgements about the algorithms they use. Features: includes both introductory and advanced data structures and algorithms topics, with suggested chapter sequences for those respective courses provided in the preface; provides learning goals, review questions and programming exercises in each chapter, as well as numerous illustrative examples; offers downloadable programs and supplementary files at an associated website, with instructor materials available from the author; presents a primer on Python for those from a different language background. Preface For Teachers Credits 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.4.1 Creating Objects and Calling Methods 1.4.2 The Dog Class 1.5 Operator Overloading 1.5.1 The Dog Class with Overloaded Addition 1.6 Importing Modules 1.7 Indentation in Python Programs 1.8 The Main Function 1.8.1 Python Program Structure 1.9 Reading from a File 1.9.1 A Text File with Single Line Records 1.9.2 Reading and Processing Single Line Records 1.9.3 Pattern for Reading Single Line Records from a File 1.10 Reading Multi-line Records from a File 1.10.1 A Text File with Multiple Line Records 1.10.2 Reading and Processing Multi-line Records 1.10.3 Pattern for Reading Multi-line Records from a File 1.11 A Container Class 1.12 Polymorphism 1.12.1 Graphics Command Classes 1.13 The Accumulator Pattern 1.13.1 List of Squares 1.13.2 A Graphics Program 1.14 Implementing a GUI with Tkinter 1.14.1 A GUI Drawing Application 1.15 XML Files 1.15.1 The Truck XML File 1.15.2 The GoToCommand with XML Creation Code 1.15.3 Writing Graphics Commands to an XML File 1.16 Reading XML Files 1.16.1 Using an XML Parser 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.3.1 List Access Timing 2.3.2 A Plot XML Sample 2.4 Big-Oh Notation 2.5 The PyList Append Operation 2.5.1 Inefficient Append 2.6 A Proof by Induction 2.7 Making the PyList Append Efficient 2.7.1 Efficient Append 2.8 Commonly Occurring Computational Complexities 2.9 More Asymptotic Notation 2.9.1 Big-Oh Asymptotic Upper Bound 2.9.2 Asymptotic Lower Bound 2.9.3 Theta Asymptotic Tight Bound 2.10 Amortized Complexity 2.10.1 A PyList Class 2.10.2 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.4.1 Sum of Integers 3.4.2 Recursive Sum of Integers 3.4.3 No Else Needed 3.5 Tracing the Execution of a Recursive Function 3.6 Recursion in Computer Graphics 3.6.1 Recursive Spiral 3.7 Recursion on Lists and Strings 3.7.1 List Recursion 3.7.2 Reversing a List 3.7.3 Reversing a String 3.7.4 Another Version of Reverse 3.8 Using Type Reflection 3.8.1 Reflection Reverse 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.2.2 The PyList Constructor 4.2.3 PyList Get and Set 4.2.4 PyList Concatenate 4.2.5 PyList Append 4.2.6 PyList Insert 4.2.7 PyList Delete 4.2.8 PyList Equality Test 4.2.9 PyList Iteration 4.2.10 PyList Length 4.2.11 PyList Membership 4.2.12 PyList String Conversion 4.2.13 PyList String Representation 4.3 Cloning Objects 4.4 Item Ordering 4.4.1 The Point Class 4.4.2 Calling the Sort Method 4.5 Selection Sort 4.5.1 Selection Sort's Select Function 4.5.2 The Selection Sort Code 4.6 Merge Sort 4.6.1 The Merge Sort Code 4.7 Quicksort 4.7.1 The Quicksort Code 4.8 Two-Dimensional Sequences 4.8.1 The Board Class 4.8.2 The X, O, and Dummy Classes 4.9 The Minimax Algorithm 4.10 Linked Lists 4.10.1 The Node Class 4.10.2 The LinkedList Constructor 4.10.3 LinkedList Get and Set 4.10.4 LinkedList Concatenate 4.10.5 LinkedList Append 4.10.6 LinkedList Insert 4.10.7 Other Linked List Operations 4.11 Stacks and Queues 4.11.1 The Stack Class Code 4.11.2 Infix Expression Evaluation 4.11.3 Radix Sort 4.11.4 The CharAt Function 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 The HashSet Constructor 5.5.2 Storing an Item 5.5.3 Collision Resolution 5.5.4 HashSet Add Helper Function 5.5.5 The Load Factor 5.5.6 HashSet Add 5.5.7 Deleting an Item 5.5.8 HashSet Remove Helper Function 5.5.9 HashSet Remove 5.5.10 Finding an Item 5.5.11 HashSet Membership 5.5.12 Iterating Over a Set 5.5.13 Other Set Operations 5.5.14 HashSet Difference Update 5.5.15 HashSet Difference 5.6 Solving Sudoku 5.6.1 The Sudoku Reduce Function 5.7 Maps 5.7.1 The HashMap Class 5.7.2 HashSet Get Item 5.7.3 The HashMap Class 5.8 Memoization 5.8.1 A Memoized Fibonacci Function 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.2.1 Constructing ASTs 6.3 Prefix and Postfix Expressions 6.3.1 AST Tree Traversal 6.4 Parsing Prefix Expressions 6.4.1 The Prefix Expression Grammar 6.4.2 A Prefix Expression Parser 6.4.3 The Postfix Expression Grammar 6.5 Binary Search Trees 6.5.1 The BinarySearchTree Class 6.6 Search Spaces 6.6.1 Depth-First Search Algorithm 6.6.2 Sudoku Depth-First Search 6.6.3 Calling Sudoku's Solve Function 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.3.1 Iterative Depth First Search of 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.6.1 A Graph XML File 7.6.2 A Vertex Class 7.6.3 An Edge Class 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 The Trie Class 8.3.2 Inserting into a Trie 8.3.3 Membership in a Trie 8.3.4 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.3.1 The buildFrom Method 9.4 The Heapsort Algorithm Version 1 9.4.1 The addToHeap Method 9.5 Analysis of Version 1 Phase I 9.6 Phase II 9.6.1 The siftDownFromTo Method 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 Sorting 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.2.1 Binary Search Tree Insert 10.3 AVL Trees 10.3.1 Definitions 10.3.2 Implementation Alternatives 10.3.3 AVLNode with Stored Balance 10.3.4 AVL Tree Iterative Insert 10.3.5 Rotations 10.3.6 AVL Tree Recursive Insert 10.3.7 The Recursive Insert AVL Tree Class Declaration 10.3.8 Maintaining Balance Versus Height 10.3.9 AVLNode with Stored Height 10.3.10 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.2.1 The Feed Table 11.2.2 The FeedAttribType Table 11.2.3 The FeedAttribute Table 11.2.4 A Temporary Table 11.2.5 Programming the Joining of Tables 11.2.6 The readRecord Function 11.2.7 Efficient Join 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 Iterative Depth First Search of a Graph 12.2.2 Maze Representation 12.2.3 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 Appendix A: Integer Operators 14 Appendix B: Float Operators 15 Appendix C: String Operators and Methods 16 Appendix D: List Operators and Methods 17 Appendix E: Dictionary Operators and Methods 18 Appendix F: Turtle Methods 19 Appendix G: TurtleScreen Methods 20 Appendix H: Complete Programs 20.1 The Draw Program 20.2 The Scope Program 20.3 The Sort Animation 20.4 The PlotData Program 20.5 The Tic Tac Toe Application 20.6 The Connect Four Front-End Bibliography Index