Concise Notes on Data Structures and Algorithms
Ruby Edition
Download for FREE in 4 easy steps...
This is a Premium eBook  get it free for 30 days
You can also read this in Bookboon.com Premium
Summary
Concise Notes on Data Structures and Algorithms: Ruby Edition is a text for a standard foundational course in the topic.
300+ Business books exclusively in our Premium eReader
 No adverts
 Advanced features
 Personal library
Users who viewed this item also viewed

Mathematics for Computer Scientists

An Introduction to Relational Database Theory

Exercises on Relational Database Theory

SQL: A Comparative Survey

Structured Programming with C++

C Programming in Linux

Go Faster!  The TransRelational™ Approach to DBMS Implementation

Object Oriented Programming using Java
About the book
Description
Concise Notes on Data Structures and Algorithms: Ruby Edition is a text for a standard foundational course in the topic. It emphasizes abstract data types and covers standard containers, algorithm analysis, sorting and searching, hashing, binary search trees, and graphs. Ruby is used for code examples and exercises, but not taught in the book. Code for the book is available on the web. The text presents its topics in short, readable chapters that still provide pedagogical support in the form of examples, review question and answers, exercises, and a glossary.
Content
 Preface
 Introduction
 What Are Data Structures and Algorithms?
 Structure of the Book
 The Ruby Programming Language
 Review Questions
 Exercises
 Review Question Answers
 BuiltIn Types
 Simple and Structured Types
 Types in Ruby
 Symbol: A Simple Type in Ruby
 Range: A Structured Type in Ruby
 Review Questions
 Exercises
 Review Question Answers
 Arrays
 Introduction
 Varieties of Arrays
 Arrays in Ruby
 Review Questions
 Exercises
 Review Question Answers
 Assertions
 Introduction
 Types of Assertions
 Assertions and Abstract Data Types
 Using Assertions
 Assertions in Ruby
 Review Questions
 Exercises
 Review Question Answers
 Containers
 Introduction
 Varieties of Containers
 A Container Taxonomy
 Interfaces in Ruby
 Review Questions
 Exercises
 Review Question Answers
 Stacks
 Introduction
 The Stack ADT
 The Stack Interface
 Using Stacks—An Example
 Contiguous Implementation of the Stack ADT
 Linked Implementation of the Stack ADT
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Queues
 Introduction
 The Queue ADT
 The Queue Interface
 Using Queues—An Example
 Contiguous Implementation of the Queue ADT
 Linked Implementation of the Queue ADT
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Stacks and Recursion
 Introduction
 Balanced Brackets
 Infix, Prefix, and Postfix Expressions
 Tail Recursive Algorithms
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Collections
 Introduction
 Iteration Design Alternatives
 The Iterator Design Pattern
 Iteration in Ruby
 Collections, Iterators, and Containers
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Lists
 Introduction
 The List ADT
 The List Interface
 An Example of Using Lists
 Contiguous Implementation of the List ADT
 Linked Implementation of the List ADT
 Implementing Lists in Ruby
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Analyzing Algorithms
 Introduction
 Measuring the Amount of Work Done
 The Size of the Input
 Which Operations to Count
 Best, Worst, and Average Case Complexity
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Function Growth Rates
 Introduction
 Definitions and Notation
 Establishing the Order of Growth of a Function
 Applying Orders of Growth
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Basic Sorting Algorithms
 Introduction
 Bubble Sort
 Selection Sort
 Insertion Sort
 Shell Sort
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Recurrences
 Introduction
 Setting Up Recurrences
 Solving Recurrences
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Merge sort and Quicksort
 Introduction
 Merge Sort
 Quicksort
 Improvements to Quicksort
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Trees, Heaps, and Heapsort
 Introduction
 Basic Terminology
 Binary Trees
 Heaps
 Heapsort
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Binary Trees
 Introduction
 The Binary Tree ADT
 The Binary Tree Class
 Contiguous Implementation of Binary Trees
 Linked Implementation of Binary Trees
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Binary Search and Binary Search Trees
 Introduction
 Binary Search
 Binary Search Trees
 The Binary Search Tree Class
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Sets
 Introduction
 The Set ADT
 The Set Interface
 Contiguous Implementation of Sets
 Linked Implementation of Sets
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Maps
 Introduction
 The Map ADT
 The Map Interface
 Contiguous Implementation of the Map ADT
 Linked Implementation of the Map ADT
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Hashing
 Introduction
 The Hashing Problem
 Hash Functions
 Collision Resolution Schemes
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Hashed Collections
 Introduction
 Hash Tablets
 HashSets
 HashMaps
 Implementing Hashed Collections in Ruby
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Graphs
 Introduction
 Directed and Undirected Graphs
 Basic Terminology
 The Graph ADT
 The Graph Class
 Contiguous Implementation of the Graph ADT
 Linked Implementation of the Graph ADT
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Graph Algorithms
 Introduction
 Graph Algorithms in Ruby
 Searching Graphs
 DepthFirst Search
 BreadthFirst Search
 Paths in a Graph
 Connected Graphs and Spanning Trees
 Summary and Conclusion
 Review Questions
 Exercises
 Review Question Answers
 Glossary
About the Author
Christopher Fox is a Professor and Director of the Undergraduate Program in Computer Science at James Madison University. He holds a Ph.D. in Information Studies and an M.S. in Computer Science from Syracuse University, and M.A. and B.A. degrees in Philosophy from Michigan State University. Dr. Fox has over 20 years experience teaching Computer Science at JMU, Bowling Green State University, Villanova, Rutgers, and Colgate. Dr. Fox also spent a decade in software research and development at various companies, including AT&T Bell Laboratories. He has published numerous articles and several books, including Introduction to Software Engineering in the Unix/C Environment, and Introduction to Software Engineering Design.
Embed
Embed Frame  Terms of UseThe embed frame is free to use for private persons, universities and schools. It is not allowed to be used by any company for commercial purposes unless it is for media coverage. You may not modify, build upon, or block any portion or functionality of the embed frame, including but not limited to links back to the bookboon.com website.
The Embed frame may not be used as part of a commercial business offering. The embed frame is intended for private people who want to share eBooks on their website or blog, professors or teaching professionals who want to make an eBook available directly on their page, and media, journalists or bloggers who wants to discuss a given eBook
If you are in doubt about whether you can implement the embed frame, you are welcome to contact Thomas Buus Madsen on tbm@bookboon.com and seek permission.