Concise Notes on Data Structures and Algorithms Ruby Edition.

Content  
 1. Preface  
 2. Introduction  
 2.1. What Are Data Structures and Algorithms?  
 2.2. Structure of the Book  
 2.3. The Ruby Programming Language  
 2.4. Review Questions  
 2.5. Exercises  
 2.6. Review Question Answers  
 3. Built-In Types  
 3.1. Simple and Structured Types  
 3.2. Types in Ruby  
 3.3. Symbol: A Simple Type in Ruby  
 3.4. Range: A Structured Type in Ruby  
 3.5. Review Questions  
 3.6. Exercises  
 3.7. Review Question Answers  
 4. Arrays  
 4.1. Introduction  
 4.2. Varieties of Arrays  
 4.3. Arrays in Ruby  
 4.4. Review Questions  
 4.5. Exercises  
 4.6. Review Question Answers  
 5. Assertions  
 5.1. Introduction  
 5.2. Types of Assertions  
 5.3. Assertions and Abstract Data Types  
 5.4. Using Assertions  
 5.5. Assertions in Ruby  
 5.6. Review Questions  
 5.7. Exercises  
 5.8. Review Question Answers  
 6. Containers  
 6.1. Introduction  
 6.2. Varieties of Containers  
 6.3. A Container Taxonomy  
 6.4. Interfaces in Ruby  
 6.5. Review Questions  
 6.6. Exercises  
 6.7. Review Question Answers  
 7. Stacks  
 7.1. Introduction  
 7.2. The Stack ADT  
 7.3. The Stack Interface  
 7.4. Using Stacks—An Example  
 7.5. Contiguous Implementation of the Stack ADT  
 7.6. Linked Implementation of the Stack ADT  
 7.7. Summary and Conclusion  
 7.8. Review Questions  
 7.9. Exercises  
 7.10. Review Question Answers  
 8. Queues  
 8.1. Introduction  
 8.2. The Queue ADT  
 8.3. The Queue Interface  
 8.4. Using Queues—An Example  
 8.5. Contiguous Implementation of the Queue ADT  
 8.6. Linked Implementation of the Queue ADT  
 8.7. Summary and Conclusion  
 8.8. Review Questions  
 8.9. Exercises  
 8.10. Review Question Answers  
 9. Stacks and Recursion  
 9.1. Introduction  
 9.2. Balanced Brackets  
 9.3. Infix, Prefix, and Postfix Expressions  
 9.4. Tail Recursive Algorithms  
 9.5. Summary and Conclusion  
 9.6. Review Questions  
 9.7. Exercises  
 9.8. Review Question Answers  
 10. Collections  
 10.1. Introduction  
 10.2. Iteration Design Alternatives  
 10.3. The Iterator Design Pattern  
 10.4. Iteration in Ruby  
 10.5. Collections, Iterators, and Containers  
 10.6. Summary and Conclusion  
 10.7. Review Questions  
 10.8. Exercises  
 10.9. Review Question Answers  
 11. Lists  
 11.1. Introduction  
 11.2. The List ADT  
 11.3. The List Interface  
 11.4. An Example of Using Lists  
 11.5. Contiguous Implementation of the List ADT  
 11.6. Linked Implementation of the List ADT  
 11.7. Implementing Lists in Ruby  
 11.8. Summary and Conclusion  
 11.9. Review Questions  
 11.10. Exercises  
 11.11. Review Question Answers  
 12. Analyzing Algorithms  
 12.1. Introduction  
 12.2. Measuring the Amount of Work Done  
 12.3. The Size of the Input  
 12.4. Which Operations to Count  
 12.5. Best, Worst, and Average Case Complexity  
 12.6. Summary and Conclusion  
 12.7. Review Questions  
 12.8. Exercises  
 12.9. Review Question Answers  
 13. Function Growth Rates  
 13.1. Introduction  
 13.2. Definitions and Notation  
 13.3. Establishing the Order of Growth of a Function  
 13.4. Applying Orders of Growth  
 13.5. Summary and Conclusion  
 13.6. Review Questions  
 13.7. Exercises  
 13.8. Review Question Answers  
 14. Basic Sorting Algorithms  
 14.1. Introduction  
 14.2. Bubble Sort  
 14.3. Selection Sort  
 14.4. Insertion Sort  
 14.5. Shell Sort  
 14.6. Summary and Conclusion  
 14.7. Review Questions  
 14.8. Exercises  
 14.9. Review Question Answers  
 15. Recurrences  
 15.1. Introduction  
 15.2. Setting Up Recurrences  
 15.3. Solving Recurrences  
 15.4. Summary and Conclusion  
 15.5. Review Questions  
 15.5. Exercises  
 15.6. Review Question Answers  
 15.7. Merge sort and Quicksort  
 16. Introduction  
 16.1. Merge Sort  
 16.2. Quicksort  
 16.3. Improvements to Quicksort  
 16.4. Summary and Conclusion  
 16.5. Review Questions  
 16.6. Exercises  
 16.7. Review Question Answers  
 16.8. Trees, Heaps, and Heapsort  
 17. Introduction  
 17.1. Basic Terminology  
 17.2. Binary Trees  
 17.3. Heaps  
 17.4. Heapsort  
 17.5. Summary and Conclusion  
 17.6. Review Questions  
 17.7. Exercises  
 17.8. Review Question Answers  
 17.9. Binary Trees  
 18. Introduction  
 18.1. The Binary Tree ADT  
 18.2. The Binary Tree Class  
 18.3. Contiguous Implementation of Binary Trees  
 18.4. Linked Implementation of Binary Trees  
 18.5. Summary and Conclusion  
 18.6. Review Questions  
 18.7. Exercises  
 18.8. Review Question Answers  
 18.9. Binary Search and Binary Search Trees  
 19. Introduction  
 19.1. Binary Search  
 19.2. Binary Search Trees  
 19.3. The Binary Search Tree Class  
 19.4. Summary and Conclusion  
 19.5. Review Questions  
 19.6. Exercises  
 19.7. Review Question Answers  
 19.8. Sets  
 20. Introduction  
 20.1. The Set ADT  
 20.2. The Set Interface  
 20.3. Contiguous Implementation of Sets  
 20.4. Linked Implementation of Sets  
 20.5. Summary and Conclusion  
 20.6. Review Questions  
 20.7. Exercises  
 20.8. Review Question Answers  
 20.9. Maps  
 21. Introduction  
 21.1. The Map ADT  
 21.2. The Map Interface  
 21.3. Contiguous Implementation of the Map ADT  
 21.4. Linked Implementation of the Map ADT  
 21.5. Summary and Conclusion  
 21.6. Exercises  
 21.7. Review Question Answers  
 21.8. Hashing  
 22. Introduction  
 22.1. The Hashing Problem  
 22.2. Hash Functions  
 22.3. Summary and Conclusion  
 22.4. Review Questions  
 22.5. Exercises  
 22.6. Review Question Answers  
 23. Hashed Collections  
 23.1. Introduction  
 23.2. Hash Tablets  
 23.3. HashSets  
 23.4. HashMaps  
 23.5. Implementing Hashed Collections in Ruby  
 23.6. Summary and Conclusion  
 23.7. Review Questions  
 23.8. Exercises  
 23.9. Review Question Answers  
 24. Graphs  
 24.1. Introduction  
 24.2. Directed and Undirected Graphs  
 24.3. Basic Terminology  
 24.4. The Graph ADT  
 24.5. The Graph Class  
 24.6. Contiguous Implementation of the Graph ADT  
 24.7. Linked Implementation of the Graph ADT  
 24.8. Summary and Conclusion  
 24.9. Review Questions  
 24.10. Exercises  
 24.11. Review Question Answers  
 25. Graph Algorithms  
 25.1. Introduction  
 25.2. Graph Algorithms in Ruby  
 25.3. Searching Graphs  
 25.4. Depth-First Search  
 25.5. Breadth-First Search  
 25.6. Paths in a Graph  
 25.7. Connected Graphs and Spanning Trees  
 25.8. Summary and Conclusion  
 25.9. Review Questions  
 25.10. Exercises  
 25.11. Review Question Answers  
 26. Glossary