Data Structures and Algorithms Using Python

Preface. Chapter 1: Abstract Data Types. 1.1 Introduction. 1.2 The Date Abstract Data Type. 1.3 Bags. 1.4 Iterators. 1.5 Application: Student Records. Exercises. Programming Projects. Chapter 2: Arrays. 2.1 The Array Structure. 2.2 The Python List. 2.3 Two-Dimensional Arrays. 2.4 The Matrix Abstract Data Type. 2.5 Application: The Game of Life. Exercises. Programming Projects. Chapter 3: Sets and Maps. 3.1 Sets. 3.2 Maps. 3.3 Multi-Dimensional Arrays. 3.4 Application: Sales Reports. Exercises. Programming Projects. Chapter 4: Algorithm Analysis. 4.1 Complexity Analysis. 4.2 Evaluating the Python List. 4.3 Amortized Cost. 4.4 Evaluating the Set ADT. 4.5 Application: The Sparse Matrix. Exercises. Programming Projects. Chapter 5: Searching and Sorting. 5.1 Searching. 5.2 Sorting. 5.3 Working with Sorted Lists. 5.4 The Set ADT Revisited. Exercises. Programming Projects. Chapter 6: Linked Structures. 6.1 Introduction. 6.2 The Singly Linked List. 6.3 The Bag ADT Revisited. 6.4 More Ways to Build a Linked List. 6.5 The Sparse Matrix Revisited. 6.6 Application: Polynomials. Exercises. Programming Projects. Chapter 7: Stacks. 7.1 The Stack ADT. 7.2 Implementing the Stack. 7.3 Stack Applications. 7.4 Application: Solving a Maze. Exercises. Programming Projects. Chapter 8: Queues. 8.1 The Queue ADT. 8.2 Implementing the Queue. 8.3 Priority Queues. 8.4 Application: Computer Simulations. Exercises. Programming Projects. Chapter 9: Advanced Linked Lists. 9.1 The Doubly Linked List. 9.2 The Circular Linked List. 9.3 Multi-Linked Lists. 9.4 Complex Iterators. 9.5 Application: Text Editor. Exercises. Programming Projects. Chapter 10: Recursion. 10.1 Recursive Functions. 10.2 Properties of Recursion. 10.3 How Recursion Works. 10.4 Recursive Applications. 10.5 Application: The Eight-Queens Problem. Exercises. Programming Projects. Chapter 11: Hash Tables. 11.1 Introduction. 11.2 Hashing. 11.3 Separate Chaining. 11.4 Hash Functions. 11.5 The HashMap Abstract Data Type. 11.6 Application: Histograms. Exercises. Programming Projects. Chapter 12: Advanced Sorting. 12.1 Merge Sort. 12.2 Quick Sort. 12.3 How Fast Can We Sort? 12.4 Radix Sort. 12.5 Sorting Linked Lists. Exercises. Programming Projects. Chapter 13: Binary Trees. 13.1 The Tree Structure. 13.2 The Binary Tree. 13.3 Expression Trees. 13.4 Heaps. 13.5 Heapsort. 13.6 Application: Morse Code. Exercises. Programming Projects. Chapter 14: Search Trees. 14.1 The Binary Search Tree. 14.2 Search Tree Iterators. 14.3 AVL Trees. 14.4 The 2-3 Tree. Exercises. Programming Projects. Appendix A Python Review. A.1 The Python Interpreter. A.2 The Basics of Python. A.3 User Interaction. A.4 Control Structures. A.5 Collections. A.6 Text Files. A.7 User-Defined Functions. Appendix B User-Defined Modules. B.1 Structured Programs. B.2 Namespaces. Appendix C Exceptions. C.1 Catching Exceptions. C.2 Raising Exceptions. C.3 Standard Exceptions. C.4 Assertions. Appendix D Classes. D.1 The Class Definition. D.2 Overloading Operators. D.3 Inheritance. D.4 Polymorphism.