Concise Notes on Data Structures and Algorithms

1 Concise Notes on Data Structures and Algorithms Ruby Edition Christopher Fox James Madison University 2011. Contents 1 Introduction 1. What Are Data Structures and Algorithms ?.. 1. Structure of the Book .. 3. The Ruby Programming Language.. 3. Review Questions.. 3. Exercises .. 4. Review Question Answers.. 4. 2 Built-In Types 5. Simple and Structured Types.. 5. Types in Ruby.. 5. Symbol: A Simple Type in Ruby.. 5. Review Questions.. 9. Exercises .. 9. Review Question Answers.. 9. 3 Arrays 10. Introduction.. 10. Varieties of Arrays.

2 10. Arrays in Ruby.. 11. Review Questions.. 12. Exercises .. 12. Review Question Answers.. 13. 4 Assertions 14. Introduction.. 14. Types of Assertions.. 14. Assertions and Abstract Data Types.. 15. Using Assertions.. 15. Assertions in Ruby.. 16. Review Questions.. 17. Exercises .. 17. Review Question Answers.. 19. 5 Containers 20. Introduction.. 20. Varieties of Containers .. 20. 1. Contents A Container Taxonomy.. 20. Interfaces in Ruby.. 21. Exercises .. 22. Review Question Answers.. 23. 6 Stacks 24. Introduction.. 24. The Stack ADT.

3 24. The Stack Interface.. 25. Using Stacks An Example .. 25. Contiguous Implementation of the Stack ADT.. 26. Linked Implementation of the Stack ADT.. 27. Summary and Conclusion.. 28. Review Questions.. 28. Exercises .. 29. Review Question Answers.. 29. 7 Queues 31. Introduction.. 31. The Queue ADT.. 31. The Queue Interface .. 31. Using Queues An Example .. 32. Contiguous Implementation of the Queue ADT.. 32. Linked Implementation of the Queue ADT.. 34. Summary and Conclusion.. 35. Review Questions.. 35. Exercises .. 35. Review Question Answers.

4 36. 8 Stacks and Recursion 37. Introduction.. 37. Balanced Brackets.. 38. Infix, Prefix, and Postfix Expressions.. 39. Tail Recursive Algorithms .. 44. Summary and Conclusion.. 44. Review Questions.. 45. Exercises .. 45. Review Question Answers.. 45. 2. Contents 9 Collections 47. Introduction.. 47. Iteration Design Alternatives .. 47. The Iterator Design Pattern.. 48. Iteration in Ruby.. 49. Collections, Iterators, and Containers.. 50. Summary and Conclusion.. 51. Review Questions.. 52. Exercises .. 52. Review Question Answers.

5 52. 10 Lists 54. Introduction.. 54. The List ADT.. 54. The List Interface .. 55. Using Lists An Example.. 55. Contiguous Implementation of the List ADT .. 56. Linked Implementation of the List ADT.. 56. Implementing Lists in Ruby.. 58. Summary and Conclusion.. 58. Review Questions.. 58. Exercises .. 58. Review Question Answers.. 59. 11 Analyzing Algorithms 61. Introduction.. 61. Measuring the Amount of Work Done.. 61. Which Operations to Count.. 62. Best, Worst, and Average Case Complexity.. 63. Review Questions.. 65. Exercises.

6 66. Review Question Answers.. 66. 12 Function Growth Rates 68. Introduction.. 68. Definitions and Notation.. 68. Establishing the Order of Growth of a Function .. 69. Applying Orders of Growth .. 70. Summary and Conclusion.. 70. iii Contents Review Questions.. 70. Exercises .. 70. Review Question Answers.. 71. 13 Basic Sorting Algorithms 72. Introduction.. 72. Bubble Sort.. 72. Selection Sort .. 73. Insertion Sort .. 74. Shell Sort.. 76. Summary and Conclusion.. 77. Review Questions.. 78. Exercises .. 78. Review Question Answers.

7 78. 14 Recurrences 80. Introduction.. 80. Setting Up Recurrences.. 80. Review Questions.. 83. Exercises .. 83. Review Question Answers.. 84. 15: Merge sort and Quicksort 85. Introduction.. 85. Merge Sort .. 85. Quicksort.. 87. Summary and Conclusion.. 91. Review Questions.. 91. Exercises .. 91. Review Question Answers.. 92. 16 Trees, Heaps, and Heapsort 93. Introduction.. 93. Basic Terminology.. 93. Binary Trees.. 94. Heaps.. 94. Heapsort.. 95. Summary and Conclusion.. 97. Review Questions.. 97. iv Contents Exercises .. 97.

8 Review Question Answers.. 98. 17 Binary Trees 99. Introduction.. 99. The Binary Tree ADT.. 99. The Binary Tree Class.. 100. Contiguous Implementation of Binary Trees .. 102. Linked Implementation of Binary Trees.. 102. Summary and Conclusion.. 103. Review Questions.. 103. Exercises .. 104. Review Question Answers.. 104. 18 Binary Search and Binary Search Trees 106. Introduction.. 106. Binary Search .. 106. Binary Search Trees.. 108. The Binary Search Tree Class .. 109. Summary and Conclusion.. 110. Review Questions.. 110. Exercises.

9 111. Review Question Answers.. 112. 19 Sets 113. Introduction.. 113. The Set ADT.. 113. The Set Interface.. 113. Contiguous Implementation of Sets.. 114. Linked Implementation of Sets.. 114. Summary and Conclusion.. 114. Review Questions.. 115. Exercises .. 115. Review Question Answers.. 116. 20 Maps 117. Introduction.. 117. The Map ADT .. 117. The Map Interface.. 118. Contiguous Implementation of the Map ADT.. 118. v Contents Linked Implementation of the Map ADT .. 118. Summary and Conclusion.. 119. Review Questions.. 120.

10 Exercises .. 120. Review Question Answers.. 120. 21 Hashing 122. Introduction.. 122. The Hashing Problem.. 122. Collision Resolution Schemes.. 124. Summary and Conclusion.. 127. Review Questions.. 127. Exercises .. 127. Review Question Answers.. 128. 22 Hashed Collections 129. Introduction.. 129. Hash Tablets.. 129. HashSets.. 130. Implementing Hashed Collections in Ruby .. 130. Summary and Conclusion.. 131. Review Questions.. 131. Exercises .. 131. Review Question Answers.. 132. Glossary 133. vi 1: Introduction What Are Data Structures and Algorithms ?