Data Structures and Algorithms Using Python

Rance D. Necaise, Department of Computer Science, College of William and MaryTo my nieces and nephewsAllison, Janey, Kevin, RJ, and mariaThis page intentionally left blankContentsPrefaceChapter 1: Abstract Data Types1.1 Introduction1.1.1 Abstractions21.2 Abstract Data Types31.1.3 Data structures51.1.4 General definitions61.2 The Date Abstract Data Ty1.2.1 Defining the adt1.2.2 Using the ADT1.2.3 Preconditions and Postconditions2.4 Implementing the ADT101.3 Bags143.1 The Bag Abstract Data Type1.3.2 Selecting a Data Structure171.3.3 List-Based Implementation191. 4 Iterators201.4.1 Designing an Iterator214.2 Using Iterators221.5 Application Student Records231.5.1 Designing a Solution231.5.2 Implementation26Exercises28Programming projects29Chapter 2: Arrays332. 1 The array structure332.1.1 Why Study arrays?342.1.2 The Array abstract Data Type342.1.3 Implementing the Array362.2 The Python ListCONTENTS2. 2.1 Creating a Python List412. 2.2 Appending Items422.2.3 Extending a List442.2.4 Inserting Items442.2.5 List Slice452.3 TWO-Dimensional Arrays472.3.1 The Array2D Abstract Data Type472.3.2 Implementing the 2-D Array492.4 The Matrix abstract data type522.4.1 Matrix Operations532.4.2 Implementing the Matrix552.5 Application: The Game of Life572.5.1 Rules of the game572.5.2 Designing a Solution592.5.3 Implementation61Eⅹ excises64Programming projects65Chapter 3: Sets and Maps693.1 Sets693.1.1 The Set Abstract Data Type703.1.2 Selecting a Data Structure723.1.3 List-Based Implementation723.2 Maps753.2.1 The Map Abstract Data Type3.2.2 List-Based Implementation773.3 Multi-Dimensional Arrays803.3.1 The MultiArray Abstract Data Type813.3.2 Data Organization813.3.3 Variable-Length Arguments853.3.4 Implementing the MultiArray863.4 Application: Sales Reports89Exercises95Programming Projects96Chapter 4: Algorithm Analysis974. 1 Complexity Analysis974.1.1 Big-O Notation994.1.2 Evaluating Python Code1044.2 Evaluating the Python List1084.3 Amortized cost1114. 4 Evaluating the set adt113CONTENTS4.5 Application: The Sparse Matrix1154.5.1 List-Based Implementation1154.5.2 Efficiency Analysis120Exercises121rogramming Projects122Chapter 5: Searching and Sorting1255.1 Searchin1255.1.1 The Linear search1265.1.2 The Binary Search1285.2 Sorting1315.2.1 Bubble Sort1325.2.2 Selection Sort1365.2.3 Insertion Sort1385.3 Working with sorted Lists1425.3. 1 Maintaining a Sorted List1425.3.2 Merging Sorted Lists1435.4 The Set Adt Revisited1475.4.1 A Sorted List Implementation1475.4.2 Comparing the mplementations152Exercises152Programming Projects153Chapter 6: Linked Structures1556.1 Introduction1566.2 The Singly Linked List1596.2.1 Traversing the Nodes1596. 2.2 Searching for a Node1616. 2. 3 Prepending Nodes1626.2.4 Removing Nodes1636.3 The Bag adt revisited1656.3.1 A Linked List Implementation1656.3.2 Comparing Implementations1676.3.3 Linked List Iterators1686. 4 More Ways to Build a Linked List,,,,,,1696.4.1 Using a Tail Reference1696.4.2 The Sorted Linked list1716.5 The Sparse Matrix Revisited1746.5.1 An Array of Linked Lists Implementation1756.5.2 Comparing the Implementations1786.6 Application: Polynomials1796.6.1 Polynomial Operations179CONTENTS6.6.2 The Polynomial ADT1816.6.3 Implementation.181Exercises189Programming Projects190Chapter 7: Stacks1937.1 The stack ADT1937.2 Implementing the stack1957.2.1 Using a python list1957.2.2 Using a Linked list1967.3 Stack Applications1987.3.1 Balanced delimiters1997.3.2 Evaluating Postfix Expressions2027.4 Application: Solving a Maze2067.4.1 Backtracking2077.4.2 Designing a Solution20874.3 The Maze adt2117.4.4 Implementation214EXercises218Programming Projects219Chapter 8: Queues2218. 1 The Queue ADT.2218.2 Implementing the Queue2228. 2. 1 Using a Python List2228.2.2 Using a Circular Array2248.2.3 Using a linked list2288.3 Priority Queues2308.3.1 The Priority Queue ADT2308.3.2 Implementation: Unbounded Priority Queue2328.3.3 Implementation: Bounded Priority Queue2358.4 Application: Computer Simulations2378.4.1 Airline Ticket Counter2378.4.2 Implementation239excises244Programming Projects246Chapter 9: Advanced Linked lists2479. 1 The Doubly Linked List2479.1.1 Organization2479.1.2 List Operations2489.2 The Circular Linked list253CONTENTS9.2.1 Organization2539.2.2 List Operations2549.3 Multi-Linked Lists2599.3.1 Multiple Chains2599.3.2 The Sparse matrix2609. 4 Complex Iterators2629.5 Application: Text Editor2639.5.1 Typical Editor Operations2639.5.2 The edit Buffer adt2669.5.3 Implementation268Exercises275Programming Projects275Chapter 10: Recursion27710.1 Recursive Functions27710.2 Properties of Recursion27910.2.1 Factorials28010.2.2 Recursive call trees28110.2.3 The Fibonacci sequence28310.3 How Recursion Works28310.3.1 The run time stack28410.3.2 Using a Software Stack28610.3.3 Tail Recursion28910.4 Recursive Applications29010.4.1 Recursive Binary search29010.4.2 Towers of hanoi29210.4.3 Exponential Operation29610.4. 4 Playing Tic-Tac-Toe29710.5 Application: The Eight-Queens Problem29910.5.1 Solving for Four-Queens30110.5.2 Designing a Solution303Eⅹ excises.307Programming Projects308chapter 11: Hash Tables30911. 1 Introduction30911.2 Hashing31111.2. 1 Linear Probing31211.2.2 Clustering31511.2.3 Rehashing31811. 2. 4 Efficiency Analysis32011.3 Separate chaining321CONTENTS11. 4 Hash Functions3231. 5 The HashMap Abstract Data Type32511.6 Application: Histograms33011.6. 1 The Histogram Abstract Data Type33011.6.2 The Color Histogram334Exercises337Programming Projects338Chapter 12: Advanced Sorting3392.1 Merge Sort33912.1.1 Algorithm Description34012.1.2 Basic Implementation34012.1.3 Improved Implementation34212.1.4 Efficiency Analysis34512.2 Quick Sort34712.2.1 Algorithm Description34812.2.2 Implementation34912.2.3 Efficiency Analysis35312.3 How Fast Can We sort?35312.4 Radix Sort35412.4.1 Algorithm Description35412.4.2 Basic Implementation35612. 4. 3 Efficiency Analysis35812.5 Sorting Linked list35812.5. 1 Insertion Sort35912.5.2 Merge Sort362Exercises367Programming Projects368Chapter 13: Binary Trees36913.1 The Tree structure36913.2 The binary tree37313.2.1 Properties37313.2.2 Implementation37513.2.3 Tree Traversals.37613.3 Expression Trees38013.3. 1 Expression Tree Abstract data type38213.3.2 String Representation38313.3.3 Tree Evaluation38413.3.4 Tree Construction38613. 4 Heaps39013.4.1 Definition391