Hands-On Data Structures and Algorithms in Rust
4.8 (4 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
67 students enrolled

Hands-On Data Structures and Algorithms in Rust

Learn about common and useful Data Structures and Algorithms
4.8 (4 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
67 students enrolled
Created by Packt Publishing
Last updated 6/2020
Current price: $74.99 Original price: $124.99 Discount: 40% off
2 days left at this price!
30-Day Money-Back Guarantee
This course includes
  • 7 hours on-demand video
  • Full lifetime access
  • Access on mobile and TV
  • Certificate of Completion
Training 5 or more people?

Get your team access to 4,000+ top Udemy courses anytime, anywhere.

Try Udemy for Business
What you'll learn
  • How Rust can help you keep your memory access safe and effective
  • How we can use Rust to build Generic Algorithms that we can use again and again across our codebase
  • Greedy, dynamic, and Iterative algorithms and when to use them
  • Different data structures such as Maps, Trees, and Linked lists, and when it is appropriate to use them.
  • Why and how an Entity Component System separates the different parts of the object into different storage areas
  • How we can build files that work like simple databases using BTrees
  • How we can run our programs even faster-using Multithreading
Course content
Expand all 49 lectures 06:55:25
+ Getting to Grips with Rust and its Syntax
11 lectures 01:23:03

This video provides an overview of the entire course.

Preview 05:30

We need a mechanism to run the code we are writing. So, we need to get the Rust compiler installed.

   •  Download Rustup.sh

   •  Run rustup

   •  Build a simple Hello World project

Install Rust and Running a Simple Program

In order to do anything in programming in Rust, we need ways to organize our data.

   •  Introduce the Struct

   •  Introduce the Enum

   •  Get printouts of each showing what they can do and hold

Build complex structures with Struct and Enum

Some functions may need to let the caller know there was a problem. How can we pass that message back?

   •  Introduce the Result and Option enum types

   •  Demonstrate how these works generically

   •  Show a function returning an Error

Results and Options

Every program needs to perform some task multiple times. How can we do that in Rust?

   •  Introduce the loop, while, and for

   •  Show how an iterator works by returning an option

   •  Demonstrate a for loop on a new iterator type

Looping Mechanisms in Iterators

Programs often need to grab memory to be able operate. Can we understand when they need to?

   •  Introduce the stack

   •  Demonstrate the stack in a set of function calls

   •  Show how the stack can be avoided in tail recursive situations

Stack Data Structure in Rust

Making sure that our code does not write to something it should not, is tricky. How can we work with the Rust compiler?

   •  Show how an object can be copied between variables

   •  Show that in order to change a variable which need to make it mutable

   •  Show how these two features interact

Mutability, Variables, Copying, and Cloning

Rust protects us from pointing to things that do not exist anymore. How can we work with this?

   •  Introduce the borrow notation for pointers

   •  Show how when you have a pointer to something, you cannot change it elsewhere

   •  Demonstrate that mutable pointers require mutable objects

Use Memory Effectively with Pointers and Lifetimes

How do we handle objects where we do not know how big they will need to be?

   •  Demonstrate how a pointer is needed to make a linked list

   •  Show how Box creates that pointer

   •  Build Dynamic arrays using vec

Own Memory on the Heap with Box, String, and Vecs

In this video, we will look at the difference between Str and String.

   •  Understand their differences

   •  Explore their uses

Difference Between Str and String

How can we make our code available to others to use?

   •  Show how to get a token from crates

   •  Show how to set up our crates for upload

   •  Show how to upload our crate and check it is uploaded

Uploading to Crates
Test your knowledge
8 questions
+ Algorithm Complexity and Sorting Algorithms
7 lectures 57:18

What is the simplest way we can sort a list?

   •  See if each element should swap left in the vec

   •  Repeat until sorted

   •  Calculate how long this takes to run and if we can save time

Preview 09:56

Can we go faster when sorting data?

   •  Introduce the concept of divide and conquer

   •  Show how to split the data into two smaller sections to sort

   •  Bring those two small sorted lists together in linear time

Divide and Conquer Sorting with Merge Sort

Can we do it without needing to grab so much memory?

   •  Show how to pivot data around a single item

   •  Sort the two sides separately

   •  Test that it works

Sorting in Place with Quick Sort

How can random numbers help us build faster solutions?

   •  Show that quick sort worst case is n squared

   •  Create a random generator

   •  Add that to our quick sort and show that removes the worst case

Improving Our Quick Sorter with Pseudo Random Numbers

Can we use all our processors to speed up the operation?

   •  Introduce threading

   •  Explain why this case unsafe and why it must

   •  Show how this works across all the threads

Spiting Quick Sort Using Multiple Threads

Can we limit the number of threads we use to solve a problem?

   •  Introduce the Rayon library

   •  Show how the join method uses threads

   •  Implement quick sort to use join

Let Rayon Speed It Up with Work Stealing

How can we avoid performing the same calculation?

   •  Show how a naive fibonacci calls the same function many times

   •  Show how iterative solutions avoid that

   •  Show how by storing previously calculated results, we can save ourselves a lot of calculation

Cut the Right Corners to Increase Your Speed with Dynamic Programming
Test your knowledge
8 questions
+ Building Linked Lists and Binary Trees
7 lectures 01:19:12

How can we store lists in the simplest way possible?

   •  Show how we can use Box to make a list

   •  Append and remove elements

   •  Show how linked list is fast for the front but not the back

Creating a Linked List

How can we access both ends of a linked safely?

   •  Introduce Rc and Weak

   •  Show why one direction must be Weak

   •  Add and remove elements from both ends of the list in linear time

Viewing Data in Both Directions with Doubly Linked Lists

How can we add data to a list in just Log(n) time?

   •  Introduce trees that have two branches

   •  Show how to add data to a list

   •  Show how to read data back in order

Building a Binary Tree to Efficiently Store and Sort Data

What if we add data in a sorted manner, doesn’t that create just a linked list?

   •  Show that adding sorted data wastes the binary tree

   •  Demonstrate tree rotation

   •  Use stored heights to calculate when to rotate the tree

Converting Binary Tree to a Binary Balance Tree

How can we use random data to quickly find tree elements?

   •  Introduce the idea of a layered linked list

   •  Show how the random data allows us to access parts quickly

   •  Begin building the skip list

Learning About Skip Lists and Their Potential Advantages

Can we finish this skip list?

   •  Add a layer tracker to the front of the list

   •  Show how we can flip a coin to add layers as needed

   •  Test our skip list

Managing the Heights of a Skip List

How can Trees be used to compress data?

   •  Create a Huffman tree

   •  Show how this puts frequent elements near the top

   •  Show how to compress and decompress a string of data

Computing Huffman Encoding and to Compress Data
Test your knowledge
8 questions
+ Model Real Situations as Graphs of Connected Nodes
6 lectures 50:05

What is the best way to store a graph?

   •  Introduce different options for storing a graph

   •  Show the costs and benefits of each

   •  Select one for the rest of this section

Consider the Options for Creating and Storing Graphs

In order to test it, our graph needs data.

   •  Make sure our graph has enough add and delete methods

   •  Add data to the graph

   •  Look at the data we have added and how it works

Filling the Graph

How can we store routes in a composable way?

   •  Show how Rc can have many clones

   •  Show many routes with the same beginning

   •  Get our routes printable

Route Structure

How can we find the shortest path between two points on the graph?

   •  Add all paths from the start node to a list

   •  Take the shortest path on the list and repeat from there

   •  Do not search from the node we have already searched from

Finding the Shortest Path

How can we solve complicated problems on such as the Traveling Salesman on graphs?

   •  Introduce Traveling Salesman

   •  Introduce greedy algorithms

   •  Try a greedy algorithm to solve Traveling Salesman

A Greedy Solution to the Travelling Salesman

Can we do better than a greedy solution?

   •  Introduce an iterative method

   •  Generate a random path

   •  Make random changes only keeping improvements

Improve the Solution Using Iterative Methods
Test your knowledge
8 questions
+ Getting Constant Time Data Access Using HashMap
6 lectures 40:52

Can we store data with constant time access?

   •  Introduce the idea of a HashMap

   •  Show how a set of buckets can be selected from

   •  Explain we are going to build this

What a HashMap Is and Why and When Do We Use Them

How do we choose a random, but consistent bucket?

   •  Introduce the idea of a Hasher

   •  Show how the Hash and Hasher Traits work together

   •  Build a Hasher

Building HashMap from Scratch

Can we create a functioning bucket list?

   •  Create a list of buckets that stores data based on its hash

   •  Show how we can add and remove data from this list

   •  Test it

Building a Bucket List for the HashMap to Use

How can we get our HashMap to grow without needing to break our const time rules?

   •  Create a wrapper around two Bucket Lists

   •  When one bucket is too full, create a new bigger one

   •  Move the data across in small chunks

Finishing the HashMap

Can we know for sure our HashMap does what it should?

   •  Build tests for inserting into our HashMap

   •  Build tests for the growth of our HashMap

   •  Show that we need to double the size every time

Testing and Improving Our HashMap

When should we use which kinds of maps or sets?

   •  Show how Rust optimizes maps to act as sets

   •  Show when each kind of map is more appropriate

   •  Show when each kind of map is less appropriate

HashMap versus BTreeMap
Test your knowledge
8 questions
+ Organizing Your Data by Type with Entity Component Systems
6 lectures 51:14

How can we organize our data for real time processing on modern systems?

   •  Introduce ECS

   •  Show how it separates the components of an entity across stores

   •  Explain how systems then operate on the data

Understand What an ECS Is and How It Differs from Traditional Structures

How can me make sure we do not treat a new element as an old one?

   •  Introduce generation tracking

   •  Show how we can do this all in constant time across many adds and drops

   •  Build a complete generation manager

Creating an ID Generator

How do we store our data so that we cannot grab the wrong element by mistake?

   •  Show the kinds of operations a store need

   •  Show how we can use a Vec store with marked generations

   •  Show how we can loop over the elements in a store

Creating Data Stores

How do the systems of ECS interact with each other?

   •  Show how simple systems can loop over the data they need

   •  Show how more complex systems can loop in different ways

   •  Build all the systems needed for a simple CLI game

Building ECS Systems

How can we run this ECS game?

   •  Show how to access the terminal and raw input

   •  Show how we can count passes

   •  Show how we can manage quitting our application

Combining It All into a Simple CLI Game

Are there any tools to make doing ECS easier?

   •  Introduce the Specs crate

   •  Show a simple example from the Specs docs

   •  Explain each part of the code required

Introduction to Specs
Test your knowledge
8 questions
+ Persistent Storage Data Structure
6 lectures 53:41

How can we maintain persistent data with fast access?

   •  Explain the new problems of data size when working across files

   •  Prepare the crate with needed libraries

   •  Prepare an error type to handle the Blob store we are building

Creating a Blob Data File

How can we make any data work as a string of bytes

   •  Create a Blob store type

   •  Show how Serdes and bincode make conversions possible

   •  Test our Blob object

Converting Any Data Size to Byte String

How can we access the file with Random Access?

   •  Show how we can create a file

   •  Set up the control data for a new file

   •  Open an existing file and read the control data

Creating a Blob Store

How can we add data to the file?

   •  Show how we can add data with marked length

   •  Show how we can find the right place to add it

   •  Test we can add data

Adding to the Blob Store

How can we read data from the file?

   •  Show that we can find the data following the same path

   •  Show that we can convert it back to the right type

   •  Test we get the right data back

Reading from the Blob Store

How can we remove data from the file?

  • Show that when we remove data, we now have two blocks that need to be joint

  • Join the two blocks

  • Test that remove works as expected

Removing an Element from the Blob Store
Test your knowledge
8 questions
  • No Rust programming knowledge is required as we will be covering the basics at the beginning.

Rust is a modern systems programming language designed with safety to simplify the development of large, complex software projects. Data structure and Algorithms are key to help in the collection and organization of the data for performing operations on the data and set instructions/logic to accomplish tasks in these projects. This course will be your guide for implementing classic data structures and algorithms in Rust, helping you to get up and running as a confident Rust programmer.

You will begin with a primer to Rust and its syntax. You will then explore the language of Time and Memory complexity by comparing different sorting methods. You’ll then learn about Lists and Binary Trees, implement them, and compare them, to show the advantages and use cases of each. Next, you will cover different algorithms in-depth such as sorting, graph, dynamic programming, greedy, divide and conquer, and more. You will learn how counterintuitive techniques can actually make it easier to build scalable projects!

By the end of the course, you will have a sound knowledge of the key data structures and algorithms in Rust to confidently implement them in your applications.

About the Author

Matthew Stoodley is a programming expert and enthusiast, who was drawn to learn about Rust and master its features initially due to its low power usage and memory safety capabilities. He primarily uses Rust to build board games.

In addition, he also possesses several years of experience in Go, PHP, and JavaScript.

Who this course is for:
  • This course is for programmers who want to get to grips with all data structures and algorithms in the latest version of Rust programming language, to help organize your code better and accomplish predefined tasks.