«
»
▶
Lecture Copilot
Lectures
Ask
Exam prep
Help
Sign in
← Data Structures & Algorithms
L2
Learn DSA Visually
Ask the lectures
Every answer cites the moment it comes from. Click a citation to jump there.
Your question
Ask
00:00
Introduction to Data Structures and Algorithms
04:13
The Concept of Arrays and Time Complexity
10:57
Linked Lists: Singly and Doubly
17:15
Stacks and Queues
25:12
Priority Queues and Heaps
28:24
Hash Tables and Sets
32:52
Trees, Binary Search Trees, and Tries
42:47
Graphs and Their Representations
48:04
Searching and Sorting Algorithms
56:15
Recursion and Backtracking
1:01:28
Graph Traversal Algorithms: DFS and BFS
1:04:47
Dijkstra's Algorithm and Greedy Approach
1:10:30
Divide and Conquer and Memoization
Transcript
00:00
Data structures and algorithms don't have to feel like an intimidating wall of complex jargon and syntax.
00:06
In this comprehensive crash course, Sue meets Shaha will teach you foundational computer science concepts
00:12
using relatable real world analogies without writing a single line of code.
00:17
You will develop a clear, intuitive mental model of how data is stored, searched, and optimized.
00:23
Once you master the underlying logic and problem solving mechanics here,
00:28
implementing them in any programming language becomes easy.
00:32
All right, let me start with a very simple question.
00:35
Think a little before you answer.
00:37
Has this ever happened to you?
00:39
You are holding a long grocery list for the month and searching for the most expensive item?
00:44
Or say, while scrolling through your contact list,
00:46
you suddenly see that a friend's number was saved twice by mistake.
00:50
It also happens that you woke up in the morning and make a to-do list for the day.
00:54
As you finish your tasks, you cross them off one by one with satisfaction.
00:59
Suddenly an urgent task pops up and you place it right at the top of the list.
01:04
If you have done even one of these things in your life, let me tell you a secret.
01:08
You have already practiced data structures and algorithms.
01:11
Yes, without realizing it, you have thought like a programmer, organized data and used
01:16
a specific path or algorithm to solve those problems.
01:20
The only difference is that you didn't know these have fancy complicated names in computer
01:24
science textbooks.
01:26
The real trouble starts with our fear.
01:28
Whenever we hear these complicated names in books or tutorials like Arrays, Link Lists,
01:33
Big O Notation, Time Complexity or Recursion, an invisible wall instantly goes up in our
01:39
minds.
01:40
Suddenly, it feels like, oh boy, this must be some incredibly difficult math stuff.
01:46
No one but a rocket scientist could possibly understand this.
01:49
It seems like it has nothing to do with our common daily thoughts.
01:53
But do you know the truth?
01:55
We are constantly using these things every day in our heads, at our desks, in the kitchen
02:00
or in the smartphone in our pockets.
02:03
Today we are going to break that very fear.
02:05
We will bridge the massive gap that has formed between our everyday familiar experiences and
02:10
these difficult computer science terms.
02:13
Today we will dive deep into data structures and algorithms.
02:16
But it won't be like those monotonous boring classroom lectures at all.
02:20
We proceed like a beautifully organized story where everything is interconnected We look for the story behind why we move from one topic to another You will see that nothing feels disconnected or like something you have to memorize without understanding
02:35
And you know what the fun part is?
02:37
Throughout this entire journey, we won't write a single line of code on the screen.
02:41
You know why?
02:42
Because the AI will write the code, right?
02:46
But you will realize by watching this full video that data structures and algorithms can
02:51
be learned even without writing code.
02:53
Not only that but this is actually the best way to learn it because we will try to understand
02:58
the mechanics behind it.
03:00
Our main goal will be to understand what these things do behind the scenes, why they do it
03:05
and which one comes in handy when you face a problem.
03:09
Once you grasp the actual logic behind something, translating it into code in any programming
03:13
language, be it C++, Java, Python or JavaScript is simply a matter of time.
03:20
Once these concepts become clear, a fantastic mind map of the entire subject will be drawn
03:25
inside your head.
03:26
Then you will see that you can effortlessly tell yourself exactly which data structure
03:30
will work like magic to solve a particular problem.
03:33
As soon as you step into the world of programming, you hear a term data structure.
03:38
But have we ever asked ourselves why we need to organize data in such specific ways?
03:43
Data is just data, isn't it?
03:46
No matter how we leave it in our system, we should be able to find it when we need it.
03:50
Then, why all these unnecessary rules, complicated names and such complexity?
03:56
To find the answer to this question, let's take a look at the desk in our study room.
04:00
Close your eyes and think for a moment.
04:03
On your desk, all your notes, exam papers, electricity bills and bank statements from
04:08
the last five years are piled up in a huge disorganized heap.
04:13
A little mountain of paper has gathered on the table.
04:16
Suddenly your father comes and asks you to find the electricity bill from March three
04:21
years ago.
04:22
He really needs it.
04:24
Now think what will your situation be?
04:27
How long will it take you to find that one specific paper by digging through that huge
04:31
mountain of messy papers?
04:33
Maybe hours will pass and the whole room will be a mess.
04:37
You will be completely drenched in sweat.
04:40
It could even happen that after searching everywhere and turning the world upside down,
04:45
you still don't find the paper.
04:47
Let's change this scene a little bit.
04:50
Suppose there is no mountain of messy paper on your table.
04:54
Instead there is a very nice file cabinet kept there The cabinet has separate drawers for each year For example 2022 2023 2024 and so on Also inside each drawer there are separate folders neatly
05:08
organized by month. For instance, January, February, March. Now, if your father comes
05:14
and asks for that specific electricity bill, what will you do? He will go straight to opening
05:20
the 2023 drawer.
05:21
You will take out the March folder from there and in the blink of an eye, within just a
05:26
few seconds hand the correct paper to your father.
05:29
If you look closely, you will see that the core elements or data between the first and
05:33
second scenes haven't changed even a bit.
05:36
The papers are exactly as they were before.
05:39
The information inside the papers is exactly the same.
05:42
Only one thing created the difference.
05:44
How the papers were organized.
05:47
And just because of this difference in organizational method, hours of back breaking labor turned
05:52
into a simple task taking only a few seconds.
05:55
Our work speed increased a thousand times.
05:58
This is exactly the core philosophy and real power of data structures.
06:02
When you work with thousands, millions or billions of data points in computer memory,
06:07
if we leave them scattered randomly, the computer will struggle immensely to find the data.
06:12
Our software or app will slow down, hang or simply crash.
06:17
Data structure means organizing data inside memory in such a smart and tidy way that it
06:22
becomes very easy to work with the data later on.
06:24
For example, finding something quickly, adding new data or deleting unnecessary data.
06:29
This task should be done extremely fast and at a much lower cost.
06:33
There is a very important point here that we need to fix firmly in our minds which will
06:37
be helpful to us at every step ahead.
06:40
When we perform a task, the calculation of how much time and memory the computer consumes
06:45
to do it is what we call efficiency.
06:48
We do not need to get into the nitty gritty of heavy mathematics or complex equations.
06:53
Just remember this simple truth.
06:55
If you organize the same data in different ways, the speed of your program will also
06:58
be completely different.
07:00
This one line will remain the key to our entire journey ahead.
07:04
From this urge to organize data, the oldest and the most fundamental data structure of
07:09
programming was born, named array programming.
07:12
We have all been more or less introduced to it during our early days of learning.
07:16
Let's try to understand how it actually works internally using an example from our familiar
07:21
world.
07:22
Surely you have the experience of watching a movie in a cinema hall At the entrance we look at the ticket in our hand which might say row A seat number 5 What are the hall seats like Placed right next to each other arranged in
07:35
a straight line. Seat number 2 is right next to seat number 1 and right beside it is number
07:41
3. It continues in this way. Now think about it. When you enter the hall, do you go to
07:46
the person sitting in seat 1 and ask, Brother, where is seat number 5? Then do you ask the
07:52
same question to someone in seat 2?
07:54
Not at all.
07:55
You know very well that seats are arranged sequentially and each one has a specific number.
08:01
Without anyone's help, you can confidently walk straight to seat number 5 and sit down.
08:06
The time it took you to sit in seat number 5 is exactly the same amount of time it would
08:10
have taken to sit in seat number 1 or 10.
08:14
In computer memory, this array works just like the seats in a cinema hall.
08:18
When we create an array in memory, the computer, like a very obedient child, allocates blocks
08:24
or spaces for us right next to each other in memory.
08:28
There are no gaps in between and a specific serial number is assigned to each of these
08:33
places.
08:34
In programming language, we call this number an index.
08:37
However, there is an interesting aspect here.
08:40
Even though our general calculations start from 1, the computer's serial numbers start
08:44
from 0.
08:45
For some reason, computers seem to really like the number zero.
08:49
The greatest magical power of an array is its instant access, which means the ability
08:54
to reach data in the blink of an eye.
08:56
Suppose your array has 10 million data points.
08:59
You come on the computer, bring me the data at the 5 millionth index.
09:04
The computer will not search even a little bit.
09:06
In a split second, it will go directly to that 5 millionth spot and hand you the data.
09:11
In technical terms, this is called constant time complexity.
09:15
Simply put, no matter how large the mountain of data is, if the specific index is known,
09:20
the time to find it will always be the same.
09:23
And that time is very close to zero.
09:26
But as the saying goes, nothing in this world is perfect.
09:29
This is true to the letter for arrays as well.
09:32
Behind this incredible strength lies a huge weakness.
09:35
Let's go back to that movie theater again.
09:38
Suppose people are packed tightly in sets 1 through 10 in a row, watching a movie intently.
09:43
Suddenly, the hall manager announces that for a VIP guest a new seat must be placed
09:49
exactly between seats 3 and 4.
09:51
Now imagine what a huge problem this is.
09:54
There isn't even an inch of space in between.
09:57
To insert a new seat there, the poor person in seat
10:00
4 will have to get up and move to 5.
10:02
The person at 5 will have to move to 6.
10:05
The person at 6 to 7.
10:07
This way everyone all the way to the end will have to leave their spot and shift one seat
10:12
to the right.
10:13
This will create extreme chaos and annoyance among all the people in the hall.
10:18
Right?
10:19
And a lot of time will be wasted doing this whole task.
10:23
The exact same thing happens inside an array.
10:26
When you try to insert new data into the middle of an array or want to delete data from the
10:30
middle, the computer is forced to move all the following data one spot forward or backward.
10:36
We call this shifting.
10:38
Now if the amount of data is small, it might not be a big deal.
10:42
But if there are hundreds of thousands or millions of data points, then this task of
10:47
inserting or deleting data in the middle becomes a massive, time-consuming and annoying job
10:53
for the computer.
10:54
So what is the solution?
10:56
We want speed.
10:57
But we don't want to deal with this hassle of inserting data in the middle.
11:01
We need a solution where we can easily add new things whenever we want, wherever we want.
11:07
And that too without bothering anyone.
11:10
It is from this deep human desire that our next data structure is born.
11:14
Its name is Link List.
11:16
To avoid the hassle of shifting seats and the pain of finding data in between, computer
11:21
scientists came up with a brilliant idea.
11:23
They said there is no need to keep the data packed tightly or side by side inside memory.
11:29
Let them sit anywhere in the free memory space as they please.
11:32
We will just provide a link of communication between them.
11:35
This wonderful concept is called a link list.
11:38
To understand this link list concept easily, we can think of a treasure hunt game.
11:43
Many of you might have played this game in your childhood.
11:46
What actually happens in the game?
11:48
When you start the game, you don't have the entire treasure map or the addresses of all
11:52
the locations in your hand.
11:54
You only have a small note in your hand with the first clue or hint written on it.
12:00
That note might say the next note can be found under that big mango tree in the garden.
12:04
You run towards the mango tree and find the second note there.
12:08
It says the next clue is hidden by the old well.
12:11
This is how one note points you to the address of the very next note.
12:15
And you, passing through one address at a time, eventually find the treasure box at the
12:20
very end.
12:21
A link list works exactly by the rules of this treasure hunt game Here we call each piece of data a note Each note contains two things Firstly our actual data such as a number or a name
12:35
And secondly, the address or pointer to where the next node is sitting in the memory.
12:40
In simple terms, the first data tells you where the second data is.
12:44
And the second one tells you the location of the third.
12:47
Even though they are scattered here and there in the vast kingdom of memory, they remain
12:51
strung together like a thread through this chain of addresses.
12:55
Now think about it.
12:57
How does the linked list magically disappear at the hassle of inserting data in the middle
13:01
like in an array?
13:02
Suppose in our treasure hunt we want to add a new note or clue right between the second
13:07
and third notes.
13:08
Do you have to move the mango tree or the old well in the garden even an inch for this?
13:13
Not at all.
13:14
We just erase the address written on the second note and write the address of the new note
13:18
there.
13:19
And in the new note, we write the address of the third note.
13:22
That's it.
13:23
The work is done.
13:24
Not a single piece of data in the memory had to be moved.
13:27
Therefore, adding or deleting anything in the middle of a linked list is extremely easy
13:32
and very fast.
13:33
But wait a minute.
13:35
When we were talking about arrays, we said that there is nothing perfect in the world
13:39
of programming.
13:41
Everything is a trade-off.
13:43
Meaning to get something, you have to give something up.
13:46
The linked list did indeed give us the advantage of inserting data very easily.
13:51
But in return, it took one thing away from us.
13:54
This is the ability to reach any data in the blink of an eye.
13:58
Just think, in a treasure hunt game, can you jump straight to the fifth note at the beginning?
14:02
Never.
14:03
No one knows where the fifth note is except for the fourth note.
14:07
And again, only the third note knows the address of the fourth one.
14:11
So you are forced to always start from the first note and walk through them one by one
14:16
to reach the fifth.
14:17
In a linked list, if you want to see the 100,000th piece of data, you have to start from the
14:22
first one and cross 99,999 pieces of data before getting there.
14:29
In terms of searching, it is therefore quite slow.
14:32
This linked list also has some interesting and useful types that we need to know about.
14:37
First let's talk about the singly linked list.
14:39
What we are discussing all this time is actually a singly linked list.
14:44
Its main characteristic is that it can only move forward.
14:48
Each note only knows the address of the next note.
14:50
It has no information about where the previous one is.
14:53
It a lot like a one street Cars will only run in one direction Now imagine you have moved forward in a treasure hunt game But suddenly you feel the need to read the previous note again
15:05
In a singly linked list, you cannot go back.
15:08
You have to start all over again from the very beginning.
15:11
To solve this hassle, the doubly linked list was introduced.
15:14
Here, each note doesn't just keep the address of the next data.
15:18
It also carefully keeps the address of the data immediately preceding it.
15:23
Meaning this is a two way street.
15:26
If you want, you can go forward and you can also walk backward whenever you please.
15:31
And the third type is the circular link list.
15:34
Now imagine the very last node in all list keeps the address of the very first node at
15:38
its next address.
15:40
What would happen then?
15:41
The entire list would join up like a round wheel.
15:44
It would have no beginning or end.
15:46
It would just keep going around.
15:48
Do you know where this is used?
15:50
When you listen to music on your phone's player with loop or repeat mood on, you will
15:54
notice that as soon as the last song ends, the first song starts playing again on its
15:58
own.
15:59
The concept of this circular linked list is what works behind this magical task.
16:04
So what is the bottom line?
16:05
Arries give us the power to find data quickly, but they get exhausted when it comes to adding
16:11
or removing data.
16:13
On the other hand, linked lists give us the freedom to add or remove data in the blink
16:17
of an eye.
16:18
But to search for data, it has to work a long way.
16:21
This is the true expertise of a good programmer, choosing exactly which one is needed for which
16:27
task.
16:28
If you treat every problem with the same simple solution here, you are doomed.
16:32
Does your app need to search for data repeatedly?
16:35
Then choose an array.
16:36
Or does your app need to add new data in the middle frequently?
16:40
Then go for the linked list.
16:41
This subtle knowledge of the difference will turn you from a regular coder into an expert
16:46
software engineer.
16:47
So far, we have seen how to organize data in memory, sometimes side by side like an
16:51
array and other times scattered around and linked like a linked list.
16:56
But in real life, we encounter situations where more than where the data is, the important
17:00
thing is the order in which the data enters and leaves.
17:04
Based on this rule, two amazing data structures have been created, named stack and queue.
17:09
Let's start by talking about the stack.
17:12
The simple meaning of the word stack is a pile or heap.
17:15
To understand this, imagine a familiar scene in your dining table or kitchen at home.
17:20
Suppose many dishes have been washed at home and now need to be organized.
17:24
You place the first plate on the table you place the second one right on top of the first the third one on top of the second In this way a high pile of ten plates is formed by placing one on top of another
17:36
Now when you need a plate to eat, which plate will you pull out first?
17:41
Would you try to pull out the first plate from the very bottom?
17:44
Are you crazy?
17:45
If you try to pull the bottom one, the whole pile will come crashing down.
17:49
Naturally, you will pick up the plate from the very top.
17:52
Meaning, the plate you placed last is the one you are picking up first.
17:56
This simple and natural rule of our daily lives is known in computer science terminology
18:01
as LIFO or LAST IN FIRST OUT.
18:04
This means the data that enters the system last will be the first one to come out.
18:09
And the data structure that follows this rule to the letter is what we affectionately call
18:14
a stack.
18:15
There are mainly two operations that happen within this stack.
18:19
When we add new data to the very top of the stack, that action is called push, just like
18:24
placing a new plate on the pile of plates.
18:27
And when we remove or delete the data from the very top, that is called popping, just
18:31
like picking up the top plate to use for a meal.
18:35
To be honest, we are using this stack every moment of every day on our computers or smartphones.
18:40
We don't even realize it.
18:42
For instance, when you browse the internet, suppose you go to Google first.
18:47
From there, you click a link and enter Facebook.
18:50
Then clicking another link takes you straight to YouTube.
18:54
Behind the scenes, your web browser is arranging these pages in an invisible stack, one after
19:00
another, meaning it is pushing them.
19:02
Now if you click the browser's back button, do you go straight to Google?
19:07
No, you go back to Facebook.
19:09
This means the page you were on last is the one returning or popping first.
19:15
by pressing back again to reach Google.
19:18
This is a living example of the stack in action.
19:21
Again, suppose you are watching something in Microsoft Word
19:24
or editing a photo in Photoshop.
19:26
Whenever we make a mistake,
19:28
we quickly press Ctrl Z on the keyboard to undo it, right?
19:32
Every time you type a new word or make a stroke on an image,
19:35
the software quietly pushes those actions into a stack.
19:39
Whenever you press undo,
19:41
it pops the action at the very top of the stack,
19:43
which is the last thing you did.
19:46
And your document returns to its previous state.
19:49
Don't be surprised.
19:50
In programming, when a function is called, memory uses a call stack in the exact same
19:55
way.
19:56
Now, let's talk about queues.
19:58
By now, we have understood the state.
20:00
Stack Rule Whoever comes last lives first.
20:03
But does this rule work everywhere in real life?
20:06
Suppose you have gone to the bank to deposit money or are standing in line to buy movie
20:11
tickets.
20:12
You have been standing in scorching heat since 8 am and have reached the very front of the
20:16
line.
20:17
Then at 10 am someone else comes along lazily and stands at the very back of the line.
20:23
Now what would happen if the bank or ticket counter started working based on the stack
20:28
rules?
20:29
person who arrived last would take the ticket first and head home happily.
20:34
And you just keep standing there like you have since morning.
20:38
Does that make any sense?
20:39
It wouldn't be fair at all.
20:41
If that happened, there would be absolute chaos and fighting in the line.
20:46
It is precisely for situations like this that we need a data structure with the complete
20:50
opposite rule, where the simple rule is whoever comes first gets served first.
20:56
Here this wonderful and perfectly fair data structure is called a queue.
21:01
The direct meaning of the word queue is a line or a row.
21:05
When you stand in line at a bank, pass counter or supermarket to pay a bill, that is a real
21:10
life queue.
21:11
Here, the cashier serves the person standing at the very front of the line first.
21:16
Once their work is done, they leave the line with a smile and the person behind them moves
21:20
forward.
21:21
if someone new wants to join this line, they are forced to go and stand at the very back.
21:27
They cannot just push their way into the middle or the front under any circumstances.
21:32
This simple and beautiful rule is known in computer science as FIFO or first in, first
21:37
out.
21:38
Meaning the data that arrives at the front of the line first is the first to be processed
21:43
and leave the line.
21:45
Basically two main events occur within a queue.
21:48
The process of adding new data or a person to the very back of the line is called enqueue.
21:53
And the process of removing data or a person from the very front of the line once their
21:57
task is complete is called tqueue.
22:00
To understand this queue concept inside a computer, think about the printer in your office or
22:04
home.
22:05
Suppose there is only one printer in an office.
22:08
But there are 10 computers connected to it.
22:11
Now in the morning 10 employees send 10 large documents to be printed almost at the same
22:16
time.
22:17
Your printer cannot print 10 documents all at once.
22:20
It has to print them one by one.
22:22
That when the printer neatly creates a print queue in its own memory The document request that arrived even a millisecond earlier the printer places it at the very front of the line and it enqueues the rest in the pack
22:35
lining them up in order. Then it starts printing the very first document. Once the first one
22:41
is finished, it removes it from the line, meaning it dequeues it and starts working
22:46
on the second one. No one interferes with anyone else's work. Everything is completed
22:51
in an orderly fashion, just like clockwork.
22:55
Besides this common queue, there are several other great and useful types.
22:59
For example, the circular queue.
23:01
When we build a simple queue using an array, we often run into an interesting problem.
23:06
It turns out that after the people at the front of the line finish their work and leave,
23:10
the memory spaces at the front remain empty.
23:13
But because the back is full, no new data can be added.
23:17
This is a huge waste of memory.
23:19
The circular queue was born as a great solution to this problem.
23:22
Here, the very end of the line is connected back to the beginning, just like a circle
23:27
or a loop.
23:29
As a result, even if there is no space at the back, if there is free space at the front,
23:34
new data can simply wrap around and sit in those empty spots.
23:38
This ensures not a single bit of memory is wasted.
23:41
It is widely used in various process management tasks in operating systems.
23:46
Now let's talk about the DQ.
23:49
Another great and special form of a queue is DQ.
23:52
Its full name is double ended queue.
23:54
The rule for a standard queue is that data enters from one end and leaves from the other.
23:59
But sometimes special situations arise where we need a line where data can be added from
24:05
both the front and the back.
24:07
And data can also be removed from both ends.
24:10
This particular two way line is called a DQ.
24:13
It is so flexible and useful that you can use it as a stack if you want or even run it
24:18
as a cue when needed.
24:19
We have seen that the rules of a cue or line are quite straight.
24:23
Whoever comes first gets served first.
24:26
But think about it.
24:27
Can we always follow these strict rules in real life?
24:30
Let's try to understand this with a very sensitive and real world example.
24:34
Suppose you are sitting in the emergency room of a hospital.
24:37
There is a long line or cue to see a doctor.
24:40
Perhaps there are three patients sitting in that line.
24:43
Someone has a mild fever.
24:45
Someone else might have a cut on their hand bleeding slightly and someone else has a mild
24:49
headache.
24:50
They have all been waiting in line since the morning.
24:53
Just then a new patient arrives at the hospital with an ambulance siren wailing loudly They are having a severe heart attack The person is completely unconscious Now what if the hospital authorities insist on the strict rules of that common cue
25:09
What if they say, so what if you are having a heart attack?
25:12
There is nothing we can do outside of the rules.
25:14
Go stand at the back of the line.
25:17
Let the patient with fever and headache be treated first, then it will be your turn.
25:22
Imagine the other patient might die while standing in that line.
25:26
In such critical real-life moments, the rule of a standard cue is completely ineffective.
25:30
Here, we need a smart cue or system where who come first or last is not a consideration
25:36
at all.
25:37
Instead, whoever has the highest priority of need will receive service first.
25:42
Under this rule, a heart attack patient will come to the very front of the line even if
25:46
they arrive last.
25:48
at this moment their life is the most important priority. Interestingly, computer science has
25:54
created a data structure based exactly on this hospital model. Its name is the priority queue.
26:00
Data in a standard queue exists according to the sequence of time. But in a priority queue,
26:06
a priority value or weight is attached to every piece of data. No matter how or in what sequence
26:12
you insert the data into the line, when you extract or dequeue, the most important data
26:17
will always come first.
26:19
Now a very natural question might come to your mind.
26:22
How does a computer actually build this priority queue internally?
26:26
How does it find the most important data out of thousands in the blink of an eye and place
26:30
it right at the front?
26:32
To par from this magic, the data structure that the priority queue uses as its engine
26:36
is called a heap.
26:38
You can think of a heap as a brilliant and smart organizing system or a pyramid.
26:43
This pyramid has a very beautiful and strict role.
26:46
The most important item will always sit right at the very top.
26:50
Whenever you add new data to this system, the heap immediately shuffles and compares
26:55
its internal data, arranging it so that the most important data automatically floats up
27:00
to the very top.
27:02
There are mainly two types of heaps, max heap and min heap.
27:06
If your rule is that the largest numerical value is the most important, then we use a
27:10
max heap.
27:11
Here, the largest number will always sit at the very peak of the pyramid.
27:15
For example, if there is a 100 mark exam and we want to reward the person with the highest
27:20
score first, we will use a max heap.
27:23
And if your rule is that the smallest numerical value is the most important then we use a mean heap Here the smallest number will always sit at the very peak of the pyramid For instance in a race the person who finishes in the least amount of time is the winner
27:37
In that case, the mean heap will always bring that shortest time data to the peak for us.
27:42
Our computers or operating systems are using these priority cues and heaps every single day.
27:47
When you are playing music, downloading a file in the background, and moving your mouse on your computer simultaneously,
27:53
operating system assigns a priority to each of these tasks. For a computer, moving the
27:58
mouse is a task of the highest priority. That is why it processes the mouse input in the
28:03
priority queue before any music or downloads. This ensures the computer feels completely
28:09
smooth and fast to you. If you look closely at all the ways we have seen to find data
28:13
so far, you will notice a common thread. In Arrays, we were searching by following indices.
28:20
On link lists we were moving along by following one after another.
28:24
And in the case of a queue we were waiting in line.
28:27
But think about this.
28:29
What if we had data for which we didn't know any index or serial number?
28:33
What would happen then?
28:34
Suppose you walk into a huge library or a large bank locker room where 1000 lockers or
28:39
cabinets are lined up.
28:41
You are handed a key with the number 420 written on it.
28:45
Now how long might it take for you to find locker number 420 among those 1000 lockers?
28:50
You might start working from the very beginning of the road.
28:53
Then you would search until you finally reach local number 420.
28:57
That is going to take some time, right?
29:00
Now let's change the scene a little bit.
29:02
Imagine a completely different picture.
29:05
Suppose you open the contact list on your smartphone.
29:07
You might have 1000 friends phone number saved on your phone.
29:11
Suddenly, you need to find your friend Rafid's phone number.
29:14
You don't scroll down through a list of 1000 names at all.
29:18
You simply go to the search box at the top and type Rafit.
29:22
And what about scrolling?
29:23
What about waiting?
29:25
In the blink of an eye, in less than a millisecond Rafit's phone number appears on your screen.
29:30
Have you ever wondered how this impossibly magical speed is possible?
29:35
How does the computer pull out Rafit's number directly from a thousand or hundred thousand
29:39
names without any searching or scrolling hassle?
29:43
This magical data structure that provides such incredible speed is called a hash table.
29:48
Many programming languages also call it a hash map or a dictionary. The core philosophy
29:53
behind how this hash table works is quite fascinating. Its mantra is stop searching, go straight to
30:00
location, in other words direct action.
30:03
It basically works on a key value pair basis, meaning it is a rule similar to matching a
30:08
key to a lock.
30:09
In this rule, our friend Rafid is our key and his phone number is our value or our asset.
30:16
When you store data in a hash table, a very smart and high speed mechanism starts working,
30:21
which is called a hash function.
30:23
You can think of this hash function as a magical machine.
30:26
As soon as you provide the name Rafid as input to the machine, it performs a specific mathematical
30:31
calculation internally.
30:33
Then in the blink of an eye, it gives you a memory number or an index.
30:38
Suppose it says drawer number 75.
30:41
The computer then carefully stores Rafid's phone number exactly in drawer 75 rather than
30:46
in 74 or 76.
30:48
Later, whenever you go to look for Rafid's phone number again, the computer won't search
30:53
through the entire phone book.
30:55
It will simply put the name Rafid into that hash function machine again.
30:59
The machine will immediately say draw number 75 and the computer will directly open draw
31:05
number 75 and hand you the number.
31:07
Whether your phone book has 10, 1000 or 10 million pieces of data.
31:12
Searching for anything in a hash table always takes exactly the same amount of time which
31:16
is close to zero.
31:18
In terms of speed, this hash table is the undisputed king of the data structure world.
31:23
There is another very useful member of this hash table family.
31:27
Its name is Set.
31:28
To understand what a set actually is, imagine a guest list for a VIP club.
31:33
That club has a strict rule.
31:35
The same person cannot enter the club twice under any circumstances and no one's name
31:39
will be written on the list twice.
31:42
When we use a regular array or list, we can keep the same number or name even 10 times
31:47
if we want.
31:48
But, as soon as you put this data into a set, it uses its magical touch to trim all
31:53
duplicate data and keeps each item only once. Interestingly, tip down this set is actually
32:00
just a variation of our powerful hash table. It just keeps the keys carefully to itself.
32:06
It doesn't keep any values. And since by hash table rules the same key cannot exist twice,
32:11
the set automatically removes all duplicates from our data. So, whenever your software
32:16
needs something like removing all duplicate email addresses from a database or checking
32:20
in the blink of an eye if a user name is already in the system then the best weapons in your arsenal will be these hash tables and sets If you look closely at all the data structures we have seen so far you will see a wonderful similarity between them They are all linear data structures This means that here data sits one after another in a well
32:40
organized straight line or row. Number one, then number two, then number three. Just like the
32:46
carriages of a train. But think about it. Does all the information or relationships in our real
32:52
the world always move in such a straight line? Absolutely not. Most relationships in our real
32:57
life are hierarchical or layer-based. Here, many people remain under one person and many more remain
33:04
under them. Let's give a very beautiful and familiar example. Our family tree. Think about
33:10
your own family for a moment. At the very top is your grandfather. Your grandfather's children are
33:16
your father and your uncle, meaning two branches spread out in two directions from your grandfather.
33:22
Again, your father's children are you and your sister, meaning two new branches were
33:27
created from your father's branch.
33:29
On the other side, your uncle's child is your cousin.
33:33
Another branch emerged from your uncle's branch.
33:36
Take a look.
33:37
Can you arrange this entire relationship in a straight line or an array?
33:41
Who would come after the grandfather, father or uncle?
33:44
And who would follow the father?
33:46
Trying to arrange it in a straight line would make the whole relationship tangled and meaningless.
33:51
To explain this kind of branching and parent-child relationship, we need a completely new type
33:56
of data structure.
33:57
It is called a tree.
33:59
However, there is a small but very interesting difference between real world trees and computer
34:04
science trees.
34:05
Real trees have their roots under the ground and their branches spread towards the sky.
34:11
But a computer tree is exactly the opposite, an inverted tree.
34:16
Its root is at the very top, just like the grandfather in our family tree.
34:21
its branches spread downwards. In this magical wall of trees, the very first data at the top
34:26
is called the root, which has no parent. The data from which new branches emerge is the parent.
34:32
And the branches below are called children. The data at the very end of the tree, which has no
34:38
further branches or children, is called a leaf. For example, consider yourself, your sister and
34:44
your cousin. That is, if you don't have children yet. If you do, that's a different story.
34:50
Inside computers, these trees are used constantly every single day.
34:54
Take your computer folder system or file explorer for instance At the very beginning is your C drive which is the root inside this c drive are folders named program files users and windows these are
35:06
the children of the c drive then inside the users folder there are pictures music and documents
35:12
folders like this one folder inside another and more folders inside those this entire system is
35:19
actually one massive living tree. The most famous tree in the tree family is called a binary tree.
35:25
The word binary means two. A tree where each parent can have a maximum of two children.
35:31
One is called the left child and the other is the right child. We call it a binary tree. It cannot
35:37
have more than two children under any circumstances. And when a special rule is cleverly added to this
35:43
binary tree, it becomes one of the most powerful tools in the programming world. The binary search
35:48
tree or BST. The rule for a binary search tree is very simple. The data in the left child
35:54
of any parent must be smaller than the parent's value and the data in the right child must
35:58
have a value greater than the parent. This simple rule gives us a great advantage. Let's
36:04
recall that popular childhood number guessing game. Suppose I have thought of a number between
36:09
1 and 100. You have to guess it. You will say a number each time and I will only answer
36:15
whether my number is greater or smaller than the number you said. Now, if you foolishly start
36:21
guessing in a straight line, like 1, 2, 3, 4, it might take you up to 100 tries. But if you are
36:28
smart, your first guess will be the middle number, which is 50. If I tell you my number is smaller
36:34
than 50, notice what magical thing just happened. With one second of questioning, all 50 numbers
36:40
from 51 to 100 were eliminated from your list of possibilities in one go.
36:45
You don't even have to look in that direction anymore.
36:49
Now you will only search between 1 and 49, right in the middle.
36:54
Next you said 25.
36:55
I said my number is greater than 25 and instantly 1 through 24 are gone.
37:01
In this way, by guessing the middle number each time, we cut our search area exactly
37:05
in half at every step.
37:07
Even if you search through 10 million data points using this method, you can find the
37:11
correct number in just 23 to 24 guesses.
37:15
Our binary search also organizes data in memory following the rules of this magical guessing
37:20
game.
37:21
Whenever you go to search for data it first compares the data with the root If the data is smaller than the root it goes straight to the left and discards all thousands of data points on the right forever As a result searching for any data adding new data or deleting it happens at an incredibly
37:38
fast speed here.
37:40
But there is a small danger hidden here as well.
37:43
Suppose you are going to add some new numbers to a binary search tree.
37:47
But instead of giving the numbers randomly, you start giving them in a sequential order
37:51
for small to large. Like 1, then 2, 3, 4, 5. Now close your eyes and think about it. According
38:00
to our rules, what would be the tree look like? Initially, our root is 1. Then came 2. Since
38:06
the number 2 is greater than 1, it will sit to the right of 1. Then came 3. It is larger
38:12
than 2, so it will sit to the right of 2. Then when 4 arrives, it will sit to the right
38:17
of 3. This tree has no branches on the left side at all. All the data has just gone down
38:23
in a straight line to the right. It doesn't look like a tree anymore. Instead, it has
38:28
taken the form of our old long straight line of a linked list. And whenever our tree leans
38:34
to one side and turns into a straight line, the speed of our magical guessing game is completely
38:40
destroyed. Now, if you want to find the number 5, you have to pass through 1, 2, 3, 4 and
38:46
walk straight to reach 5. To save us from this serious problem, balance trees have arrived
38:52
in the world of trees. The two most famous members of this family are avial trees and
38:57
red-black trees. Here, the full form of avial tree is Adelson-Welsky and Landis tree. These
39:04
words came from the name of the inventors of this data structure. The superpower of a
39:08
balance tree is its ability to maintain its own balance. Whenever you add new data, if
39:14
If it sees the tree growing too heavy or tall on one side, it immediately twists its branches
39:20
to spread the tree evenly again.
39:22
It never allows one side of the tree to grow taller than the other.
39:26
As a result, the tree always remains perfectly balanced.
39:29
And the search speed is lightening fast.
39:32
Our modern large-scale databases use these balanced trees for data indexing.
39:37
So much for the story of maintaining balance in the world of trees.
39:41
Now let's get acquainted with a completely different and amazing type of tree, which
39:46
is also called a tree. The pronunciation is the same as tree, but the spelling is different.
39:52
Some people however call it a tri. The name comes from the word retrieval. To understand
39:58
this type of tree, think of a tree.
40:00
a very familiar daily experience. When you go to the Google search box and type how to.
40:06
Even before you finish the sentence, Google immediately shows you several popular search
40:10
suggestions. Or the way the auto complete feature works when you type on your phone.
40:15
How does the computer figure out which words can be formed from just two or three letters
40:19
out of a vast dictionary of one or ten million words? The data structure that works day and
40:24
The only night behind this incredibly fast autocomplete magic is our tree.
40:29
The way a tree works is completely different.
40:32
In a regular tree, we store an entire word or number inside each node.
40:37
But in a tree, we don't store full words.
40:40
In every node, we store a single letter of the English alphabet.
40:44
Suppose we want to store two words in our tree, car and cat.
40:49
The tree will first create a branch from the root for the letter C.
40:52
From that C, the next branch will extend for A. Now notice, the first two letters of both
40:58
car and cat are exactly the same, C and A. So, the tree will not create C and A twice
41:05
in memory. It will share the same C and A path as a common route for both words. Then,
41:11
from A, the path will split into two separate branches. One branch will go toward R and
41:17
the other will go to our T. Now think about this. Even if our dictionary had a hundred
41:22
thousand words starting with C, they would all begin their journey from that single C
41:27
branch. This results in a massive saving of memory. And when you go to the Google search
41:32
box and type only CA, the computer goes directly from the root to the C branch, then to the
41:38
A branch where it looks down to see how many branches extend below it. It will see that
41:43
one branch goes to R and the other to T. And just like that within a millisecond it will
41:48
show suggestions on your screen asking if you mean to search for car or cat.
41:53
For word searches, spell checkers or search engine autocomplete features, so far we have
41:59
looked at linear data structures that look like straight lines. We also saw hierarchical
42:04
data structures that spread from the top downwards. There is always a parent there and under it
42:09
there are some children, but now let's think about some of the largest networks in our real
42:14
world. For example, social media platforms like Facebook or LinkedIn. On Facebook, you
42:20
are my friend and I am your friend Again your friend is Rafid Rafid friend is Tanvir This is a huge cycle Who is whose parent here and who is whose child Is there even any rule that your friends must be under you
42:37
Absolutely not.
42:38
Everyone on Facebook is connected to everyone else in parallel.
42:42
This is not a straight line nor is it a tree structure depending from top to bottom.
42:47
It is a fast, complex network that spreads in all directions like a spider's web.
42:53
Now consider Google Maps.
42:55
There is a road to go from Dhaka city to Chittagong.
42:58
You can also go from Dhaka to Silet.
43:01
On the other hand, there is also a bypass road from Silet to Chittagong.
43:05
Here, every city is connected to one another through various roads.
43:09
There isn't just one fixed path to travel from one city to another.
43:13
There are countless alternative paths.
43:16
The data structure used to store these complex and interconnected relationships of the real
43:20
world in computer memory is called a graph. In simple terms, in the world of data structures,
43:26
a graph is the most independent and flexible member. It has no strict rules or regulations.
43:32
Anyone can connect with anyone else whenever they want. They can create as many connections as they
43:37
like. It's basically free mixing. To get to know this strange world of graphs well, we need to be
43:43
familiar with two fundamental things. The first one is the Vertex. Vertex refers to the core data
43:49
points of our network.
43:50
For example, on Facebook, every person's profile is a vertex.
43:55
Or in Google Maps, every city is a vertex.
43:58
And the second thing is the edge.
44:01
An edge is the connection or path between two vertices.
44:04
The friendship between two people on Facebook is an edge.
44:07
Again, the road between two cities in Google Maps is also an edge.
44:12
Based on the type of these edges or connections, graphs can be divided into several categories.
44:17
First, let's talk about the undirected graph.
44:20
This is much like our Facebook friendship.
44:23
If you send a friend request to someone on Facebook and they accept it, the relationship
44:27
is established from both sides.
44:29
If I am your friend, it means you are also my friend.
44:32
This connection has no specific direction or one-way arrow.
44:36
Both can access each other's profile with equal rights.
44:40
This wonderful network of two-way relationships is called an undirected graph.
44:45
Now let's think about Twitter or Instagram.
44:48
If you follow a famous celebrity there, it doesn't mean that the celebrity follows you
44:51
back.
44:52
The relationship here is completely one way Information or updates will only come from their profile to yours None of your news will go to them This type of network with one way directional arrows is called a directed graph
45:05
Let's go back to Google Maps.
45:07
Suppose there is a road from Dhaka to Chittagong and there is also a road from Dhaka to Silet.
45:13
The two roads are not the same.
45:15
The distance from Dhaka to Chittagong might be 250 km taking 5 hours.
45:19
On the other hand, the distance from Dhaka to Silet might be 240 km.
45:24
But, it takes 6 hours.
45:26
When each connection or road in our graph is associated with a calculation of distance,
45:31
time or cost which we call weight.
45:34
It is called a weighted graph.
45:36
Google Maps or Uber always uses these weighted graphs to calculate exactly which route will
45:41
save you both time and fuel.
45:43
And if there is no calculation of distance or cost between the connections, what do we
45:47
call it?
45:48
For example, my friendship with you on Facebook has no kilometers or weight attached to it.
45:54
This kind of simple connection is called an unweighted graph.
45:57
Finally, let me tell you a great truth.
46:00
All the studying we did about trees, trees are not actually things from another planet.
46:05
A tree is just a special form of a graph.
46:08
If you apply two strict rules to a graph, first, there cannot be any cycles, meaning
46:13
there should be no path that loops back to where you started.
46:17
And second, every child must have only one parent.
46:20
you will see that the graph magically transforms into a tree.
46:24
Once you understand this small relationship,
46:26
you will be surprised to see that everything from arrays to graphs
46:30
are actually members of the same family.
46:33
They have just taken on different forms to meet our various needs over time.
46:37
So far, we have seen how our data can be neatly organized in computer memory.
46:42
We met movie theater seats with arrays,
46:45
treasure hunt chains with linked lists,
46:47
stacks of plates with stacks,
46:48
Ticket queues with queues, magic drawers with hash tables, family trees with trees and a
46:55
giant spider web with grubs.
46:58
But think about it.
46:59
Is our job done just by organizing data in memory like this?
47:03
Suppose you bought a filing cabinet for your desk as a hobby.
47:06
You organize the papers neatly in folders.
47:09
But if you sit in front of that cabinet all day just staring at it without taking out
47:14
any papers, reading them or doing any new calculations, then what was the point of a
47:18
of building such a wonderful cabinet?
47:21
A data structure is essentially a house to store your data But the real work is with the data kept inside that house We might need to find specific information from among billions of data points You need to organize random data neatly from smallest to largest
47:37
Or like Google Maps, you need to find the shortest and cheapest route from one city
47:41
to another.
47:43
The specific and disciplined method you use to handle this data, solve problems and reach
47:47
an accurate result through step by step calculation is professionally called an algorithm.
47:53
In simple terms, data structure is the science of where and how we store things and algorithm
47:58
is the art of how we use those stored things to perform tasks and solve problems.
48:04
One is absolutely useless without the other, just as science is useless without arts.
48:09
The first task we encounter when stepping into the world of algorithms is searching
48:13
or finding something.
48:15
Honestly, our entire digital world stands on this searching.
48:19
In computer science, there are mainly two primary methods for searching data, linear
48:24
search and binary search.
48:26
Let's start with linear search.
48:28
Suppose you got a huge 100 page register book from your college.
48:32
It contains the names of 1000 students.
48:35
But the trouble is the names are not sorted alphabetically.
48:38
They are completely random.
48:40
Now if you are asked to find the name Tanvirah Amit from that book, what options do you have?
48:45
You are forced to open page number 1.
48:48
You have to read the first name, then you have to read the second name.
48:51
This way you have to check every name line by line until Tanvir Ahmed is found.
48:57
This method is called linear search.
48:59
Here, the computer starts from the very first index of an array or list and checks the data
49:04
one by one until the end.
49:06
The problem arises when Tanvir's name is on the last line of the last page of the book.
49:11
You have to go through the trouble of reading all 1000 names.
49:15
If the data is 10 million, the computer will have to check 10 million times.
49:19
It is clear that this is extremely slow.
49:22
The second method is binary search.
49:24
Now imagine you were not given a random book.
49:27
You were given a huge, thick, Oxford English dictionary containing 100,000 words, all sorted
49:34
alphabetically from A to Z.
49:36
Now if you are asked to find the word monkey, you surely wouldn't start reading line by
49:40
line from the first page, right?
49:43
You directly open the dictionary right in the middle.
49:45
Suppose after opening the middle, you see that words starting with the letter M are
49:49
there, but the page is for the word mango.
49:52
You know very well that in the English alphabet, the letter O in the word monkey comes much
49:57
later than the letter A in the word mango.
50:00
This means you are certain that the word monkey cannot possibly be in the left half of the
50:05
dictionary.
50:06
You immediately eliminate that entire 50,000 word section on the left side of the dictionary
50:11
in the blink of an eye.
50:13
Now you open the remaining right half of the dictionary right from its middle.
50:18
Perhaps you found nose there.
50:20
You realize that monkey must be before nose.
50:24
Immediately the entire right half is discarded.
50:27
By opening from the middle each time, you are halving your search area with every step.
50:33
This magical method is binary search.
50:35
In a dictionary of 100,000 words, a linear search could take up to 100,000 checks.
50:42
With binary search, you can find the word by opening the pages at most 17 times.
50:47
However, there is one thing you must keep in mind.
50:50
The main condition for binary search to work is that your data must be pre-sorted.
50:55
Once the data is scrambled, binary search will not work.
50:59
Then linear search remains your only hope.
51:02
And this concept of dividing in the middle and discarding half is exactly what we saw
51:06
inside binary search.
51:08
We saw that to use binary search, the data must be sorted.
51:12
But in real life, when you get new data, it doesn't come neatly organized on its own.
51:18
It comes in a completely random state.
51:20
The algorithms we use to transform this chaotic disorder into order are called sorting algorithms.
51:26
Let's get acquainted with a few such excellent sorting algorithms.
51:31
First comes bubble sort.
51:33
What happens when a bubble of air or gas forms underwater?
51:36
It slowly floats up to the surface.
51:38
Bubble sort works exactly on this principle.
51:41
It compares two adjacent numbers starting from the very beginning.
51:45
If it says the front number is larger than the back one, it immediately swaps their positions.
51:50
By comparing side by side like this, the largest number in the list floats just like a water
51:54
bubble to the very end of the list and settles in its correct place.
51:59
It repeats this entire process until all the numbers are sorted correctly.
52:03
The method is very easy to understand, but it works extremely slowly when there is a
52:08
lot of data.
52:10
Next comes the selection sort.
52:12
Suppose 30 students are standing in a classroom with random heights.
52:16
The teacher wants to line them up from the shortest to tallest according to their height.
52:21
The teacher will look at all 30 students and the shortest student among them will be pulled to the front and placed in the first position in the line Then ignoring that first student the teacher will pick the shortest among the remaining 29 students and place them in the second position
52:38
This method of picking the smallest from the remaining students each time and placing them
52:42
in the correct spot is selection sort.
52:44
The third method is insertion sort.
52:47
When you play cards with friends, how do you arrange the new cards when they are given
52:51
to you one by one from the deck?
52:53
Suppose you already have three cards arranged in your left hand, 2, 5 and 9.
52:59
Now you pick up a new card in your right hand.
53:02
Suppose it is 7.
53:04
You will compare the 7 card with the cards in your left hand.
53:07
You will see that 7 is smaller than 9, but it is larger than 5.
53:11
You immediately create a small gap between the 5 and 9 cards and insert the card right
53:16
into that place.
53:18
This method of taking new data one by one and inserting it into the correct position
53:22
within the already sorted part is called insertion sort.
53:25
It works quite fast when the amount of data is small.
53:29
These three simple methods are good for small tasks.
53:32
But they will completely fail when trying to sort 10 million or 100 million data points.
53:38
So for large data, we need more powerful weapons.
53:42
Marge sort is a very intelligent algorithm.
53:44
It doesn't try to solve a huge problem all at once.
53:48
believes that no matter how big a problem is, break it into small pieces.
53:53
Suppose you have a list of 8 random numbers.
53:56
Marsort will first cut these 8 numbers in the middle and divide them into 2 groups of
54:01
4.
54:02
Then it will cut this 4 into 2 groups of 2.
54:06
After that it will cut the 2 into single pieces, making 8 separate individual pieces.
54:11
A single number is already sorted by itself, right?
54:15
Now Merge Sort will take two single numbers at a time from the bottom.
54:19
It will compare them and pair them up in the correct order or merge them.
54:23
By joining these small sorted pieces together like this, in the end it will create a perfectly
54:28
sorted list of all the eight numbers.
54:31
The speed of this method is super fast.
54:34
Another fast-paced method is Quick Sort.
54:36
It first uses any number from the list as a leader or pivot.
54:40
Suppose it makes the number 50 our leader from the list.
54:43
Now QuickShot will run through the entire list once and bring all the numbers smaller
54:48
than 50 to its left side.
54:50
And it will bring all the numbers larger than 50 to its right side.
54:54
As a result our leader 50 will land in its exact correct position because everything to the left of 50 is smaller and everything to the right is larger Now QuickSort will choose a new leader for that small left section and it will choose
55:09
a new leader for the large right section.
55:11
By dividing into small groups and selecting leaders this way, a list of millions of data
55:16
points will be sorted in the blink of an eye.
55:19
In real life, when we call a sort function in most of the world's programming languages,
55:24
Quick sort or merge sort silently works for us behind the scene in memory.
55:29
Now we'll talk about a concept that feels like a puzzle when heard from the first time
55:33
or seen in court.
55:35
This wonderful thing is called recursion.
55:38
Simply put, when a task or function calls itself repeatedly to solve its own problem,
55:43
that is recursion.
55:45
Giving two examples from real life will make the matter crystal clear in an instant.
55:49
Have you ever been to a salon or dressing room where there's a huge mirror on the wall
55:53
in front of you and another one right behind you.
55:57
Have you ever noticed what happens when you stand in the middle?
55:59
You can see the back mirror inside the front mirror and inside that back mirror you see
56:04
the front one again.
56:06
Inside that another smaller one with you looking even smaller and this image continues to repeat
56:12
into infinity, getting smaller and smaller.
56:15
One mirror reflecting itself over and over.
56:18
This is recursion in its living form in nature.
56:21
I can give you another example.
56:23
For those who have used the OBS screen recorder, if you select your desktop as a scene in OBS,
56:29
you'll see the fun.
56:30
You can see an infinity recursion there as well.
56:33
Or consider those famous Russian wooden dolls.
56:36
If you open the lid of a beautiful wooden doll, you can see that inside it looks exactly
56:41
the same.
56:42
But there is another doll sitting inside that is a bit smaller.
56:46
Opening that one will reveal a third, even smaller doll.
56:50
A smaller version of the same doll hiding inside the belly of the larger one.
56:54
This is recursion.
56:55
In the world of programming, it is famously called the Russian nesting doll.
56:59
Suppose I ask you to find the sum of all numbers from 1 to 100.
57:04
If you think in terms of recursion, you might say adding 1 to 100 is quite a task.
57:10
Let's do this.
57:10
Set the number 100 aside and tell my younger brother to get me the sum of numbers from 1 to 99.
57:17
Once it brings it, you add 100 to it.
57:20
and that's it.
57:21
But your younger brother isn't that foolish either.
57:24
He sets the number 99 aside and calls his younger brother to bring him the sum from 1 to 98 In this way each brother keeps calling a smaller version of himself to solve a problem that is one step smaller
57:37
The call eventually reaches the very youngest brother, who has only one number in his hand, which is 1.
57:43
Then that little brother will say, the sum of 1 is just 1.
57:47
He doesn't need to call anyone for that.
57:50
He sends the 1 back to his older brother.
57:52
He adds two to it and sends it back to his older brother.
57:56
In this way, the sum builds up from the very bottom one after another until it finally reaches your hands.
58:02
And you get your desired answer.
58:04
Five zero five zero.
58:06
Notice that the last little brother for whom the problem became so tiny that there was no need to call anyone else.
58:13
In programming terms, this magical moment is called the base case or the stopping condition.
58:17
If you don't provide this correct base case in recursion, you are in big trouble.
58:22
The code will then keep looping forever, just like the two mirrors in that salon.
58:27
On one point, the computer's memory will be completely filled up and the program will
58:30
crash with a critical error, which is called a stack overflow.
58:35
Whether it's smart sort, quick sort or the stories of three data structures we have heard,
58:40
recursion is the most intelligent and precise way to handle them.
58:43
Do you know why?
58:44
Because if you look closely at every branch of a tree, you will see that it is actually
58:49
a small tree itself.
58:50
extraordinary application of this recursion. And an almost magical practical implementation
58:56
of it is backtracking. The name itself suggests following your own footprints back to the starting
59:01
point. Take your daily life for example. When we look for a path in an unfamiliar place,
59:06
we start walking down a road. If we suddenly hit a high wall or a dead end while walking,
59:12
do we just sit there and give up? Not at all. We calmly retrace our own footsteps back to exactly
59:18
where we came from, to the point where we took the wrong turn.
59:22
Then standing there, we try a different path.
59:25
Moving forward on a path and stepping back the moment we see an obstacle or dead end
59:29
and searching for a new path, this entire clever technique is called backtracking.
59:33
In computer science, this concept is perfectly explained by the popular puzzle game, Sudoku.
59:39
You must have seen the 9 into 9 grid it uses.
59:42
And numbers from 1 to 9 have to be placed so perfectly that no number repeats in any
59:47
row, column or 3x3 box. Now do you know what a computer does when it is given a different
59:53
sudoku to solve? It first tries placing a 1 in the very first empty cell. If the rules
1:00:00
Broken, it confidently moves to the second cell and places a 2.
1:00:04
It keeps moving forward like this step by step.
1:00:07
But as it progresses, let's say it reaches the 25th empty cell and realizes that no matter
1:00:13
which number from 1 to 9 it places, it breaks one rule or another.
1:00:17
There is no way to move forward.
1:00:19
A complete dead end.
1:00:21
Right at this point, our clever backtracking algorithm doesn't panic at all.
1:00:25
It quickly calculates that since nothing works in the 25th cell, it must have placed an incorrect
1:00:30
number in the 24th or 23rd cell earlier.
1:00:33
In an instant, it steps back from 25th cell to the 24th.
1:00:37
It clears the previous wrong number and attempts to place a new correct one.
1:00:42
Even if it doesn't find a solution in the 24th cell, it takes another step back to the
1:00:46
23rd cell.
1:00:47
By relying on this magic of retracing footsteps when a mistake occurs, correcting it and trying
1:00:52
a new path, the computer solves the world's hardest Sudoku in just a few milliseconds.
1:00:58
Even the AI in computer chess games use this backtracking to mentally explore all possible
1:01:03
paths for 10 to 15 moves ahead.
1:01:06
And whenever it sees a dead end, it quietly steps back and makes the best possible move.
1:01:11
Most complex relationships in our real world are actually like graphs on networks.
1:01:16
Everything is interconnected, much like a spider's web.
1:01:20
Now think about it.
1:01:21
If we set out to find something within this massive web or we want to walk from one city
1:01:25
to another, how exactly would you proceed?
1:01:28
A network where countless roads branch out from every intersection.
1:01:33
Walking randomly with your eyes closed there, it's only natural to get lost.
1:01:37
You might find yourself going in circles trapped in a maze.
1:01:41
To walk through these complex grubs or trees in an orderly fashion without getting lost,
1:01:45
we primarily have two algorithms at our disposal.
1:01:48
The first is called Depth for such or DFS for short.
1:01:53
And its way of walking is quite strange.
1:01:56
As long as there is a road ahead, don't even think about looking back.
1:02:00
Dive straight to the very end of the boundary.
1:02:03
Imagine you have entered a massive dark maze.
1:02:06
There are three paths open in front of you.
1:02:08
To the right, to the left and in the middle.
1:02:11
If you walk using the DFS method, you would pick one path.
1:02:15
Let's say the one on the left.
1:02:17
Then you would keep going deeper and deeper along that path.
1:02:21
You do not stop until you reach the very end of the road or hit a dead wall Only when you reach the end and see there are no more paths do you use backtracking or retrace your footsteps back to the previous junction Then from there you dive deep again into another unexplored path
1:02:38
For this entire strategy to work properly, we need the help of a stack or recursion.
1:02:43
Because we have to store and remember the junctions we left behind in a stack as we moved forward.
1:02:49
The second technique is called BREADFARSAGE or BFS.
1:02:53
Its main philosophy is very simple.
1:02:55
Before jumping far away, take a good look at those close to you.
1:02:59
Think of a calm steel pond.
1:03:01
You throw a small pebble right into the middle of the pond.
1:03:05
The ripple created the moment the pebble hits the water spreads out perfectly in a circle.
1:03:09
Doesn't it?
1:03:10
At first, it's a tiny circle or the very immediate area.
1:03:14
Then that circle gradually grows larger and moves to distant areas.
1:03:18
BFS works exactly by the rule of this pond ripples.
1:03:22
Suppose, we start our search from your profile on Facebook's massive network.
1:03:27
BFS won't jump straight away to your friend's friend's friend.
1:03:31
It will first check the profiles of everyone in your immediate circle, that is your first
1:03:36
level direct friends.
1:03:38
Just like that first ripple in the pond.
1:03:40
Once it finishes checking all your direct friends, it will step into the second level.
1:03:45
Meaning it will start checking all the friends of your friends one by one.
1:03:49
In this way, it spreads out evenly level by level to scan the entire network.
1:03:54
This beautiful sequence, first the people close by, then the ones further away.
1:03:59
To keep this sequence in memory, we need the help of a queue.
1:04:02
When Facebook or LinkedIn shows you people you may know or friend suggestions, they are
1:04:07
actually using this magical BFS algorithm.
1:04:10
Now let's think about this in a different way.
1:04:13
In real life, when we leave home to head somewhere, what is our main objective?
1:04:18
It is how quickly we can reach our destination in the least amount of time and at the lowest
1:04:23
cost.
1:04:24
Isn't that right?
1:04:25
This weighted graph from one city to another finding the shortest and best route which
1:04:30
you call the shortest path.
1:04:32
How do we find that?
1:04:33
The world famous algorithm that provides the solution to this great problem is called Diastra's
1:04:38
algorithm.
1:04:39
The funny thing is that Dutch computer scientist Edgar Diastra reportedly discovered this groundbreaking
1:04:44
algorithm while simply drinking coffee.
1:04:47
Assume you are now in Dhaka and your destination is Chittagong.
1:04:51
You have to pass through several cities or junctions in between and every road has a specific cost or a distance in kilometers The core strategy of Mr Dastor algorithm is quite beautiful Forget about the future
1:05:05
At this moment, always choose the cheapest or the closest junction at your hand.
1:05:10
Initially, you are standing in Dhaka.
1:05:13
So, the distance from Dhaka to Dhaka is zero.
1:05:16
And for all the other cities, say Kumilla, Feni or Chittagong,
1:05:20
you don't know their distances yet.
1:05:22
So, for the time being, they are assumed to be infinite or very far away.
1:05:28
Now let's calculate the direct roads that go out from Dhaka.
1:05:32
Suppose one road goes to Narayan Gaunch with a distance of 20 km.
1:05:37
Another one grows straight to Kumilla which has a distance of 100 km.
1:05:42
Diastas algorithm will then quietly note down the cost to reach Narayan Gaunch as 20 and
1:05:47
the cost to reach Kumilla as 100.
1:05:50
Then it will ask itself, well, which is the cheapest city at hand right now?
1:05:55
The answer is very simple.
1:05:56
Narangonj is only 20 km away.
1:05:59
Then without any delay it will immediately move to Narangonj.
1:06:03
Standing there it will look at where else one can go from there.
1:06:06
It says there is a wonderful bypass road from Narangonj to Kumilla whose distance is only
1:06:11
50 km.
1:06:13
Now notice that we previously knew the cost to go directly from Dhaka to Kumilla was 100
1:06:18
km.
1:06:19
But now we see that Dhaka to Narangonj is 20 km and Narangonj to Kumila is 50 km.
1:06:26
Meaning the total cost comes to only 70 km.
1:06:29
Now you tell me, is 100 km cheaper or 70 km?
1:06:34
Certainly 70 km.
1:06:36
Diastra's algorithm will then immediately cross out that old 100 km figure and write the new, cheaper cost there.
1:06:43
The act of crossing out the old calculation and writing the new, cheaper one is called relaxation.
1:06:48
By standing at every junction and always choosing the cheapest path, by the time it reaches
1:06:54
Chittagong, the lowest cost route from Dhaka to Chittagong will be created in your hand
1:06:58
like magic.
1:06:59
And this ability to stand at every intersection and find the shortest path in the blink of
1:07:04
an eye is powered by Diastro's algorithm, which uses a Minhip or Priority Queue, the
1:07:10
very thing we just learned about as its engine.
1:07:14
Today whenever you pull your phone out of your pocket open Google Maps or Uber and see those directions with a beautiful blue line appearing on the screen know that right behind that line our diastasis algorithm and priority queue are working tirelessly Almost all of the thousands of algorithms in the world are fundamentally built upon four core philosophies
1:07:36
Once you grasp these philosophies, you will be able to understand and even create new algorithms
1:07:41
yourself.
1:07:42
The first of these philosophies is called the greedy approach.
1:07:45
In the world of algorithms, being greedy has a wonderful meaning.
1:07:49
The core idea is to stop worrying about what might happen in the distant future for now.
1:07:54
Let's grab the option that seems most profitable or best right in front of you at this very
1:07:59
moment without any hesitation.
1:08:01
To understand this, let's think about a shopkeeper giving back change.
1:08:06
Suppose you go to a store and buy items worth 68 taka.
1:08:10
You give the shopkeeper a 100 taka note.
1:08:13
He needs to give you 32 taka back in change.
1:08:15
The shopkeeper's goal is to return this 32 taka using the fewest number of notes or coins
1:08:20
possible.
1:08:21
He first looks at the largest note in his cash box.
1:08:24
50 taka is larger than 32 taka, so he cannot give that.
1:08:29
Then he picks up the next largest note, which is 20 taka.
1:08:33
Without calculating anything for the future, he greedily hands you the largest 20 taka note.
1:08:38
12 taka remains.
1:08:40
Now to settle this 12 taka, he again looks for the largest note in his box.
1:08:45
He picks up the 10 taka note.
1:08:47
2 taka remains.
1:08:49
Now to settle the 2 taca he simply hands you a 2 taca coin.
1:08:53
Notice how perfectly he settled your 30 taca change using only 3 notes or coins.
1:08:58
At every step he chose the largest option available at that moment.
1:09:03
And that resulted in the best solution for the entire problem.
1:09:07
Taster's algorithm works using this exact same strategy.
1:09:10
But yes, one thing must be remembered.
1:09:13
The greedy approach cannot provide the best solution everywhere.
1:09:16
Where a momentary gain can cause damage later on, we must turn to other philosophies.
1:09:22
Let me give you a small example.
1:09:24
For instance, when you go to purchase an educational course, generally good courses are more expensive.
1:09:30
But you always try to choose the one that is cheaper.
1:09:33
In this case, Triestos algorithm will not work.
1:09:36
The second philosophy is called divide and conquer.
1:09:40
The ancient Roman Empire ruled the entire world by utilizing this very policy.
1:09:45
Their strategy was brilliant.
1:09:47
Instead of engaging in a direct frontal war with a massive and powerful enemy force, they
1:09:52
would strategically create divisions among them, break them down into small groups.
1:09:56
Once the enemies are divided into small and weak groups, you can either
1:10:00
defeat them by fighting each group one by one. And once all those small groups are defeated,
1:10:05
the entire empire will be in your hands. In computer science, this philosophy works in
1:10:10
three steps. The first task is to break the massive problem in front of you into smaller
1:10:15
sub-problems. Next, solve or conquer these small problems individually, usually by using
1:10:22
recursion. And at the very end, combine those conquered solutions together to construct a
1:10:28
complete solution to the main problem.
1:10:30
The merge sort and quicksort that we have heard of are excellent examples of this divide
1:10:34
and conquer philosophy.
1:10:36
Just like merge sort takes 10 million pieces of random data and keeps cutting them down
1:10:40
into individual small pieces.
1:10:42
Then it sorts them into small pairs and conquers them.
1:10:46
And finally it joins those sorted pieces together to give us a perfectly sorted list of the
1:10:50
entire 10 million data points.
1:10:53
Binary search also does the exact same thing.
1:10:56
Every time it opens a book from the middle, helps the problem and finds the correct word.
1:11:01
The name of the third philosophy is Dynamic Programming which is known as DP for short Its core concept is so simple that even a small child could easily understand it Its entire philosophy
1:11:13
stands on a very simple piece of real life intelligence.
1:11:16
Suppose a task or calculation you once struggled to do in the past, write down or remember the
1:11:21
result of that calculation somewhere. If you need to perform the exact same calculation
1:11:26
again later, would you foolishly repeat all that same hard work from the start? Not at
1:11:31
all. You would directly use the previous result you remembered. Suppose I write 1 plus 1 plus
1:11:36
1 plus 1 plus 1 on the board in front of you. How much is it? You count quickly and say
1:11:42
5. Now I add another plus 1 to the far right of the same equation. It won't even take
1:11:49
you a second to find the answer. You will immediately say 6. You didn't sit there and
1:11:54
count from the beginning this time. Because you know that adding the previous 5 ones equals
1:11:59
5. So you simply added the new one to the old result of the 5 that you had remembered.
1:12:05
This magical process of writing down or remembering the results of our past calculations in memory or a table is technically called memoization Think about the Fibonacci series in mathematics There every new number is the sum of the two numbers immediately preceding it
1:12:20
If you ask a computer to find the 50th number of the Fibonacci series using simple recursion,
1:12:25
it will perform the same small calculations billions of times without even realizing it.
1:12:31
It could take hours or even days for the test to finish.
1:12:34
But if you add dynamic programming or memoization to it and tell the computer, hey, just write
1:12:40
down the calculated result in a diary, then the same calculation that took the computer
1:12:45
days to solve will be done in a second.
1:12:48
So whenever you see the same small problem recurring in a complex task, you will know
1:12:52
it's time to use dynamic programming.
1:12:55
And the fourth philosophy is the very familiar backtracking.
1:12:59
We have seen this in the solutions to Sudoku and mages.
1:13:02
you have countless alternative paths in front of you and you have to try them all to find
1:13:07
the correct solution. And if you hit a dead end, you have to step back and take a new
1:13:12
path. That is exactly when backtracking becomes our
1:13:15
best tool Think deeply for a moment Did any of the topics or concepts I just talked about fall from the sky They didn When it became difficult to insert data in the middle of an array the linked list was
1:13:27
born from that very problem.
1:13:30
When we needed to control the sequence of data storage, stack and queue emerged.
1:13:35
When we needed the speed to search for data in the blink of an eye from thousands of records,
1:13:39
hash tables and binary search trees were born.
1:13:42
Again, when we needed to store real-life complex networks and relationships in memory, graphs
1:13:48
came along.
1:13:50
Every data structure and every algorithm is connected to one another at the root.
1:13:54
Together they form a vast and beautiful family that keeps our world of software and technology
1:13:59
running.
1:14:00
Knowing these concepts will create a very powerful and clear map of the entire subject
1:14:05
in your mind.
1:14:06
Now it is time to put this knowledge into practice.
1:14:09
Speak any programming language of your choice and start building the concepts we learned
1:14:13
today in your memory by writing the code yourself.
1:14:16
When you write the code yourself, you won't be blindly memorizing anything anymore.
1:14:21
You will feel exactly what magical events are happening inside the memory behind every
1:14:25
line of your code.
1:14:27
Happy coding!