How Data Structures & Algorithms are Actually Used
Summary
TLDRIn 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
📚 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.
🎮 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.
🔍 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.
Mindmap
Keywords
💡Algorithms
💡Data Structures
💡Social Media App
💡PostgreSQL
💡Array of Objects
💡Sorting Algorithm
💡Breadth-First Search (BFS)
💡HashMap
💡Sets
💡AI and Machine Learning
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
5.0 / 5 (0 votes)