How Data Structures & Algorithms are Actually Used

Summary

In this informative video, Forest explores the practical applications of algorithms and data structures in real-world scenarios, such as social media feeds and AI projects. He demonstrates how posts are stored in a PostgreSQL database and retrieved in an array of objects, then sorted using algorithms like Timsort. Forest also dives into the game of Soom, illustrating the use of data structures like hashmaps, arrays, and sets to solve puzzles efficiently. The video concludes with a discussion on BFS (Breadth-First Search), showcasing its implementation in a Soom solver, providing a hands-on look at how these concepts are applied in programming and AI.

Takeaways

• 😀 The video discusses the practical applications of algorithms and data structures, particularly in the context of a social media application.
• 🔍 The speaker uses a social media feed as an example to illustrate how data structures like arrays and databases are utilized to store and retrieve posts.
• 🗃️ Posts in the example are stored in a PostgreSQL database, with each post represented as a row in a table containing various attributes like ID, title, content, etc.
• 📉 The video explains how posts are fetched from the database, sorted by their creation date in descending order, and then used in the application's frontend.
• 🔄 The process of mapping through the posts ensures consistency of data types and structure before they are displayed in the feed.
• 🏆 The video also touches on sorting algorithms, mentioning Timsort used in JavaScript engines like V8 and Spider Monkey, and how they are applied to order posts by upvotes.
• 🤖 The speaker mentions a project involving AI, emphasizing that AI encompasses more than just machine learning, and discusses its application in various fields.
• 🎁 There is a giveaway for a GTX 490 GPU by Nvidia, which the audience can enter by attending a GTC 2024 session and following specific instructions.
• 🧩 The video introduces 'Soom', a puzzle game that involves moving boxes to designated spots, which serves as a practical example for demonstrating algorithms and data structures.
• 🗺️ The game's board state is captured using specialized data structures like hashmaps for character-to-bitfield mapping and arrays for the game board layout.
• 🔍 The speaker explains the use of sets in the game to track movable boxes and the player's position, and how these data structures change with each move in the game.
• 🌐 The video concludes with an explanation of the BFS (Breadth-First Search) algorithm used in the Soom solver, detailing its implementation and how it explores the game's state space.

Q & A

What is the main topic discussed in the video?

The main topic discussed in the video is the application of data structures and algorithms in real-world scenarios, specifically using examples from social media apps and the game Sooon.

How are posts stored in a social media application according to the video?

Posts in a social media application are stored in a PostgreSQL database within a table, where each row represents a single post containing information such as unique ID, created at, updated at, user ID, title, content, URL, and image.

How does the video describe the process of fetching and displaying posts in a social media feed?

The process involves calling the database to fetch posts, ordering them in descending order to have the most recent posts at the top, and then returning the data for use in the application's frontend code.

What is the role of arrays in the context of the social media feed example?

Arrays are used to store the fetched posts as objects, where each object contains all the data for a single post, which is then used throughout the frontend code of the application.

How is the sorting of posts by upvotes achieved in the video's example?

The sorting is achieved by fetching the posts from the database and then using a sorting algorithm to order the array of objects based on the vote count, which is a value within each object.

What sorting algorithm is mentioned in the video, and in which JavaScript engine is it used?

Timsort, a hybrid sorting algorithm derived from merge sort and insertion sort, is mentioned. It is used in the V8 engine, which is found in Chrome and Node.js.

What is the significance of the Sooon game in the context of the video?

The Sooon game is used as an example to demonstrate the practical application of data structures and algorithms, particularly in solving puzzles and navigating through game states.

What data structure is used to represent the game board in the Sooon game example?

An array is used to represent the game board, as it provides a well-organized, fixed-size container that matches the 2D setup of the Sooon puzzle.

How does the video explain the use of a hash map in the Sooon game?

The hash map is used for bi-directional mapping between characters seen in the game's bitfield codes and the actual bytes, allowing for quick finding and updating of items.

What does the video say about the use of sets in the Sooon game?

Sets are used to keep track of the goals and boxes, as well as the player's position on the game board, allowing for easy addition, movement, or checking of these positions.

Can you explain the role of the BFS algorithm in the Sooon game solver presented in the video?

The BFS (Breadth-First Search) algorithm is used in the Sooon game solver to explore all possible moves from a given state before moving on to the moves that result from those moves, covering the search space layer by layer.

What is the purpose of the backtrack hash map in the BFS solver for the Sooon game?

The backtrack hash map stores every move the solver makes and where that move came from, allowing the solver to trace all the steps back and provide a final solution once the correct path is found.

Outlines

00:00

📚 Real-World Application of Data Structures and Algorithms

In this paragraph, the speaker, Forest, discusses the practical use of data structures and algorithms, particularly focusing on social media applications. He explains how posts are stored in a PostgreSQL database and retrieved in an array of objects sorted by the most recent first. Forest then elaborates on how these posts are used within the application, including mapping through the array to ensure consistent types and returning the data for use in the application's front end. He also touches on the use of sorting algorithms, such as Timsort, which is used in JavaScript engines like V8 and Spider Monkey, to order posts by upvotes. The paragraph concludes with an introduction to how arrays and sorting algorithms are utilized in real-world applications, setting the stage for further exploration of data structures and algorithms in AI and other projects.

05:03

🎮 Solving Puzzles with Data Structures in a Java Application

The second paragraph delves into the application of data structures in solving puzzles, specifically using a Java application built by the speaker. The application in question is a puzzle game similar to 'Soom,' where the objective is to move boxes to designated spots without blocking access to others. Forest introduces the concept of a board state, captured using specialized data structures like hashmaps for character-to-bitfield mapping and arrays for the game board layout. He also mentions the use of sets to track the positions of movable boxes and the player. The paragraph further explains how each move in the game transforms the data structure, leading to visual changes on the screen. Additionally, Forest discusses the implementation of the Breadth-First Search (BFS) algorithm in the game's solver, which uses a queue implemented as a linked list to explore all possible moves from a given state before moving to the next layer of moves.

10:03

🔍 Deep Dive into BFS Solver and Data Structure Transformations

In the final paragraph, the focus is on the intricacies of the BFS solver and how it interacts with various data structures during the puzzle-solving process. Forest describes the constructor of the BFS solver class, which initializes the current board state, a hash set to track seen puzzle states, and a backtrack hashmap to record every move made by the solver. The search algorithm is implemented using a queue, ensuring a layer-by-layer exploration of the search space. The paragraph concludes with an explanation of how valid moves are logged in the backtrack hashmap and added to the queue for further exploration. This comprehensive look at the BFS solver provides insight into the mechanics behind solving puzzles using data structures and algorithms.

Keywords

💡Algorithms

Algorithms are a set of rules or procedures for solving problems or performing tasks. In the context of the video, they are essential for understanding how data is processed and manipulated. The script discusses the use of sorting algorithms, like Timsort in JavaScript and Python, which are used to order data, such as posts in a social media feed by upvotes. The video also mentions the use of algorithms in AI and the game of Soom, where algorithms like BFS (Breadth-First Search) are used to solve puzzles.

💡Data Structures

Data structures are specialized formats for organizing, storing, and manipulating data. They are fundamental to computer science and software development. The video script mentions arrays, hashmaps, and sets as examples of data structures used in applications like social media feeds and the Soom game. For instance, an array of objects is used to store and manage posts in a feed, while hashmaps are used for quick look-up of game board states in Soom.

💡Social Media App

A social media app is a software application designed for users to create and exchange content or to participate in social networking. The video script uses a social media app as an example to illustrate how data structures and algorithms are applied in real-world scenarios. It explains how posts are stored in a database and then fetched, sorted, and displayed to users, highlighting the importance of choosing the right data structures and algorithms for efficiency.

💡PostgreSQL

PostgreSQL is a powerful, open-source object-relational database system. In the video, it is mentioned as the database system used to store posts in a social media application. Each post is stored as a row in a table with various attributes like unique ID, title, content, and image, demonstrating how databases are integral to managing and retrieving data for applications.

💡Array of Objects

An array of objects is a data structure where an array contains multiple objects, each object representing a single entity with various attributes. In the script, this concept is used to explain how posts in a social media feed are stored and managed. Each post is an object with properties like ID, title, content, and image, which are then sorted and displayed to the user.

💡Sorting Algorithm

A sorting algorithm is a method for arranging the elements of a list or array in a certain order. The video script explains how sorting algorithms are used to order posts in a social media feed by the number of upvotes. It also mentions Timsort, a hybrid sorting algorithm used in JavaScript and Python, which is an example of how sorting algorithms play a crucial role in organizing data for user interfaces.

💡Breadth-First Search (BFS)

Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at the tree root and explores all the neighboring nodes at the present depth prior to moving on to nodes at the next depth level. In the context of the Soom game, BFS is used as a solver to find a path for moving boxes to their designated spots by exploring all possible moves layer by layer.

💡HashMap

A HashMap is a data structure that implements an associative array abstract data type, a structure that can map keys to values. In the video, HashMaps are used for quick look-up and updating of game board states in the Soom game. The script mentions a HashMap for character-to-bitfield mapping, which is crucial for efficiently managing the game's state.

💡Sets

In the context of data structures, a set is a collection that does not allow duplicate elements and provides high efficiency for adding, removing, and checking for an item's presence. The script mentions the use of sets to keep track of goals and movable boxes in the Soom game, ensuring that there are no conflicts in positions and allowing easy management of game state changes.

💡AI and Machine Learning

Artificial Intelligence (AI) refers to the simulation of human intelligence in machines that are programmed to think like humans and mimic their actions. Machine Learning is a subset of AI that enables machines to learn and improve from experience without being explicitly programmed. The video script touches on the broader concept of AI, mentioning that it's not limited to machine learning and that the project discussed will showcase various data structures and algorithms used in AI applications.

Highlights

Introduction to the importance of algorithms and data structures in real-world applications.

Explanation of how posts in a social media app are stored and retrieved using a PostgreSQL database.

Demonstration of fetching posts from the database and ordering them by the most recent first.

Use of arrays of objects to store and manage post data in a social media feed.

Mapping through the array to ensure consistent data types and structure.

Front-end implementation showing how post data is utilized in a social media app interface.

Sorting posts by upvotes using a sorting algorithm, with a discussion on different JavaScript engines and their sorting methods.

Real-world application of arrays and sorting algorithms in social media platforms.

Introduction to the SooN solver Java application, built to showcase the use of various data structures and algorithms.

Discussion on the use of arrays, hashmaps, and sets in the SooN puzzle game to manage game state and elements.

Explanation of the board state and how it is captured using specialized data structures.

Breadth-First Search (BFS) algorithm implementation in the SooN solver and its role in exploring game states.

Use of a queue implemented as a linked list for efficient state exploration in BFS.

Description of the backtrack hashmap used to store and trace the solver's moves for finding the solution.

Involvement in GTC 2024, the leading AI conference, and the giveaway of an Nvidia GTX 490 GPU.

Highlight of the AI-assisted developer tools, AI for agriculture, and Omniverse content production as topics of interest at GTC 2024.

Summary of the practical applications of data structures and algorithms in the SooN puzzle game and their relevance to AI.

Transcripts

all right hey my name is Forest welcome

back so lately I've talked about some

algorithms and I've talked about some

data structures I've shown what they

look like how the code behind them works

why it's important to choose right ones

and mentioned how they're used but it's

been brought to my attention that I

haven't shown how they're used in real

world applications take a social media

app for example every single one has a

feed a feed of whatever content that

that social media application that

platform provides and this instance it's

a bunch of posts that are used as

examples because I'm still working on

this but are these posts stored in a

data structure kind of kind of not

really but kind of we have to work our

way to it as you can see the posts are

actually stored in an array of objects

or at least when they're being used see

they're stored actually in the database

in this instance it's a postgressql

database with all of the posts being

stored in a table and this table has all

of the information each row is a single

post and it has the unique ID created it

updated at the user ID for who created

it the title content URL image you get

the idea but then we need to use this so

the way we use it is that we call to our

database and we fetch those posts from

our database and we put them in

descending order so the most recent is

up top and then once we do that we

return the data for whenever this

function is being called like right here

so we are calling our fetch posts and

storing all of that data remember what

it's returning into our array of objects

just like you can have an array of

strings where each value is a string or

an integer each one here is an object so

each object has all of that post data

that you need and then we map through it

just to make sure that our types are all

consistent and things of that nature and

then what we're doing here is returning

it by passing it through posts and the

post feed as you can see right here post

is the parameter that's being passed

into Post Feed and then we are using it

throughout our code and however we see

fit with this being that front end code

that you see here so within each post we

need to identify the user and that

user's username and profile the title

the content the upvotes and that's what

we do down here as well we get the user

posts image we get the username we get

when it's created at that's what this

data is here the post title as you can

see so on and so forth so that's how an

array would be used in an instance like

this but what about an algorithm so as

you can see here we have home that's

where we're at right now and you can

notice that we have these being upvoted

one one one and then there's a zero down

here and then there's a one right here

if we go to most upvoted you can now see

that all of those that are actually

upvoted by me the sole user are at the

top because it's ordered from the most

upvoted down but how do we do that it's

actually very very simple so what we do

is we do the same thing as before we

fetch the post so remember we're using

this we're calling to our database and

bringing in all of that data storing it

in an array of objects but then we are

sorting that array of objects based on

vote count which is one of the values

within the object as you can see right

here and this right here is a sorting

algorithm now in JavaScript it depends

on what engine you're using so if you're

using Chrome or node.js that uses the V8

engine so that uses timsort which is a

hybrid sorting algorithm derived from

merge sword and insertion sword this is

also what python used is actually

developed for python however if it's in

Firefox which uses the spider monkey

engine then it uses variations of merge

sort and then Safari uses JavaScript

core engine whereas the specific

algorithm used can vary as far as I know

at least so right there is a real world

use case of how arrays array of objects

in this instance are used in an actual

application as well as how sorting

algorithms are used and I'm really glad

we could do that one because it not only

fits the criteria of that original

comment where wasn't really asking about

real world applications but more so how

you can utilize and use data structures

and algorithms in our own projects as he

said but it also hit that other criteria

of how they're using railroad

applications like a social media

application whereas this one that we're

about to discuss not so much but it does

fit the how you can use them in your own

projects and it translates outward but

not like it lays the foundation it allow

like it allows you to learn about data

structures and algorithms and how

they're utilized in ai ai is very broad

it doesn't just have to be machine

learning by the way and things of that

nature but this project will showcase

arrays hashmaps array lists link lists

hash sets and how they're used as well

as DFS and BFS and AAR which are three

of the algorithms that I went over in my

three types of algorithms video and all

of this in my sooon solver Java

application that I built about 7 years

ago in my intro to artificial

intelligence class wait what happened oh

yeah yeah yeah yeah yeah GTC 2024 is

about to start March 18th to 21st it's

the number one AI conference for

developers and your boy will be there

live and in person well not live but in

person I'll be attending a handful of

Tours workshops and of course the main

keynote presented by the CEO of Nvidia

himself Jensen hang who is also the same

man who signed this GTX 490 GPU that I'm

giving away to one of y'all didn't see

that coming did you all you have to do

to enter is attend a GTC 2024 session

virtually is obviously fine and send me

a screenshot of your session to prove it

just follow these instructions register

for GTC using my link in the description

box it's free to attend virtually and if

you've already registered that's

perfectly fine then as you're attending

a GTC session take a screenshot and fill

out the Google form also linked below

and while not part of this giveaway it

may or may not it won't give you a

better chance to win the GPU if you sign

up to my newsletter devotes also free

devotes daily.com that'll be the third

link in the description we'll be

covering everything mentioned at this

event that developer should know and

summarized beautifully and concisely for

y'all if you're curious about my top

choices that I'll be attending those are

linked below as well and include AI

assisted developer tools for Accelerated

Computing AI for agriculture because

farmer and implementing Omniverse to

produce cinematic content that one seems

wildly interesting and if you're going

in person and you see me feel free to

say what's up all right now back to the

video so the sooon silver you've

probably played soan one way or another

without even realizing it especially if

you played Pokémon and you had to move

all of those rocks in a certain order to

get them where they need to go so you

have a path that's sooon that's

literally the game sooon I think I'm

pronouncing that right is a puzzle game

where you push boxes to their designated

spots but you have to figure out which

boxes to push where and in what order so

you don't block yourself off from the

rest of the boxes a beautiful game to

practice some algorithms on and we

really get intricate with some of these

data structures and it all starts with

the board State this is a snapshot of

where the walls boxes goals and the

player are located on the game board

that is these are bit fields and then we

capture this snapshot of the game using

a specialized data

structure take a look here so we use

hashmaps and we have the hashmap for

exactly what it says here character to

bitfield BU mapping so it's for biral

mapping between the characters you see

in their bitfield codes because well

hashmaps are great at quickly finding

and updating these items so as you can

see we have a new hashmap chart of field

with a character and a bite and these

are our bytes as you can tell and these

are our characters that will

represent said bites and you can see a

little bit more of how that works here

but then down here we use arrays so the

array it's in charge of holding the

entire game board's layout which is

really just a it's a big grid that keeps

everything in its place the walls boxes

everything and we chose an array because

it's well organized and provides a fixed

siiz container that perfectly matches

the 2D setup of this Soom puzzle

meanwhile we have sets for the goals in

the boxes to keep an eye on where the

movable boxes in the player are because

a box and a player cannot be in the same

location at the same time and of course

sets they allow us to really easily add

move or check these positions and then

with every move or push you make in the

game you're essentially changing this

data structure which leads to

Transformations that you see on the

screen which you can see how that works

in these methods down here so here we're

returning whether or not the player can

move in a certain direction down here

we're returning the new board state

after moving in a certain direction down

here we're returning true if the next

move has the input bit field that

otherwise it'll be false and you get the

idea now if we want to come over to BFS

this is one of our many solvers let's

get that out the way and as you know BFS

is Brett the first search so it's a

layer by layer exploration strategy that

examines all possible moves from a given

node before moving on to the moves six

accessors or next layer so our BFS

solver here inherits from abstract

solver which as you can see over here

sets up a framework for a search based

puzzle solver like these this is this is

where the real magic happens here here's

our Constructor for this class we're

first passing in that board state which

will be assigned to current state here

we're preparing a list well technically

it's a set a hash set as you can see

here to keep track of all the puzzle

States we've already seen and here is

our backtrack hash map which stores

every move the solver makes and where

that move came from this way once it

finds the solution it can trace all of

those steps back so you have a final

solution after the fact otherwise then

you do it once you forget how to do it

you have to do it again doesn't make

sense and down here is where our search

algorithm is implemented with the use of

a q determining the order which states

are explored so first in first out

exploring all possible moves from a

given State before moving on to the

moves that result from those moves so

covering the search space layer by layer

as BFS should and you can see how this

translates back over in our BFS solver

this is it it's convenient but it's

annoying when I just want to highlight

something in GitHub so in our BFS solver

class we initialize with the board State

set and our queue being implemented as a

linked list because we'll be adding and

removing many states as we explore the

puzzle and because link list in Java

comes with

methods ready to unq and DQ by default

so it just made it easier for me that's

that's really why I used it and down in

this method we create an array list of

valid moves where when we move we log it

in the backtrack hash map this keeps

track of where each move came from and

then we add the move to the que for

further exploration that without really

going down like a crazy rabbit hole is

that's all I got for you I don't know if

I answered the question I often times

stray uh but I have fun doing it so take

the video for what it is feel free to

subscribe if you enjoyed the content and

you want to see more like this again I'm

forest and I'll see you in the next one