Learn How to Code
  • Welcome
  • Foundations
    • Introduction
      • Becoming a web developer
      • Motivation and mindset
      • Join a supportive community
      • How does the web work?
    • Requirements
      • Prerequisites
      • Text editors
      • Command line basics
      • Setting up Git
      • Setting up Node
    • Git
      • Git basics
      • Project: Practicing Git
    • Frontend
      • HTML and CSS
      • Developer Tools
      • Project: Create a web page
    • JavaScript
      • Strings and Conditionals
      • Using Developer Tools
      • Functions
      • Problem solving
      • Project: Rock paper scissors
      • Writing clean code
      • Arrays and Loops
      • The DOM
      • Project: Etch-A-Sketch
      • Objects and More Arrays
      • Project: Calculator
    • Backend
      • Frameworks
    • Next steps
  • Deep dives
    • Computer Science
      • Pseudocode and algorithms
      • Recursion and algorithms
        • Project: Fibs and sorting
        • More on algorithms
        • Big O
        • Project: Practicing Big O
      • Data structures
        • Maps, Stacks and Queues
        • Project: Stacks and Queues
        • Nodes, Linked Lists and Trees
        • Project: Linked Lists
        • Project: Trees
        • Next steps
    • Databases
      • Databases and SQL
      • Project: SQL Zoo
    • Design / UX
      • Fonts and typography
      • Grids
      • Project: Teardown
      • Responsive design
      • Project: Mobile friendly
      • CSS frameworks
      • Project: Bootstrapping
    • HTML / CSS
      • HTML Basics
        • Linking
        • Images and media
        • Project: Embedding media
        • HTML5
        • Tables
        • Lists
        • Forms
        • Project: Make a form
      • CSS Basics
        • Box model
        • Floats and positioning
        • Flexbox
        • Grids
        • Project: Breaking news
        • Best practices
        • Backgrounds and gradients
        • Project: One more thing
        • CSS3
        • Preprocessors
        • Project: Your own framework
      • Next steps
    • JavaScript
      • Refresher
      • Organization
      • Objects and constructors
      • Project: Library
      • Factory functions and module patterns
      • Project: Tic Tac Toe
      • Classes
      • ES6 Modules
      • Project: Restaurant
      • Object Oriented Programming
      • Project: Todo list
      • Linting
      • Menus and sliders
      • Forms
      • ES6 features
      • JSON
      • Callbacks and promises
      • Using APIs
      • Async and Await
      • Project: Weather
      • Testing
      • Project: Testing 1-2-3
      • Advanced Testing
      • Project: Battleship
      • Backends
      • Project: Where's Waldo?
      • Project: All-Star
      • Next steps
    • NodeJS
      • Project: Going to school
      • Project: Passing the test
      • Express
        • Templates and middleware
        • CRUD and MVC
        • Project: Message board
        • Routes
        • Displaying data
        • Forms and deployment
        • Project: Inventory
      • Authentication
      • Security
      • Project: Clubhouse
      • APIs
      • Securing an API
      • Project: Blog
      • Testing
      • Testing with a database
      • Project: Social network
    • React
      • Props and State
      • Render lists and handle inputs
      • Project: CV
      • Lifecycle methods
      • Hooks
      • Project: Memory card
      • Router
      • Project: Shopping cart
      • Advanced concepts
    • Ruby
      • Installation
      • Data types
      • Variables
      • Input and Output
      • Conditionals
      • Loops
      • Arrays
      • Hashes
      • Methods
      • Enumerables
      • More enumerables
      • Nested collections
      • Blocks
      • Pattern matching
      • Debugging
      • Project: Caesar cipher
      • Project: Substrings
      • Project: Stock picker
      • Project: Bubble sort
      • Object oriented programming
      • Project: Tic Tac Toe
      • Project: Mastermind
      • Serialization
      • Project: Event manager
      • Project: Hangman
      • Computer Science
        • Recursion
        • Project: Merge Sort
        • Data structures and algorithms
        • Project: Linked Lists
        • Project: Binary Search Trees
        • Project: Knight Travails
      • Testing
      • RSpec
      • Project: Four in a row
      • Git
      • Project: Open Source
      • Project: Chess
      • Next steps
    • Ruby on Rails
      • Using Heroku
      • Installing Rails
      • Basics
        • Routing
        • Controllers
        • Views
        • Asset pipeline
        • Deployment
        • Project: Blog
      • Active Record
        • Project: Upvote
      • Forms
        • Cookies, sessions, and authentication
        • Project: Password
      • Advanced forms and Active Record
        • Associations
        • Project: Private Events
        • Callbacks
        • Menus, helpers and nested forms
        • Project: Ticket agent
      • APIs
        • External APIs
        • Project: Animals
        • Project: Photo widget
      • Mailers
        • Project: Confirmation
      • Advanced topics
        • Action Cable
      • Project: Social network
      • Next steps
  • Getting hired
    • Preparing to find a job
      • Plan a strategy
      • What companies want
      • Get yourself together
      • How to prepare
      • Project: Make your website
    • Applying and interviewing
      • Qualifying leads
      • Project: Make your resume
      • Applying for jobs
      • Preparing for an interview
      • Handling an offer
      • Final words
  • Maintained by
    • wbnns
  • License
    • CC BY-NC-SA 4.0 © 2022
Powered by GitBook
On this page
  • Introduction
  • Learning outcomes
  • Assignment
  • Additional resources
  1. Deep dives
  2. Ruby
  3. Computer Science

Data structures and algorithms

Learn more about data structures and basic algortihms.

Introduction

The basic idea of a data structure is to store data in a way that meets the needs of your particular application. You might be inclined to store a particular kind of data in one giant array, but it would be rather time consuming to locate a specific value if you had a significant number and depth of items. So you need to look to other options.

Depending on the application, there are a batch of other basic data structures available to help you out. The differences between them typically have to do with trade-offs between how long it takes to first populate the structure, how long it takes to add or find elements, and how large the structure is in memory.

We'll save the specifics of data structures for more computer-science-oriented courses, but this introduction should again expand your toolbox slightly so you can identify and solve certain problems where plain old Arrays, Hashes and Sets don't quite cut it. New structures and strategies will be particularly relevant, for instance, when you're trying to search through a large batch of data for a particular value or plan out a strategy several moves in advance.

You've already had a brief introduction to algorithms over some of the other lessons and you even got to write your own Merge Sort algorithm in the last project. You'll find that sorting algorithms are quite common. Another major area for algorithms is in search, where milliseconds count. When you're searching through enormous troves of data, the quality of your search algorithm is incredibly important. Traversing a data tree looking for a particular element is a related problem that's common in data intensive applications.

Luckily for you, these complex algorithmic problems have all been solved many times in the past. Understanding how they are solved will give you some great tools to apply to other (similar) problems on your own. Algorithms are really just ways of solving problems systematically. In this brief introduction, we'll focus on a couple of algorithms that you may run into when coding on your own -- breadth-first-search and depth-first-search.

Learning outcomes

Look through these now and then use them to test yourself after doing the assignment:

  • What is a data structure?

  • What is a stack?

  • What is a queue?

  • What's the difference between a stack and a queue?

  • What is a stack useful for?

  • What is a queue useful for?

  • What's the best way to implement stacks and queues in Ruby (hint: think simple)?

  • Why bother having many different search algorithms?

  • What is breadth-first-search (BFS)?

  • What is depth-first-search (DFS)?

  • What situations would you want to use BFS?

  • What situations would you want to use DFS instead?

  • When would BFS be impractical?

Assignment

  1. Finally, learn about breadth-first search and depth-first search of binary search trees from this series of videos on YouTube:

Additional resources

This section contains helpful links to other content. It isn't required, so consider it supplemental for if you need to dive deeper into something.

PreviousProject: Merge SortNextProject: Linked Lists

Last updated 4 years ago

Glance over the for a high level overview of things.

Learn about basic algorithms from Coursera's Algorithms course in . The first 10 minutes are really the meat of the introduction to algorithms, the rest gets more mathematical (if you're so inclined).

Read for another basic look at what algorithms are.

Learn about how binary search works by watching from Harvard's CS50 on YouTube.

Now, we're going to focus on learning about binary search trees. Start by watching to learn how a binary search tree is constructed from an unordered array.

Next, learn about the principles of queues and stacks, which are concepts used in breadth-first search and depth-first search, respectively, by watching .

that discusses how to construct a binary search tree from an unordered array.

on the relative strengths of BFS and DFS.

Wikipedia entry on Data Structures
this video
What is an Algorithm and How Does it Make You a Better Programmer
this video
this video
this video
Binary tree traversal
Breadth-first traversal
Depth-first traversal
Khan Academy's great Algorithms Course
Stanford's Coursera 4-Part Algorithm Course
Visualizing Algorithms from Mike Bostock
Another free course on algorithms by Udacity
A brief note on putting Sorting, Tries and Heaps into Ruby, by Ilya Grigorik
A more detailed video on stacks and queues
An article
A stack overflow discussion