Skip to main content
Loading Explore guides…
Key Computer Science Algorithms · Acedra
Home
Explore
Computer Science
Key Computer Science Algorithms
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
366 segments
Copy
Hide video
0:00
Welcome to this course on famous computer science algorithms. In this video, I'll explain six key types of algorithms that you need to know and then will come up in any computer science course or potentially technical interviews. Now the algorithms are as follows and can be navigated to from the video player below. So we have recursion linear slash, binary search, sorting algorithms, pathfinding, minimum spanning tree and dynamic programing. And this is meant to be a practical walkthrough
0:27
where I focus only on the parts of the algorithms you actually need to know, and that you'll use on a day to day basis. I don't dive extremely deep, and I don't go into a ton of unnecessary theory. Now, in fact, the videos that you're going to see here used to be a part of one of my premium programing courses that I since made free for everyone on YouTube. Now, with that in mind, if you are someone who's learning this topic to land a software engineering role
0:49
or to pass technical interviews that make sure you sign up for my free newsletter, which I'll link below. Every week I break down a ton of practical tips on career growth, interview prep, and the tech skills that actually matter in this job market. With no fluff and just the stuff that actually moves the needle takes just a few seconds to sign up again. It is completely free, and if you do so, I'll send you over my free guide on how to make money from coding.
1:12
Because believe it or not, you don't just need a job to do this. Anyways, with that said, let's dive in and let's learn about famous algorithms. So in this first video we're going to talk about recursion. Now recursion is again a strategy that you can use to solve a problem. So you can write a recursive algorithm. So the goal here is not just to have you memorize the algorithms I show you, but to teach you how recursion works
1:35
and how you can apply this to any arbitrary problem that you might face. Really, the whole point of this section is to introduce you to all of these different strategies, so that you can have them in your toolbelt when you move on to becoming more experienced developer, and you need to actually write some more complicated code that may involve some of these strategies or some of these algorithms. With that said, let's begin here and talk about recursion. Well, what is recursion?
2:00
Well, recursion is really fairly straightforward. It means we have some kind of function. And within the body of that function we call the function again. That is the most basic example of recursion. So I have some function fn okay. And then inside the function I call it. That means we have a recursive call. That's calling the same function. Now whenever we design recursive algorithms we need to come up with two things. The first thing we need to do is come up with the base case or cases.
2:31
And then the recursive
2:35
case or case is okay, excuse my messy handwriting here. Hopefully you guys get the idea. So a base case is a situation in which we know what the answer to this case is. A recursive case means we are actually going to make a recursive call to this function. Now, in simple recursive algorithms, we have maybe 1 or 2 base cases and one recursive case, but a more complicated algorithm. So we can have multiple base cases and multiple recursive cases. Now when we are defining essentially the recursion
3:05
that needs to occur, we need to know both of these things. And we need to define what both of the cases are. Now I know this is a little bit abstract. So the best way I can show this to use with an example. So we saw in some of the previous videos that we had a Fibonacci sequence. As a quick refresher here, the Fibonacci sequence is one, one, two, three five eight 13 21 etc. where the value of one term is equal to the value of the two previous terms.
3:37
Now, this is a great example of where you can utilize recursion, because what we can do is break this problem into a series of subproblems. And if we can solve those subproblems, then we can solve the entire problem as a whole. Typically, when we write a recursive algorithm, what we're doing is something known as dividing and conquering. We're taking what is typically a fairly large problem, a difficult thing to solve, like determining the nth Fibonacci term and saying, okay, well,
4:04
I don't know how to determine the end, but I know how to determine the nth minus one, or I know how to determine the first and the second. So how can I use some of the subproblems or solutions to those subproblems to solve the main problem? That's really the idea behind recursion. And in a few minutes I'll show you a few examples in code, and this will start to make a bit more sense. Okay, but when we're talking about our Fibonacci numbers here,
4:26
what we need to do if we want to solve this recursively is determine, first of all the base case and then the recursive cases. Now again, the base cases are cases in which we know the answer to the problem. Now you can define many different base cases for Fibonacci. But in this case the two base cases that we need are these right here. So this is the first term and the second term. So what we'll say is the following f at one where f is our function for the recursion is equal to one.
4:56
And f at two is equal to two. And then we can sum these up and say that these are the base cases. So now we have two base cases. Which means if we reach this case we know what the answer is. And sorry this is not equal to two. This equal to one. My apologies. So f of one is equal to one. And f of two is equal to one. These are the two base cases where we know the answer to the problem. And there's no more computations that we need to perform.
5:19
Now that we know what these base cases are, we need to define the recursive case. Now there can be more than one recursive case. However in our case they'll just be one. So I'm just going to put our standing for the recursive case. And this is equal to the following f of n is equal to f of n minus one plus f of n minus two. So what we're doing here is writing something based on the parameter that we have which is n. That will recursively be able to solve the problem for us.
5:49
So we've already walked through the entire call stack. I'm not going to repeat everything we've done in the previous videos, but the idea is if we're trying to look for, say, this term right here. Well, if we can calculate the term before and the second term before. So the previous term and I guess the term before that, then we're able to solve this problem. And if I don't know what the result of this term is, then I would recursively again calculate the result by taking the two previous values.
6:12
So this is a great example of simple recursion where we have one recursive case which is f of n is equal to f of n minus one plus f of n minus two. And then we have our base cases where f of one is equal to one, and f of two is equal to one. And so long as we will eventually reach these base cases, then we're going to be able to solve this problem recursively. Because we know the answer to a very, very small problem. And then we take those answers
6:36
and we move up slowly to answer the larger problem as a whole. Hopefully this is making a tiny bit of sense. I don't want to get too theoretical with you, but this is the notation that you would write if you were writing down kind of the theory for recursion. You define the base case or base cases. There can be multiple depending on the problem. And then you define the recursive cases. In this case we have one recursive case but we could have other. For example,
6:58
maybe we have a recursive case when n is even and then a different recursive case when n. It's odd. Many different things you can do here to solve an algorithm recursively, or not to solve, but to create a recursive algorithm. Again, this is kind of known as divide and conquer. I'm saying okay, to solve this problem I need to solve these two subproblems. To solve these two subproblems, I solved these two subproblems, so on and so forth. Okay. So that's it for the theory here.
7:21
Now I actually want to go to the computer and show you some code to make this more clear. We'll begin here by writing a function. We'll call this fib for Fibonacci. And we'll take in one parameter n. Now remember we need to start by defining our base cases. So I'm going to say if n is less than or equal to two then return one. Okay. So this means if we're passing in 1 or 2. Also if we pass zero we're not going to be doing that. But if for some reason we did we would just return one. Okay.
7:47
So this is our base case and that handles those two base cases. I discussed where we have an equal one or an equal two. And that means we are returning the value one. Okay. So we can kind of comment this and say this is the base case. Then we have our recursive case. Now the recursive case is simply the Fibonacci of n minus one plus the Fibonacci of n minus two. Very straightforward. Probably the most basic example of recursion we can use. All we're saying is that if we are not in our base case,
8:16
then we need to go to our recursive case and the recursive case means that we're taking the previous term plus the second previous term and adding those together. So let's have a quick look at this. I'm going to say console.log. Let's go up here and say const result is equal to the Fibonacci of something like five. And then we will log our result. So I'll say node program js and we get five. That's correct. If I do six here we get eight
8:43
seven we get 13. Okay. So this is working correctly and giving us the correct Fibonacci terms. Now let's have a look at what happens if we try to call this on a very large number or a very large term, like 70. If I run this notice that this is actually going to take an extremely long amount of time. In fact, there may not even be enough time for me to execute all of this code because the time complexity of this algorithm is so poor.
9:12
Remember, the time complexity of this is Big-O of two to the exponent n, which means it's going to take two to the power of 70, which is an exponentially massive number relative time to run. So this is still running. It still hasn't finished yet because of how poor the time complexity is. So I want to show you there's actually a way that we can significantly increase the speed of this type of algorithm. It actually involves not writing this recursively.
9:40
So since we're doing this recursively, what happens is we have two different base cases that we need to solve for every single case. And then we're going to recursively keep adding to that as we increase the value of n. So you can see that small values of n it's not really a big deal. But as n gets like 20, 30, 40, 50, 60, 70, etc., it becomes infeasible for for us to actually run this algorithm, which is one of the main reasons why we even talked about time complexity.
10:06
Because if you have a time complexity like this, well, this function is pretty much useless when it comes to large terms of n. So let's see how we can rewrite this. All right. So what we're going to do here is write a new function. And we're going to call this fib memoized. Now what this is going to take in is n and a calculated object that has our base cases inside of it. Now we just quickly explain something when we're looking at this Fibonacci function right here.
10:33
The reason it's so inefficient is because we're constantly recalculating values that we already have calculated in the past. For example, if we look at calling Fibonacci with the value five, well, the first call that we need to make is two Fibonacci of four plus Fibonacci of three. But then Fibonacci of four, right. If we go down here, this requires the call to Fibonacci of three plus Fibonacci of two. Three requires the call of two plus one. Now we can continue with this,
11:00
and you'll see that every single time we increase the number. The term end here that we're calculating, we're constantly doing more calculations, repeated calculations of things that we've already calculated. So already here we've calculated three twice two twice. We're going to calculate one, two and a bunch of these other values multiple times. Now if we only needed to calculate them one time, that would drastically reduce our time complexity.
11:25
In fact, if I only needed to calculate each Fibonacci term one time, I would be able to run my algorithm in the big O of N time, which is what we can actually do here
11:38
when we go and add something known as memoization. So memoization is essentially a cache. Now a cache is a place where we're going to store values that we've already computed, meaning we only need to compute each Fibonacci term one time. If we do that, then that allows us to actually run this algorithm much faster, and then simply look at the values we've already computed, rather than recomputing them each additional time. So let me show you how we write that code.
12:04
So let's begin by first checking if the key n is in the calculated object. If it is, then we can simply return calculated at property or key n, which will then give us the values. Right now I've just written to the value one and two, which are base cases inside of this calculated object. Next, what we'll do if we haven't already computed this value is we'll compute it. So we'll say if or not. If sorry we'll say const result is equal to the fib memoized of n minus one.
12:40
And we're going to pass this calculate object again plus the fib memoized
12:46
of n minus two. And again this calculator object. Then we're going to say calculated at n
12:55
is equal to the result. And then we'll simply return the result. Okay. So the only addition we've made here is that now we're reading from our memoization cache. And we are storing whatever value we make inside of the cache before we return it. So we calculate the result stored inside of calculated and then return the result. So now if I call my fib memoized with 70 and we say const result
13:26
and we console.log, the results and I go here and run this code, you'll see that we actually compute this value almost instantly. We've gone from a Big-O of two to the exponent n time to big o of n time by making this very simple change to our recursion. So you don't always need to do this, but in this situation it's helpful because since we have two recursive function calls that we're making, and these end up going down different stacks that repeatedly
13:53
call the same values or compute the same values. If we store those, that drastically increases the time complexity of our algorithm. I won't go too much further into that, but I'll now show you one last way that we can write this Fibonacci algorithm iteratively. That's going to actually solve this, even a little bit better. Now it's going to be the same time complexity, but it's going to have a reduced space complexity. So when we use recursion here,
14:16
one thing that we haven't really talked about is the space complexity. Now the space complexity is essentially how much space is taken up in your computer's memory. I don't want to get too much into it, but when we're looking at something like having this memoization cache, that means that we're going to have big O. That should make this in a comment, but that's fine. Of N space being used for this algorithm. The reason for that is we're going to be storing
14:38
at most n elements inside of this cache, which means we'll be taking a big O of n space, right? So the time complexity and space complexity work pretty much the exact same way. But with space, we're just concerned about the maximum number of elements or space that we would be taking up. So in this situation, it's big O of N space because we are storing all of the different results that we've already calculated, and there is actually a way to reduce the space to constant space.
15:03
And the way we can do that is with this last algorithm. So function fib iter which stands for iteratively I'm going to take in n here. And I actually don't need to use recursion to solve this Fibonacci problem. Obviously the whole point of this video is to show you recursion, but I'll just show you the iterative approach because it's a very famous algorithm. Okay. So inside of here, what we're going to do is we're just going to write if n is less than or equal to two then return one. Okay.
15:30
Just to kind of handle the base case here so that we don't need to handle that in the next line. So I'm going to right now what I'll do is I'll define two variables last equal to one
15:40
and second last equal to one as well. Now this is going to be for term two. And this is for term one okay. So the idea here is that I don't actually need to store every single result that I've calculated. All I need to be able to calculate the nth Fibonacci term is the nth minus one and the nth minus two term. So what I can do is calculate those starting from the very first term. Move my way up will always keeping track of the previous two terms and then I will solve the problem.
16:13
So let me show you what I mean here. But again what I'm doing is I'm now kind of mitigating this recursion and saying, okay, if I just keep track of the last and the second last term. Now once I get to n, I know what the value is. I can just add those two terms and return. So I'm going to say for let I equal to I is less than n
16:33
and I plus plus I'm saying I equal to two. Because in this situation we've already said that I's going to be greater than or equal to two, because if it wasn't, we would have returned here. And then we've defined that the last and the second last term are these two values. Now what I need to do is just update the last and the second last term. Well, first of all, the last and the second last term are going to be kind of relative to each other. So the second last term now as I move through this
16:58
for loop is going to be equal to the last term. And the last term is going to be equal to itself plus the second last term. Because what I'm doing every time I iterate through this for loop is I'm essentially increasing n, where n is the Fibonacci term that I'm calculating. So I start by calculating the third term, then the fourth and the fifth and the sixth, so on and so forth. And to do that I use these two variables. So what I'm going to do is say const temp is equal to last.
17:24
I just need to store with the current value of this last term is. Then I'm going to update the value of the last term. So I'm going to say last is equal to last plus second last. And then I'm going to say second last is equal to whatever last was equal to before that. Okay I know this is a little bit confusing, but I'm saying all right, now I want to calculate whatever the term is. So to calculate this term I take whatever the previous term was. And I add whatever the second previous term was.
17:50
Now though I'm going to store that in last, because now that's the last term that I calculated. And then the second last term will just be equal to whatever this was equal to before I did this addition. So now all I need to do down here is simply return whatever the last term is, because that will be the nth term. Once I get through this entire for loop, I don't want to explain it too in-depth. So this is the iterative approach. And now if we do something like const result is equal to fib itor
18:17
add something like 70 and then we console.log the result. If I go here and run this, you can see that we get the same result that we got when we called fib Memoized. Now this is going to run in big O of N time because we have a for loop that's running N times. However, we're going to use constant space because we no longer have this memoized cache or object that we need to be reading from. Okay, so that is the Fibonacci sequence. All three of these algorithms are extremely famous
18:45
and that's why I wanted to show them all to you in this video. Now let's just quickly comment the time complexity. So this is big O of N time and big O of N space okay. And then this will be big O
19:00
of N time and big O of one or constant space. Now I'm not going to go through the space complexity of this one, but there is actually a space complexity that is larger than constant time. Okay. So we're not going to look at that right now because I don't want to get too far into the weeds there. Let's move on to the next algorithm okay. So for this algorithm what I want to do is show you how we traverse a binary tree. So let's make a comment here and just say binary tree traversal.
19:26
And let's go up here and we'll just do a kind of a header comment and say this is fib. Now I'm going to make this code available to download afterwards. Hence why I'm kind of mark it up, marking it up for you. Sorry. So first of all, for our binary tree traversal, I want to show you how we recursively do the in-order preorder and post order traversal. In order to do that though, we need a binary tree. So I'm just going to bring one in here.
19:46
We have a node object that has a value left and right property. We have a constructor for creating that node. Now what I want to do is initialize a binary tree using this node object. So I'm going to paste this in here. And what this does creates a binary tree that looks like this okay. So we have our head node node 23456789 ten. Notice I'm kind of, defining them in reverse order because I'm using one of the previous nodes that I defined inside
20:12
of one of these nodes constructor to set it to be the left or right child. So in this case, my head node, which is one, has a left child of two and a right child of three. So that's what I've defined right here okay. You can read through that more using this node class. All right. So now that we have a binary tree that is represented with our head, we can write an in-order preorder and post order traversal. So to do this we'll write a function.
20:37
We'll call this function inorder and we'll take in some kind of node. Now remember the inorder traversal goes left visits the node and then goes right. So first thing I'm going to check is if the node is equal to no. If it is we'll simply return because there's nothing we need to do. Otherwise we'll call inorder on the node dot left. And then we will say console.log
21:02
the node dot value. And then we will say in order on the node dot. Right. And that's it. Actually we just wrote the inorder traversal for a binary tree. So we're just breaking this problem down into subproblems and then solving it recursively. So the base case is if the node is equal to no. If that's the case we don't need to do anything right. We've reached kind of the end of that recursive call stack. So we simply return. Now the recursive cases are these where we visit the left
21:30
and we visit the right note. So visit the left. Print out the value and then visit the right. That's the inorder. Now let's copy this and do the preorder which is going to be extremely simple.
21:42
So we're just going to change these to say three. And now I'm just going to print my node value before I visit the left and the right. There you go. We've just implemented the preorder. And now if you want to do the post order we'll write post
21:57
post post. And now we just put these before we print the value. Okay there you go. We now have the inorder preorder and post order all working recursively. So let's try them out. Rather than me writing out all of these prints, I'm just going to paste them here. So console.log inorder. Then we do the inorder. Then we do the preorder. Then we do with the post order. Let's give this a quick demo. Node program js. Let me just make sure I'm not calling my Fibonacci. I'm not. Okay. That's good.
22:29
Let's make this full screen here. And you can see that we get the inorder traversal of the tree, the preorder and then the post order. Now trust me these are valid. I'm not going to go through and explain why these are the case. We've already looked at how we do the pre post and inorder traversal in that binary trees video. All right. So moving on. The last thing I'm going to show you is a more abstract algorithm which allows us to reverse a string using recursion.
22:57
Now obviously reversing a string can be done without recursion. But I just want to show you another way that we can write a recursive algorithm. So let's say we have a string. So const str is equal to something like Tim is great.
23:10
Well how do I reverse this. Well to reverse this I simply write all of the characters in the string starting from the end back to the beginning. Right? So I take the exclamation point, the T, the E or sorry, the A, the E, etc. and I just write them backwards a little bit. Easier said than done, but that's the premise. Now in JavaScript we have some built in ways to reverse this string. Kind of some shortcuts to do this.
23:31
We can also just write a for loop, where we just loop through the string backwards and write all of the characters into a new string forwards. But we can also do this recursively. So let me write the function. Then we can explain it. Let me just write above the string here. So we're going to say function reverse string. And we're going to take in a string. We're going to say new string is equal to an array. Now what I'm going to do is append all of the new characters
23:56
for my new reverse string into this array. And then I'm going to join those characters together at the end, to create the new string. The reason for that is that it's a big O of one time complexity operation for me to insert an element into an array. Whereas if I have a string and I try to add something like one to this string, what actually happens is I need to rewrite the entire string, which is a big O of k time operation, where k is the length of the string.
24:29
So if I use a string and I can caffeinate to a string, this takes me whatever the length of the string is time length of the longest stringer length of the two strings combined. Whatever you want to write out here, regardless, is going to take me that length. Because again, I need to rewrite the string because this is an immutable object, whereas since the array's mutable, I can simply write into that array in constant time by pushing elements to the end,
24:52
rather than having to remake the entire array every single time. So that's kind of a little thing to remember here. When you're concatenating to a string, that's a big O of N or big O of K, depending on how you want to say it. Operation. Whereas when you are appending to an array or pushing into the array, that's a constant time operation. Okay, so first thing I'm going to check here is my base case. So I'm going to say if the string dot length is equal to zero then I'm simply going to return.
25:16
So if I have no string to reverse well then I don't need to reverse it so I can return. Now what I'm going to do inside of this recursion here is I'm essentially going to reverse the string one character at a time. So the reversal of a string can actually be written like this string or the reverse string is equal to reverse string dot slice one plus whatever the string at the first index is. Now, I know this seems a little bit strange, but essentially what we can do
25:47
here is reverse the string one character at a time. So we'll say that if we're looking at this string right here, the reversal of this string is equal to the reversal of the rest of the string. Plus the first character. Okay. So that means the first character will be at the very end. So again, we're kind of writing it like this where we say
26:10
that this. So the reverse of this plus t is reversal of this entire string. That then means if we're looking now at this instance here, the reversal of this string is equal to the reversal of this.
26:28
Plus I. And you can continue and break this down until eventually you get to a string that has one character or no characters. Right. So the reversal of a string, the zero characters is zero. The reversal of a string is one of one character is just equal to itself. And then again, you can kind of repeat this process and break it down until you get to the smallest possible case, which is where the string has no length. I know this seems abstract.
26:53
Let me just write this out and we can kind of walk through it step by step. Okay. So we have the base case, which is the instance where the string length is equal to zero. Now what we're going to do is we're going to grab the first character from the string. And we're going to store that in a variable. Then we're going to say reverse string. And we're going to reverse the string slice which will simply remove the first character from this string.
27:16
So reversing all of the characters except the first. And then we'll pass inside of here the new string array. Then what we'll do is we'll say new string dot push, and then the character. So what this means is we're going to reverse the entire string. And once we've reversed the entire string, then we're going to push this new character to the end of it. So again the reversal of any given string is equal to the reversal of the rest of the string, plus the first character in that string,
27:45
which takes the first character and moves it to the end of the string.
27:50
Now I'll print this out so you can see what's happening, but I'm going to come down here now and say, if the string dot length is equal to the new string dot length, then return new str dot join and we'll just put an empty string inside of here. Now what this does is create a string out of an array of characters, which is what it will do. And I'm only doing this if we're in the case where the length of the string that we have here that was passed in
28:18
is equal to the length of this new string array. Okay. So let's just make sure this works. I'm going to say const result is equal to reverse string str. And then I'm going to say console dot log
28:33
result okay. I'm going to come here and print this out. And notice that I get my reversed string. Now we just comment these out here. So I don't need that right now. Okay. Let's run that again. And you see we get the reversed string. Okay. So now let's print this one step at a time. What I'll do is I'll say print. And actually what should we print here. I'm wondering the order we should do this in. So actually I'm going to go here and I'm going to say console dot log.
29:02
And we're just going to print the string. And then the new string, before we push this character in. And actually no we'll do this after in this case right here. Okay. So let's have a look here and run this program. Now I know we get quite a bit of output here, but you can see that the very first string that we end up actually adding into this new string array is the exclamation point. Now, the reason that's the first string is because that's the first instance
29:26
where this function call just returned. It didn't go into another kind of stack or another, recursive call. So as soon as we hit the exclamation point when we call reverse string, that simply gives us nothing, right? We just return here. So then we take whatever character we had, which is the exclamation point, and we push that into new string. Then we print that out. We check this, we say, okay, we don't need to return anything.
29:50
And then we continue the process, which means then we're going to go back to whatever called the call that just added the exclamation point into this string. So now we have to make sure point right. So what we do is we have the exclamation point which is already inside of a new string. And then we append the t. We push that in because we had to first reverse this string before we could add this character to the end of the reverse string. Then we come to this where we have a t exclamation point.
30:18
Now we have exclamation point t, and then we add a. So after we reversed this substring or sorry, this substring t an exclamation point, we added this character to the end. And you can repeat this process and see that we continually reverse all of these substrings. One character at a time, until we get to the point where we're at the very last substring and we're adding t. Okay. Now, I don't know why it's skipped some of the outputs. I think it just didn't all fit in the terminal. Okay.
30:44
So there you go. You can see now the rest of the output is here regardless. That's kind of how this works. I know it's a little bit abstract. I didn't go into a ton of depth here. I don't want to spend like 30 minutes per example explaining this. I just wanted to show you that we can be very creative here when we're doing something like recursion, and we can come up with ways to recursively solve problems that we didn't think we could solve. The main premise, again,
31:05
behind recursion is we're breaking the problem down into smaller problems. And once we do that, we're then able to solve it recursively. So if I was writing the recursive notation for this, I would say that the reverse of some string is equal to the reverse of the string slice at one. Okay. Plus and then whatever this string at index zero is. Now I know we already wrote that out, but this is the recursive case. Whereas the base case is one string length is equal to zero.
31:39
Then we just return an empty string or we return nothing okay. That's the base case. All right. So with that said I think I'm actually going to wrap up the video here. This was all that I wanted to show you just a few different recursive algorithms to give you a sense of how we would go about using recursion and actually implementing this in code. So first of all, what is a searching algorithm? Well, searching algorithm is just an algorithm that searches for a specific value.
32:01
It can be searching to see if something exists. We're searching to find the position of that element. So if we have some array here and we have some kind of random values here inside of the array, we know that if we want to locate a value inside of this array or see if it's present, that's going to take us big O of N or linear time. The reason for that is what if I wanted to see if, say, element seven exists inside of this array?
32:27
I would need to look through at most every single element in the array to a say that it doesn't exist, or b find the location where it does exist. Now, in some instances it could be the first element. In that case we get lucky. This would be very fast, but if it was the last element, we'd have to look through all of them before we find that. So just kind of a quick recap here. This is a linear search. We've done this all the time. We know this time complexity.
32:51
And I just wanted to refresh you on that.
32:53
So now imagine though that our arrays structured a little bit differently. For example, maybe we actually have a sorted array.
33:06
Well if we have a sorted array then that actually means that we can find elements a lot faster. The reason for that is now the positions inside of these arrays for the elements are not arbitrary. It's actually based on some kind of ordering. So let's say I wanted to find the element three, but I know that my array is sorted. Well how can I go about locating three now? I no longer need to search to every individual element. What I can actually do is use an extremely efficient and popular
33:39
algorithm known as binary search. Now, the reason it's called binary search is because you are essentially splitting the problem in two, or having the size of the array that you need to search through every single time you do a search operation. The reason for that is that since we know this is sorted, I can either look to the left or to the right of any individual element, and I can narrow down my search quite quickly. Let me show you what I mean here. So let's say I'm looking for three.
34:11
Well, what I can start by doing is picking the element that exists in the middle of my array. I can say, okay, well, I'm going to look directly in the middle of my array, and I'm going to see what the value of this element is. Now in this case it's seven. So since it's seven I take my value three and I compare it to seven. And I first of all say are these equivalent? If they are I've just found the index where three exists and I've kind of completed my search.
34:37
If they're not, that means that any elements to the right of seven are not going to be three, right. Because all these elements are greater than seven. So the only remaining elements I need to look through are these over here in the kind of left half of the array. So now I can repeat the process and I can pick the middle element again. Let's say I pick the element two. Now I know that's not the element middle element. I'm just picking it here so that we can kind of continue with this example.
35:04
So let's say I pick two now okay. Which is relatively in the middle of these elements. Well now what I can do is I can look again to the left and to the right of two. So at this point we've kind of narrowed the array down to this. And really we've narrowed it down to this because we know that seven is not the element. So now I'm looking at two and I'm saying okay well I'm looking for three. Is three less than or greater than than two. Well it's greater than two.
35:27
Which means I don't need to look at any of this part of the array, because anything to the left of two is going to be less than that. And will my elements greater. So now that narrows me down to this subarray right here of three and four. Now I can pick either element. Let's say I pick three will I've now found my element. Let's say I pick four. Well I know it's not four. And then the only remaining element would be three which is right here.
35:49
Hopefully you kind of get the idea here, but what we're doing is we're essentially narrowing the search by having it every single time. So if we do another example here where we're searching for element, say 14, we'll repeat the process. Look at the middle element is a greater than or less than. Well it's greater then that means we no longer need to look through any of these elements. We just need to look to the right of seven. And sorry, I kind of deleted too many here. So let's go up to that.
36:17
Okay. So now we're only looking in this now again pick the middle element okay. Is a less than or greater than greater than. So we delete all this. And actually now we're just looking here. Obviously the middle elements of an array with one element is simply that element. So it is 14. And we have found that now we could continue here. And if we had an element like 16 well what would happen is when we get to this point, we'd see that there's no more elements.
36:45
And then that would mean that 16 does not exist inside of this array. So that is the binary search okay. And the binary search is extremely efficient because again we're having the problem every single time. Now you can implement a binary search recursively, which is actually what we'll end up doing. Now. The time complexity of this search operation in the binary search is log base two of n, where n is the number of elements inside of the sorted array.
37:11
Again, this only works when the array is sorted, because we know one of the properties of the array, which is every element to the left is less than every element to the right is greater than or equal to. That allows us to do this very efficient search. So I have this massive array. Well I start by splitting the array in half. So again let's just do an example here. Let's say we have an array of 1000 elements. So we start by looking at the entire thousand elements.
37:33
Then we split this in half and we're only looking at 500, then 250, then 125. And then this is what 62.5 okay. And then you get down here to what's this going to be something like 31.75 etc.. Okay. You just keep doing the math. And you having, having, having, having and you end up getting the time complexity of log base two of n. So very quickly you can search through a very, very large structure if that structure is sorted. Now one thing to keep in mind is that if we want to sort something
38:03
that's going to be a n log base two of n time complexity operation. Okay. So sometimes it may actually be in your favor to first sort some type of structure. Then look through the sorted structure with a log base two of n time complexity operation. Not always. Sometimes it's actually better just to do some type of linear search, but if you need to do repeated linear searches and it's okay for you to sort the array first, you can save yourself a bit of time by first sorting the array.
38:30
So anyway, so that was the algorithm. On to explain on the whiteboard here. Just so you understand how that works. That is the binary search where you constantly split the array in half and search through one of those halves, giving you that log base two of n time complexity. With that said, let's now go over to the computer. I'm going to show you how to implement the binary search. And then we're going to look at a depth first search and a breadth first search
38:53
and just see their code implementation. All right. So I'm on the computer here. And we're now going to implement the binary search algorithm in JavaScript. Now we're going to do this recursively. And essentially the recursive case is that we're having the array right. So we're just looking through one half at a time. That's how we're doing this recursively. And then the base case will be the situation where the array is no longer large enough for us to search net.
39:16
So there's no elements inside of the array. There's only one element. In that case we can determine if the element exists there or not okay. You'll see what I mean as we start writing. So I'm going to say function. Let's just call this search. And what we need to take inside of here is some kind of array, some kind of target. And then a start and end index to look at inside of the array. So rather than creating new versions of this array that are slices of the array
39:42
which will take us whatever the size of the slice time is, we're simply going to look at a start and end index inside of the array. Okay. Hopefully this makes a bit of sense, but that will also allow us to access whatever the index inside of this array is. For the element that we find you'll see what I mean as we go through this. But rather than recreating arrays, we're just looking through a section of the array using this start and end index. Okay. So what do we need to do here.
40:10
Well we need to say first of all our base case. If the start is greater than the end then we're going to return false indicating that we did not find the element that we're looking for which is the target. The reason this is the base case is because we'll be switching both the start and the end, as we recursively call this function. If the start eventually becomes greater than the end, that means we've exhausted the search and looked through all of the different elements.
40:38
Next, what we need to do is determine what the middle element is. So we're going to say const middle is equal to and this is going to be math.floor.
40:47
And then we're going to take the start index plus the end index and divide that by two. So just as a quick illustration here let's say we have our sorted array okay. We have index zero there. We have index seven here. So when we first start searching through this array we take zero plus seven. We divide that by two. That gives us 3.5. We then floor that. That gives us index three which is 123 okay. So now we have the middle of three.
41:17
Now let's say we start searching on the right side of the array. Well now we have three and then index seven. Right. So what I do this is my start. This is my end. So I take these add them together. That's ten. Divide them by two. That's five. So now that tells me the middle element is at index five okay. So that's why we're doing this. To determine the middle we take the start plus the end divide by two. And that gives us the middle or the yeah.
41:41
Just the middle value in between those two numbers. Just kind of some simple math there. Okay. So now we're going to check if whatever the array at the middle index value is. And we're going to see if this is equal to our target. So we're going to say if array middle is equal to target then return true indicating that we found the target. We also could return the index which is simply middle which is where this element exists. Okay. We might not care about that. We might care about that.
42:10
It doesn't really matter for this example for right now, we're just going to return true. And this will say found the elements. All right. Now let's continue. So if we didn't find the element at the middle index we need to see if we have to look on the left side of the array or the right side of the array. So we're going to say if array at middle is greater than the target
42:34
then what that means is that we need to look at the left side of the array. So we could write this the other way around. But essentially this is saying if the target is less than the, middle element in the array, then we need to look left. So how do we do that? Well, we return the search with the array.
42:53
The target, the start and the middle. But this time we're going to say middle minus one because we've already searched what the middle element is okay. So we're now recalling this. And all we need to do is change what the end is equal to to be the middle index minus one. Because we've already looked at the middle. Otherwise we can simply return the search at array target. Then this is going to be middle plus one and then the end. So now we're changing the start to be equal to the middle
43:28
plus one rather than the end. Because we're looking on the right side of the array. That's it. That finishes our binary search. So now let's see how this works. All right. So we need a sorted array. So we're going to say cons are is equal to 123456789 ten 1112 1314 okay let's pick a target. We'll say
43:51
const target equals I don't know. Let's go with 11. And then we are going to search. So we're going to say const result. If we spell const correctly is equal to search. And we're going to search the array okay for the target. And we're going to start at zero. And our end element is going to be the array dot length minus one. Because that is the last index inside of our array. Perfect. Then we can console.log the result. And this should tell us if the element exists.
44:28
Let's go ahead and run this and notice that we get true. Now let's put an element that doesn't exist. Something like 15. When I run this we get false sweet. Now what I want to do is just print out the number of operations and actually the array that we're looking through as we're doing this, just so that we get kind of some sense of what's going on here. So what I'm going to do is at the beginning of this function, I'm just going to print out the array from the start to the end index.
44:53
You can see how we kind of narrowed down these values. So not print but console.log.
44:58
Now this is going to essentially ruin the time complexity. But that's fine. I just want to show you what's going on here. I'm going to say start and then end. And this is actually going to be and plus one. Okay. Now let's go here and print this out. And let me just make this a bit larger. You can see the arrays that we look through. So we look through this array. Then we look through this subarray which is kind of from the right side here.
45:22
And then we look again to the right and then again to the right. We don't find it. So we have false. Now if we switch this to something like two, an element that does exist and we print this out, you can see we search through the entire array. We search through half the array, search through another kind of half here. And then we find the element to there you go. Those are all the operations that are being performed. All right. So that is our binary search. Now let's remove this.
45:49
All right. So moving on. We're going to get into depth first search and breadth first search. And what I'm going to show you is actually how we would navigate a maze using both of these algorithms. All right. So what I'm going to do here is just paste in a maze. I actually got ChatGPT to generate this for us. And what I'm going to do is show you how the depth first search and breadth first search algorithm works when it comes to traversing this maze.
46:11
Now, I'm not going to show you something like a shortest path finding algorithm. That's a little bit more complicated. All I'm going to do is essentially run, first of all, the depth, first search on this maze, which will go through and traverse a bunch of the different positions until it finds this x. The X is going to be our finish. These pounds are wall, and these spaces are going to be a valid path that we can go through.
46:33
So we just want to see kind of where the depth first search is going to move and how it's going to locate this X versus how the breadth first search is going to locate again is not a super practical example, but I just want to show you writing, these kind of algorithms here when it comes to traversing something like a maze. So I'm going to make a function here called DFS, which stands for depth first search. And I'm going to take in an array. Now what I need to do here.
46:56
First of all I just need to make a set called visited, which is going to store all of the elements that I've currently looked at in the depth first search. Now, the reason I need this is because unlike binary trees, we're actually going to have circular references here to the neighbors of different positions to walk you through the basics of how the algorithm will work. I'm going to look at some position in this case zero zero. Right. The position is going to be kind of like x zero, y zero.
47:21
That's how I'm going to represent the different positions in my array. So we have all of the different y values which are rows or individual arrays, and all of the x values which are the column positions. So I start at zero zero. I look at this position, I see that it's an empty string or that it's a space. So what that means is that this is a valid position to traverse. And I now need to look at all of its neighbors. So the left up, right and down element. And see if I can move to any of those.
47:45
In this case, the only valid neighbor to move to is downwards. So that's fine, I move down, but now when I come down, I need to find the neighbors of this position. The only valid neighbors are up and right, but I've already looked at up, so I don't want to go back to up, because if I go back to up, then that means that I am going to keep repeating this process, right? So if I go up, then down, then up, then I would go back down again and I would just keep moving between the same elements.
48:11
So I need to keep track of which ones I already looked at inside of some type of set. All right. So that's the first thing. Now that we have that we need to make a stack that we're going to use to traverse our different elements. So we're going to say count stack. And for a stack we can simply use an array implementation. So I'm going to say stack is equal to an array. And inside of the stack I'm going to put the string which is going to be zero.
48:38
And inside of the stack I am going to put the array which is zero zero indicating that I'm looking in row zero and column zero or column zero, row zero. However you want to read it, you got to just pick what direction and go with that. In my case, I'm going to go with y x where this is the row and this is the column okay. So I've put that inside of my stack. Now what I'll do is I'll go through my stack and I will perform the depth. First search until I find this x element.
49:06
Then I will have all of the different positions that I've visited. Then what I can do is look through those positions and I can insert them into this maze, and we can see the path that we followed. For the depth first search. Okay. So what I'm going to do is this while
49:20
the stack dot length is greater than zero. And this needs to go inside parentheses like this. All right. So the first thing we need to do is pop off of our stack. So we're going to say const position is equal to stack pop which pops from the end. And then what I will do is I will take this element and I will add it into the visited set. Now the issue here is that I can't add an array into a set in JavaScript. Well, I can, but if I do that, it's not really going to work how I want it to work.
49:52
So what I need to do is I need to make this something known as serializable. Now, I know I completely butchered that word, but essentially I'm going to convert this position into a string and then put that string version of the position into the set. Because we can actually check for unique strings inside of the set. I know this is a really bad explanation that I'm giving you, but essentially, if I insert two arrays, these arrays are going to be inserted
50:15
as object references, not the actual array values, which means that I can insert an array that looks the same multiple times into my set. And it doesn't kind of mark that as a repeated element. All those arrays are going to be unique, which isn't what I want. So what I need to do instead is use strings to represent my positions and insert those into the set. Kind of an annoying feature in JavaScript, but it is just what it is. So I'm going to say function get string pause.
50:41
This is going to take in some position. And all this is going to do is return a string that represents the position. So I'm going to say that we have a backtick string here. And we're going to have pause at index zero. And then we'll go with comma and then pause.
50:57
Let's do the variable here at index one. Because we know this is always going to have two elements. So now we're going to get strings that have something like zero and one where zero is the row, one is the column. And then we will be able to do is parse these strings later on if we need to do that okay. So now that we have this we are going to get that string. So we're going to say const string pause is equal. To get string pause of the position.
51:21
And we're going to insert this into the visited set. So we're going to say visited dot push. And then this will be the string position. Then we are going to look through all of the neighbors of this position that are valid for us to loop through, and we are going to add them to the stack and search through them. And we're going to continue doing this until eventually we find our X. So that actually reminds me that what I need to do here is I need to say if and then this is going to be
51:51
array at pause zero and position one. Because again remember we're doing the row first and then the column. And in fact we can even do this const y x is equal to position. And then we can come here and say y x. And we'll just put this inside of an array so we don't get yelled at okay. So now that we have that we'll say if this is equal to x then we can return like that okay. Which means we simply stop or actually we don't need to return. We can just say break.
52:27
So we break out of this while loop because now we found the ending position. Don't worry, I'll walk through all this code at the end. I know it's a little confusing as I'm kind of stepping through it line by line. Okay, so now what we've done is we've popped off the stack, we've gotten the Y and x coordinate of this position. We've checked if this is equal to x. If it is we're breaking out of the loop. Otherwise we're going to get the string version of this position. Add that to our visited set.
52:51
So it's actually going to be visited add not dot push. And then we're going to loop through all of the neighbors of this position that are valid. And we're going to add those to our stack and then start searching through those. So now we need another function called get neighbors okay. This is going to take in an x y. And it's going to return an array that contains the neighbors. So we're going to say const neighbors is equal to this. And then we're going to look and see
53:18
what positions are valid for us to add as neighbors. So we're looking at the left right top and bottom. So let's do left. So to check if a position is valid going to the left we need to make sure that it's inside of the array. So it's not outside. So we actually do have a left that we can go to. And then it's not equal to this pound symbol.
53:35
So we're going to say if x is greater than one greater than or equal to one. And we have what is this. We need the array actually as well here. Sorry. So error and error at index y x minus one does not equal a pound symbol. Then we can say neighbors dot push. And then we're going to push inside of here an array that contains y and then x minus one. So all we're doing here is seeing okay for the current position we're looking to the left to look to the left.
54:14
We need to make sure that we do have a left position to look at so that the current index is greater than or equal to one. We're then going to go look at that position. So for the y value at x minus one we're going to make sure it's not equal to an obstacle. If it's not then we push this in. Now the exact same thing pretty much is going to apply for the right. Except it changes a little bit. So we'll do a comment here and we'll say right. And we'll say if X is less than
54:38
the array dot length. Now we're going to assume that the array is a square size. So this will work for us. We also could do array y dot length just to make sure that we're accommodating. If the array is not a square size because we're checking for the column position we need to see. However long or large the size of the row is that we're currently inside of. I know it's a little bit confusing when we say if X is less than this dot length minus one,
55:06
okay, that means that we can move to the right without being out of bounds. Then we're going to say array y at x plus one does not equal this. Then we'll add x plus one because we're moving to the right okay. Now we need to do top bottom. So we'll do top paste this in. Now it's going to be if array y
55:24
is greater than or equal to one and array at y minus one x does not equal that. Then push y minus one and then x okay. And then we'll copy this for the bottom. So now we're going to say if y is less than the array dot length minus one and array y plus one. And then change this to plus one. Then come up here and return our neighbors. Okay. Let me make this full screen so we can actually read all of it. So I'm writing a function that returns all of the valid neighbors
56:04
that we can visit from any given position in our array. All right. So now we need to get those. So we're going to say const neighbors is equal. To get neighbors pass our array and then pass our x and our y value. And now we need to loop through all of those neighbors, make sure that we haven't already visited them. And if we have visited them, visit them. So we're going to say for const
56:28
neighbor. So we're going to say so we're going to say for const if we can spell this correctly, neighbor of neighbors,
56:44
then what we'll do here is make sure that we've not visited this neighbor. So we're going to say const string. Neighbor and I keep spelling this incorrectly. Excuse me. Here is equal. To get the string position of our position which is the neighbor. Okay. Let's just have a look at this getString position. Yep okay. So that works fine. We're going to say if the visited dot has the string neighbor.
57:16
Then continue because we don't want to visit this. Otherwise we're going to say stack dot push the string neighbor just like that okay. So we're pushing all these elements onto the stack. All right. That actually is pretty much all we need to do. Then what we're going to do here is we're going to return the visited set. And this is going to tell us all of the different positions that we visited before we reached this X position. So let's run through this.
57:46
Let me just zoom out a bit so we can read it. So we have DFS. We're saying we have a visited set keeping track of the positions we visited. We're placing the first position, the starting position inside of our stack. And then we're saying, well the stack, the length is greater than zero. So while we have an element inside of here, we're going to pop that element off of the stack. And then we're going to get the y and x position our coordinate from that element. We're then going to check
58:09
if the element that we're looking at in the array is equal to x. If it is, we found the target that we're looking for. Otherwise we're going to say const string position is equal to get string position because we need to get something that we can add into the set. And then we're going to add this into the set indicating that we have now visited. Then we're going to say const neighbors is equal to get neighbors. So we're going to get all of the neighbors
58:31
of the current position that are valid for us to visit. We're going to go in here. We're going to make sure that we haven't already visited them. If we haven't, then we push them on to the stack so they will be visited next. Okay, so now let's print out the visited set.
58:50
Okay. And what we'll do is we'll look through all the positions in the visited set and we'll place them inside of the maze. Okay. So to do this we're going to say const visited is equal to DFS
59:07
of the maze okay. And really this won't be visited. We'll just call this path. We'll console.log the path. And then we're going to iterate through the path. And we are going to add all of those different positions. So we're going to say four. And then this will be const. We'll call this position of the path.
59:32
We are now going to say const y x. And actually we can't do that because this visited path is going to be containing strings. So we'll actually need to pass that string. So what we can do actually yes we can do this. We can say const y x is equal to and then path dot split at a semicolon now or not. Semicolon. Sorry just comma. The reason this is going to work is because remember we're adding these string positions into our set. So now once we get them we need to parse them.
1:00:04
So we need to get the y and the x out of the string, which we can do by splitting at the comma. So we're going to split up the comma here. And then we're going to say array. And actually this is not array. This is maze at y x y comma x is equal to. And then this will simply be what do we want to go with. We'll just go with an X. So it kind of indicates the path. Then we can say
1:00:31
console.log the maze. Now I don't know if it's going to print it out in a way that's going to be easy for us to see, but let's run this. First of all, we'll see if I have any mistakes, which is possible. And it says array is not defined okay. So let's fix that. So gets neighbors error. And am I writing a rain here? Am I just writing error. Error okay. Get neighbors error. Because this is called array okay. So let's fix that. And now let's give this a shot again and see if it works.
1:01:03
And it says what is the issue here. Cannot read properties of undefined reading comma okay. So actually let's go up here to get neighbors. Looks like I made a mistake. All right. So I just went through and kind of debugged this a little bit and actually found where we have a few problems here. So first of all you can see that I'm saying stacked up push and then string neighbor I don't want to be pushing the string neighbor
1:01:25
I want to be pushing the normal neighbor, which is this array of elements. So that's going to fix that problem that we were just running into there. I'm not sure if you saw, but we had this issue where it was saying, well, it's not showing it now in my terminal, but either way, it was telling me there was an issue with this function. The reason for that was because actually of this bug right here. Now, I also realized why I was looking at this.
1:01:45
I'm saying const parse of path, but I'm not splitting the pause, I'm splitting the path. So I need to split the position. Apologize for the mistakes here, but it is quite a long algorithm so you know it's going to happen. So now let's run this and let's see if we get this. And it looks like this is correct okay. So first of all we printed out the path where we looked through quite a few different elements. Now this isn't every single element, but it's 46.
1:02:10
Of the different ones that we had in our ten by ten maze. All right. So now if we go through here and have a look, you can see that's printing X in all of the positions that we looked at. Now it's a little bit difficult to read. So let me see if I can find a better way to print out this maze for us. I'll just write some code for that so we can actually kind of get an illustration of how we traversed through this. All right. So I've just written a function here to kind of pretty print this maze.
1:02:35
And you can see that now we get a list of all of the different positions that we searched through. Now we could get the order, but I'm not going to do that right now anyways. You can see that we've skipped a fair amount of positions here. I didn't actually look through those because of how the depth first search works. Now, the way we've set up our depth first search is that if we go to our neighbors here, which is actually an important part of this, this algorithm, you can see that
1:02:58
we look at left, right, top and then bottom. But then when we come to the stack here and we're pushing elements, we go through all of our neighbors, which means we're pushing left, right, top, bottom, which means we pop off of the stack, the bottom first, then the top, then the right, then the left. So the order we actually look in is the reverse of what we put right here. So that means that if we want to go in kind of a different route, like we want to search the maze
1:03:25
in a different way, we can rearrange this and look in a different direction. So maybe I want to look left first, then right, then top, then bottom. Well we can do that. So if I go here
1:03:38
we can put these there. And now we're going to look in right left bottom top okay. This order we're going to search and so now if I clear this and I rerun you're going to see that we get a different path because of the order we went in the depth first search. And what we do with the depth first search is we exhaust every single direction as far as we possibly can before we move to the next direction. So what happens here is I started this position
1:04:01
and then I go in this order right, left, bottom, top. And I go as far as I can in those directions. So from here I can't go right. So I end up having to go down from here though I just go right, right, right, right. And then I have to go down. I have to go down again, and then I go to the right. Now, since I go to the right now, I need to exhaust this entire kind of right chain, which is what I do before I come back and go to the left. Then I go down.
1:04:23
I go as far right as I can, which now leads me here. Then I have to come back and then go down and then go left, down, right, up, right, and then all the way over here to this x. Now we can even switch this a little bit. And if I make it so now I go left before I go right.
1:04:40
You'll see here that when we run this we get again a different path. We've now skipped all of this because we went directly left. So the point of me kind of showing you this algorithm here is that with the depth first search, we're going to exhaust one path as far as we can possibly go before we move to a different path. So we didn't end up looking at any of these. We kind of went as quickly as we could into one direction. Now, that doesn't mean
1:05:05
that this is going to be the fastest way to traverse the maze. It's just how it's traversing. That's kind of the method that we're using now. If we want to change this to breadth first search, we can actually do that quite easily. So we can change this to BFS. And then rather than stack we can use a Q. And now we'll just replace all of our stack calls with a Q call okay. So we're going to say q dot. And rather than pop here we're actually going to say q dot shift okay.
1:05:32
So what we're going to do is we're going to push. So we're going to insert from the end. So we're going to change this to be queued up push. And then we're going to pop from the front. That's the only change we need to make. And now this actually works with breadth first search rather than depth first search because we're now using a Q rather than using a stack. So now if I clear this and I run oh it's a DFS. Not fine. We need to change this to BFS.
1:05:56
Okay. You see that we're going to traverse the maze in a different way. So now we actually end up hitting a lot more of the different entries here because we're doing breadth first search. And we're exhausting from every single position as far as we can possibly go. Now, I just realized that we're never actually going to hit these three positions because we have walls there, but you can see with the breadth first search, we essentially exhausted
1:06:16
every single position inside of the maze, which is fine. That's one way to go about finding an element. So depth first search is almost kind of like a snake where it's going as quickly as it possibly can, whereas breadth first search is expanding outwards node by node and exhausting every single neighbor before it eventually gets down here. So from this neighbor, we're looking at every neighbor, then the other neighbor, then the other neighbor, whereas depth first search is doing the opposite.
1:06:42
So I just wanted to quickly kind of show you the implementation here in code for a maze traversal. I know it's not the most simple thing in the world, but I did feel that it was kind of important to illustrate that to you. Now, quickly talking about the time complexity here of these operations. Well, the time complexity of BFS in this instance is going to be the big O of W
1:07:04
times H, where w is the width of our array and h is the height of the array. And that's going to be the same thing for DFS. Okay. That's because we have this visited set. And this visited set allows us to very quickly determine in constant time if an element exists or not, meaning we don't have to traverse it multiple times. Now, I will note that with breadth first search, since we're using the queue and we've implemented that with an array,
1:07:32
that means that this shift operation here actually takes big O of n time, where n is the amount of elements inside of our queue. Okay? And n can become quite large, right? It can be up to the size of the width times height of our, what do you call this here array? Which means that the time complexity, if we use an array implementation of the queue actually worsens to w times h to the exponent two. Okay. Because we can have that many elements inside,
1:08:00
meaning every single shift operation can take us that amount of time. So we're doing that multiplied by W times h operations. Right. So that ends up giving us the square. Hopefully that makes a little bit of sense. But that's it because we implemented the queue with an array. If we implemented it with a linked list then it would just be w times h because the shift operation where we're essentially popping from the queue would happen in constant time.
1:08:23
So for depth first search, it is still this though, because for the array as a stack, all of our operations happen in constant time. Whereas for breadth first search, when we have the queue as an array, then we have that worst time complexity pop operation or shift, which causes the time complexity to increase. In this video, I'm going to cover six of the most popular sorting algorithms. What we'll do specifically is have a quick high level overview of the algorithm.
1:08:50
I'll then go on to the whiteboard, show you how you can perform the algorithm if you were doing it by hand. And then I will show you the code implementation. Now it's worth noting that you do not need to memorize the implementation for all of these algorithms. The important part here is to understand how they work. If you know how they work, then that means that you can actually go and create the implementation by simply using some basic problem solving skills.
1:09:14
Generally speaking, that's what you should have in your mind while you're learning all of these different algorithms. Don't try to memorize every single line of code that you would use. Just try to understand how the algorithm actually functions. If you can do that, it becomes a lot easier. If you do eventually want to write an implementation for this. With that said, all of these are extremely famous and very popular, meaning you almost never have to implement this yourself.
1:09:37
You can always consult Google. You can go to ChatGPT. You can also find the implementation in many different programing languages already built in. Anyways, let's move on to the next slide. Okay, so sorting algorithms while sorting is a very common problem in computer science and programing, there are various ways to sort and organize data. Each of which has a different time complexity. In this video we'll look at some of the most famous and popular sorting algorithms.
1:10:01
Now there is hundreds of sorting algorithms. All of them work differently. All of them have different advantages and disadvantages. But the main ones I'm showing you here are ones that are commonly taught in kind of a computer science where data structures and algorithms course. Okay, so searching algorithm properties. So first thing to understand is there's two main properties were concerned with when we talked about sorting algorithms. First is if they're stable. Second is if they're in place.
1:10:27
Now a stable sorting algorithm means that elements with the same key value maintain the same relative order as in the original array. So as an example, imagine that we were sorting an array of pairs okay. What I mean by that is that we have arrays inside of the array. And we're trying to sort all of those different arrays so that they're in some ordering. Now maybe we're going to sort these pairs based on the sum of the pairs. So we have a pair that's like 1122334151 etc..
1:10:57
Okay. We have different pairs. We want to sort these pairs and we want to sort them by the sum of the pairs. Now if that's the case, it's possible that many of these pairs will have the same sum. If we were using a stable sorting algorithm, that means the pairs appeared furthest left in the array that had the same sum as another pair would be in the same relative order to those other pairs. It's a little bit difficult to explain without looking at it visually here,
1:11:22
but hopefully you understand what I mean with stable sorting algorithm. I'll try to give you a visual in just a second. Next, we have in place now an in-place sorting algorithm is how most of these work. And that's simply means that you mutate the original array that you are sorting. So rather than creating a new sorted array, you're sorting the array in place and actually mutating the existing one. Okay. Moving on. Let's talk about some inefficient sorting algorithms.
1:11:46
So the simplest sorting algorithms, but also the worst performing algorithms are the following selection sort, insertion sort and bubble sort. All of these run with a big o of n to the exponent two or n squared time complexity. So try to remember these are the inefficient ones and then the efficient ones are merge sort, heap sort and quicksort. They're also the most complicated. And they run in the big O of n times log base two of n. Now remember I was telling you previously that we can assume
1:12:17
that when we're sorting some data that it will run in n log n. The reason for that is typically programing languages are going to implement the quicksort or the merge sort algorithm. And that will allow you to sort data using the built in implementation in language like the JavaScript sort function in n log n time. If you're using a different sorting algorithm, obviously you need to know the time complexity of that. But typically speaking, we assume that when we need to sort
1:12:43
something, that it will run in the time complexity of big O of n log n. All right. Now we're going to start looking at a few different sorting algorithms and their implementations. So first selection sort. So selection sort is one of the inefficient algorithms. And we're going to go in the order in which I showed you. And this is a big O of n to the exponent two or n squared time complexity. Now selection sort is an unstable sorting algorithm.
1:13:05
And the way that selection sort works is we simply repeatedly select the smallest or the largest element from the unsorted portion of an array and swap it with the first element of the unsorted portion. Now, what this means is that we just look at an array, and we continually grab either the largest or the smallest element. We then place that either at the front or the back of the array. And then we have a sorted array.
1:13:30
So let me go over to the whiteboard here and show you how selection sort works. Okay. So in front of me you can see that I have an array. These are different elements. And selection sort is actually fairly intuitive. If we want to sort this array what we can do is just grab either the maximum or minimum values one at a time, kind of move those and place those in some position that we know is sorted and then go from there. So we start and we have none of this array currently sorted.
1:13:57
So the first thing we need to do is grab the maximum element or the minimum element okay. It depends on the order in which we're sorting it. If we're sorting in ascending order. So going from smallest to greatest then we're going to grab the minimum element and put that at the front of the array or the maximum element and put that at the back. You can choose whatever way you want to do this. For now I'll grab the minimum element and I'll put that at the beginning okay. And that will mark
1:14:20
kind of the beginning portion of our array as the sorted portion. So what I need to do is I need to look through every element and find the minimum element. So after going through all the elements I found that the minimum was one. So what I will do is I will take one and I will simply swap that with the element at index zero. So I'm going to put one here. And actually let's do this in white. And then we need to come here. And I think that this was a four. Okay.
1:14:47
So now we say that this portion of the array is sorted. So that means I no longer am going to look through this portion. I'm only going to look through everything to the right of it and then find the minimum element. So I look through and I find two. So now I need to swap two with the element right here because that's where two needs to go. So we swap this. So this becomes two and this becomes six. And now this portion of the array is sorted. So now again
1:15:13
when we're looking for the next minimum element we're only looking to the right. So now we find three. So we swap three and four. And now this is the sorted portion of the array. Now we're looking to the right. Okay. So now we do the same thing. We are going to if I can draw this correctly swap four and six. This becomes the new sorted portion of the array. And then we need to find the minimum again. Well it's in the correct position. So we just mark that there.
1:15:44
And then we only have one element left which must be the largest element. So now we have the array fully sorted. So that is selection sort. Again fairly straightforward. You just select the maximum or minimum element and then put that at the front or the back of the array depending on the order in which you're sorting these elements, you keep track of which positions in the array have already been sorted. So in this case you can see every single iteration. We're kind of tracking that.
1:16:07
Hey, we've already sorted up to here, up to here, up to here. So only look on the right of this array. Then you end up getting this sorted array. Now the reason the time complexity here is big O of n squared is because what we're doing is for every single position in the array, we are searching for the minimum element. So searching for the minimum element takes big O of n time. And then we need to do that. However many elements in the array time there is.
1:16:32
So that gives us n multiplied by n which equals n squared. Now you'll notice that as we progress through this, we have to search through less and less elements because we start by searching through the entire thing. Then the entire thing minus one entire thing minus two up until the end of the array. So we end up getting the sequence that we're familiar with which is n n minus one, n minus two, n minus three, etc. for the number of operations that we need to do.
1:16:58
Now again, if we take the limit of that as that approaches infinity, that gives us n squared. So that's why we can say the time complexity here is Big-O of n squared. Perfect. Let's move on to the next algorithm. Moving on to insertion sort. So this again runs in big O of n squared time complexity. It works well for partially sorted data sets. This is a stable sorting algorithm and the way this works is an array is split into a sorted and unsorted part,
1:17:24
and values from the unsorted part are selected one by one and inserted into the correct position in the sorted part. So let me hop over to the whiteboard here and we'll have a look at how this works. All right. So you can see that we have our array here. Now for insertion sort. We're doing a similar thing to selection sort where we're going to be keeping track of a portion of the array that's already been sorted. Then what we'll do is we'll look at the next element in the array
1:17:50
and insert that in the correct position in the sorted part. So we're not finding the minimum or maximum element each time. We're just looking at the next element that's not yet in the sorted portion and inserting it into the correct portion of the sorted array. So when we start and we have this standard array here, nothing yet is sorted. So we kind of mark our first step as indicating that okay, we're going to say that the first element here is sorted. All right.
1:18:16
The reason why this would be the sorted portion is because whenever you have one element in a subarray, well that's always going to be sorted. Right. Because that's the only element. So we start by indicating that okay, this portion of the array here that I'm in, highlighting in yellow, sorry is sorted. Then we're going to highlight a portion in green. And this portion in green is going to be the index or the element that we want to insert into the sorted portion. Sorry.
1:18:39
So what we do is we look through the sorted portion and we find where this should be inserted. The way we do that is we compared the element directly to the left of us. And we say, are we greater than or less than this element? Now in this case, we are greater than this element. And since we know the rest of this array is sorted, that means that we just leave this position where it is, because we know that now this will be the correct position in the sorted portion of the array.
1:19:07
Don't worry, as I have more than one kind of number here, this will make more sense. So now we say this yellow portion here is sorted. Now we move on to the next element which is one. So we kind of mark this as our current element that we're looking at. All right. So now what we need to do is insert this into the correct position in the sorted array. So what we do is we look to the left and we say are we greater than or less than. Well we are less then.
1:19:30
Which means that one here is not in the correct position. And it needs to move into the correct position of the sorted array. So now we need to do is swap these values. So we're going to put a one here and a six here. And remember this is the element that we're currently looking at. Okay. So now we've swapped trying to insert this in the correct position. But again we need to check if it's in the correct position. So we look to the left and we say are we greater than or less than this element.
1:19:59
Well we are less then. So that means we need to do another swap to put this in the correct position. So let's erase that. We put one here and four here. Now we've inserted what used to be here at the beginning of the sorted array. And now this portion of the array here is fully sorted. So we move on to two. So now add two. Again we do the same thing. We look to the left and we say all right are we in the correct position or are we less than this element.
1:20:28
Well we are less than which means we need to swap this. So two comes here and six comes here. Same process repeats. We look to the left. Is it less than or greater then? It's less then. Which means we need to swap it so it's in the correct position. So this becomes two and this becomes four. Now we look to the left. We say we less than or greater than. We're greater than which means this is in the correct position. So no more swaps need to be done.
1:20:53
And that means that we have now sorted four elements in this array. So now all of this portion is sorted. So now we come to three three. We repeat the process. We look to the left. Is it less than or greater than. Well it is less than. Meaning we need to swap. So we do the swap here and we put oops. I keep rewriting it in the wrong order. Three and six. Then we look to the left. We see we're less than, so we need to swap again. Okay so four comes here and three comes here. Look to the left.
1:21:23
We see that we are greater than two, meaning we're now in the correct position. And then we know that this portion of the array is now sorted. So now we only have one element left. So we need to do the same thing. We need to look and see if this in the correct position. Now fortunately for us it is in the correct position. But keep in mind we could have an element like negative one here. And if that was the case, we then need to perform swaps
1:21:45
with every single element to put this in the correct position. Now in our case it's nine. So we simply say yes, this is in the correct position. And then we mark that this entire array has been sorted. There you go. That is selection sort. Now how long does it take. Well this runs in Big-O of n squared time complexity. The reason for that is the exact same reason for selection sort, where we need to do a maximum of n swaps n times. So we're looking through the entire array, right?
1:22:16
We look at every single position and for every single position, we potentially need to swap this with every position that was currently sorted before it. So what happens is kind of in the reverse order of selection sort is we begin where we have a sorted array that contains only one element. So when we only have one element, that means the maximum number of swaps we need to do when we insert the next element is simply one, then we have two elements. Meaning.
1:22:41
Once we grab the next element, the maximum number of swaps is two, then three, then four, then so on until n minus one and then n. Now this sequence is the exact same sequence that we saw before, and we know that as n approaches infinity, that this approach is the big O of n squared time. That means this algorithm takes Big-O of n squared time to run. However, if our array is already partially sorted and there's only 1 or 2 elements that aren't sorted,
1:23:09
this can actually be a very fast algorithm to run. Because imagine the situation where all we had was something like this, where we know that most of the array is sorted, but we maybe have 1 or 2 elements that aren't sorted. Now all of a sudden this becomes very, very fast because all I have to do is swap this position two times. Everything else in the array will just be perfectly fine because it's sorted. So when I go to insert this and I look at the sorted portion, well,
1:23:33
we won't have to do anything. Same with this. Same with this. So you get the idea. Okay. So that's why this can be good when you have partially sorted data. All right. That is insertion sort. Let's move on to the next one which is bubble sort. All right. So bubble sort again a big o of n squared time complexity algorithm. This is a stable sorting algorithm as well. And this works by repeatedly swapping adjacent elements if they are in the wrong order.
1:23:58
Now the way that I like to think of bubble sort is that we are bubbling either the largest or the smallest value to the back or front of the array. Now this is a very famous algorithm. Let's head over to the whiteboard here and have a look at how we implement this. Okay so bubble sort. Again the way to think of this is you're taking whatever the largest values are and you're bubbling them to the right, or you're taking the smallest values and bubbling them to the left.
1:24:23
In our case we're going to bubble over to the right side. But you can bubble in any direction that you want. Now, the way this works is that we're going to start on the first position here, and we're going to essentially look at every single adjacent element and swap this until we're in the correct position. Okay. So let me just go through the example and you'll see how this works. So we start at this element okay. We now look to the right.
1:24:48
And we say are we greater than or less than this element. Well we are less than which means this currently is in the correct position. Not really, but it's correct relative to this element. Meaning that it wouldn't be correct for me to swap six with four because six is greater than four. Remember, what we're attempting to do with every iteration is bubble the largest or smallest value to the back or front of the array? And it's we're doing this differently sort than in selection sort.
1:25:15
So when I take four right I have my kind of pointer out four here I compare it to six. And we see that four is not greater than six. So all I do here is I move my pointer forward. And now I'm going to compare six with the next adjacent element which is one. Now in this case we see that these values do actually need to swap because six is greater than one. And we want to bubble this to the right side. So we swap these values.
1:25:38
And then we keep moving on to the next set or the next pair of elements. So move this over here. And now we're looking at six and two. Now same thing six is greater than two. So we need to swap. So we put two here and six here. Move our pointer and then keep going. So notice we're essentially looking at two elements in the array every single time I know I kind of butchered drawing this here. But we're constantly comparing elements and bubbling it to the right or to the left side.
1:26:06
Okay. So now we're looking at six and three. Six is greater than three. We need to do a swap. So we take three. We put six. We move our pointer. Now we compare 6 to 9. We see that nine is greater than six. So we're all good and we move our pointer. And now that our pointers at the end of the array, that means that we would have found the largest value and bubbled this to the last element in the array. So we're now done with this first iteration of bubble sort,
1:26:36
which means we now mark the last element here as sorted, meaning we already found the maximum element that exists in this portion of the array. Now we repeat the process again from the very beginning. So we look at one or we look at four. Sorry is a greater than one. So let's add our two pointers. Here it is. So we do swap. So one. And for now move the pointer over. Take four. Compare it to two. Is it greater than. Yes it is. So we do our swap two and four.
1:27:08
Okay. Look at four is a greater than three. Well yes it is. So we need to do our swap.
1:27:14
Okay. You can see this gets fairly repetitive. Now we have four. Move our pointer over. Now we take four. We compare it to six. Is four greater than six. No it's not. So there's no swap that needs to be done. Now we take our pointer. We move it here. And since this pointer now exists on the portion of the array that's been sorted, we say okay we're done. With this iteration, we now would have bubbled the second largest element to the front or sorry to the back of the array.
1:27:39
So now this portion of the array is sorted with the two largest elements. Then we would continue this process. So we would go to one right. We would compare it to two. We'd see no swap needs to be done. We go to two. We'd compared to three. We'd see no swap needs to be done. We'd go to three compared to four. See, no swap needs to be done. Four move our pointer over here. This now means that we're done right. So now we mark that four is the next largest element. We've now bubbled that up.
1:28:07
Now notice here that for the rest of the array there's actually no more swaps that we need to do. But we still need to do these iterations and check if any will occur. Because we don't know that there's no swaps. So we can see this visually because we're just looking at the array. But in the actual implementation of the algorithm, you're not going to know that there's no more swaps to be done, meaning you have to continually go through those iterations
1:28:28
and keep doing all of these comparisons, even though no swap occurs. So eventually we'll get to a point where we've done all of the iterations and the entire array is sorted using bubble sort. Again, the way to think of bubble sort is constantly bubbling. The smallest or largest value to the end or the beginning of the array. By continually comparing adjacent elements with each other and swapping them until you get into the sorted portion of the array.
1:28:52
Now this algorithm again runs in big O of n squared time. The reason this takes n squared time is because for every single element that we need to move to the end or the beginning of the array, that takes n time. So we need to find the n largest elements. To do that that requires n sets of swap or at least checking for swap operations. Right. So you saw in that first iteration alone we did N iterations. Right? Then we did n minus one, then n minus two, then n minus three all the way
1:29:23
until we got to one, and then zero, which is that same sequence we've seen leading us again to big O of n squared time. All right. Let's move on now to some more efficient searching sorting out, searching, sorting algorithms. So now we move on to merge sort. Now merge sort is the first efficient algorithm we're looking at that runs in Big-O of n times log base two of n time. Now this is a stable sorting algorithm and it works by dividing an array
1:29:51
into two halves, sorting each half, and then merging those halves together. Now this is a recursive sorting algorithm, which means we can implement it using recursion. So rather than me dragging on the explanation, let's just go to the whiteboard here and have a look at how this works. All right, so I'm on the whiteboard here. Now, the way the merge sort works is similar to how we do a binary search. We actually split the array into two subarrays. Okay.
1:30:16
So we have two subarrays here that contain approximately half of the elements. We then sort the two subarrays and then merge the sorted subarrays together. That's the basic premise here. Obviously gets a little bit more complicated than that, but the basic idea is that if I have two sorted arrays, then I know how to merge those sorted arrays together. So all I have to do is get to a point where I have two sorted subarrays, and then I can merge them. So the way that you actually kind
1:30:44
of derive this algorithm, or you would come up with this, if you don't know this is you'd say the following. All right. Let me start by determining what happens if I have two sorted subarrays. So in this case let's just sort these two subarrays manually okay. So we have one four and six. And then we have two three and nine okay. So it looks like that's actually sorted for us. That's nice. All right. So if we have these two sorted subarrays how do I merge them into one larger fully sorted array.
1:31:13
Well let's create two pointers here a pointer at both the starting indices of this array. Then we'll have a new array. This array will have six elements inside of it that we will insert elements into as we traverse these two arrays. So essentially what we need to do is look through both of these arrays, but look through them kind of one element at a time and compare the current elements that we're looking at. I know it seems a bit strange. It is a bit difficult to draw this out.
1:31:39
I would need a little bit more space, but the idea is we start at the first index of both of these arrays. We then look at the two elements that I have. These kind of pointers on, and we compare them together and we say okay, what element is smaller. Well in this case element one is smaller. So since element one is smaller than element two and we know that both of these arrays are fully sorted, we know that one must be the smallest element that we can possibly insert.
1:32:05
Again, the reason for that is since we know the right side is sorted, if we're comparing to the first element on the right side and the element on the left side is smaller, then this must be the smallest element. So we simply take one and we insert it in our new array. We then move this pointer forward one index. Because we've now kind of crossed this off that we've inserted that into the array. All right. Now we do the exact same thing.
1:32:27
And we continue this until we're finished looping through both of these arrays. So we now have four which is the next largest element on the left side. And we compare that to two which is the current largest element we haven't yet inserted from the right side. We see the two is larger so we insert two. We cross that off here and then we move the pointer on the right side array. Okay. Again we're just repeating this process by continually moving one of these two pointers forward.
1:32:52
As we insert the element from these subarrays. So now we compare 4 to 3. We see three is larger. So three gets inserted. We move this pointer forward. Now we repeat the process. We compare 4 to 9. Well four is less than nine. So we insert four and we move the pointer forward now six and nine. So we put six. This pointer is now outside of the array. That means the only element left to insert is this element right here. So we put nine. And now we have a sorted array that we got
1:33:24
from merging two sorted subarrays together. So now that we understand this practice here with merge sort, all we need to do is find a way to sort these subarrays. And that's where the recursion is going to come in. So again the recursive case is that we sort the left and the right side. And then once they're sorted we merge them together. Now the base case for our recursion is when no more sorts need to happen. Now we don't need to sort when we have a subarray that only contains one element.
1:33:55
So let me go back to a clear screen here, and we'll kind of walk through the merge sort tree and you'll see how this algorithm functions. All right so we're back at our fresh array here. Again remember that what we do as our very first step is we split the array in half. Now we only split the array in half if it has more than one element. Because obviously we only have one element then we can't split that in half. And again kind of teasing at it here, the base case of our recursion
1:34:20
is going to be when we have a subarray that only contains one element. Because to do that or to sort of subarray that only contains one element, we don't have to do anything. It's already sorted. Right. So we take these and now we have two subarrays. So let's kind of draw them out here. We have four six and then one. And then let me give myself a bit more space. We have two three and nine. Okay. So we have these two subarrays that we get from splitting this.
1:34:46
Now what we need to do is we need to continue to split these subarrays. Right. We're going to do this recursively. So if I want to sort this I'll use the same process that I used here. I'll say okay well to sort this I need to split this into two subarrays sort the subarrays, then merge them together. So that means I now get a subarray that contains four and six, and a subarray that contains one, which is coming off of here. Then we continue on this side.
1:35:10
We get a subarray with two and three okay. And then we get a subarray that contains nine. Excuse the messy handwriting. All right. Now we need to continue splitting these. So we see that this is already sorted. So there's nothing more we need to do there. But before we can merge these two together to create a sorted array out of this, we need to first split this up. So when we split these arrays we get two sub arrays right. We get four and we get six. Then we get here two
1:35:42
and we get three like that. So now at this point we've reached the base case of our recursion where we have subarrays that only contain one element. Now what we need to do is merge those subarrays together to create the sorted array. All right. Now I've ran a little bit out of space here. So what I'm going to do is just kind of scroll the screen up and we'll kind of go from here. Excuse me. It's going to look a little bit messed up. Okay.
1:36:05
But what I need to do is I need to merge these subarrays together. So what I do now to merge two subarrays I only have one element is I simply compare the elements and then put them in the correct order. Now, fortunately for me, that means that all I need to do here is just put a new array that contains four and six. Now if these were swapped, then I would have to kind of swap the order right where four would go here, six would go here. Hopefully this making a bit of sense,
1:36:30
but I'm now merging these two subarrays together. Okay, so now that these are merged together, I now need to merge this with this right here. So now I'm taking this subarray that's sorted. And this is a sorted subarray. I know it's a little bit difficult to visualize, but essentially I take that and one and I now merge them. Now when I merge them I get one four and six which is my sorted subarray. Okay. So now if we scroll all the way back up here, I know it's a little bit difficult to see.
1:36:59
We now have sorted this left side because all of the different subarrays that we have are now fully sorted and merged together. So kind of the return value up to this side from this recursive tree on the left would be this 146. Okay. I'm going to keep going downwards, but you'll get the idea. All right. So we have 146. Now we need to do the same thing on our right side. So on our right side we merge two and three. So we get two and three and a subarray.
1:37:26
And then we come and we merge it with nine. So let's just merge it over here. So we have a bit more space. So we merge this we get two, three and nine in a sorted subarray meaning that now what's going to be the return value up here will be two, three and nine. So now we're at the point where we have two sorted subarrays we've sorted the left and we've sorted the right. Now we need to merge these together to create the fully sorted array.
1:37:48
Again, this is such a mess I really apologize, I didn't realize it was going to run out of space this quickly. Well, what ends up happening is we now take these two and merge them together, and when we merge them together, we do that process I showed you about before. And we get one, two, three, four, six and nine in our fully sorted array. Okay. So what happens is we start by splitting it up. We then continue to split it up until we reach our base cases where we only have one element.
1:38:14
We then take those elements, merge them into a sorted array, and then we continue merging every side that we've branched off in into a sorted array. So we get another sorted array here. And eventually, once we get to the point where we now have the sorted left and right side of the original array, we merge those arrays together and that gives us the fully finished and sorted array. Okay, probably the messiest example you've seen so far, but that is how this works. All right. That is merge sort.
1:38:43
Let's move on to the next algorithm. So moving on we have heap sort. Now heap sort is efficient as well. And this runs in n log base two of n time. This is an unstable sorting algorithm. And it inserts all the array elements into a min or max heap. Then extracts the root elements one by one and places them into a new array. Now, I already talked about how we do heap sort when we were looking at the heap data structure video, but I'll quickly recap it here by going to the whiteboard.
1:39:10
Okay, so when we have an array like this and we know we have a heap data structure, we can simply use the heap data structure and insert every single element from our array into that heap okay. So if we insert into the heap, I don't really want to draw all of this out yet, but okay. We'll start with four. Then we want to insert six. Now, since six is greater than four and we're going to implement a max heap, that means that six needs to become the root node.
1:39:35
So six will come here four can come here. Okay. Then we need to insert one. So it's fine for one to go here. Then we need to insert two. Well two needs to go beneath. And elements or two can come here. All right then we need to insert three. Three is actually fine to go here. All right. Now we need to insert nine. So nine would come here. We then need to swap with one and six. So what happens is one comes here nine comes here
1:40:00
nine swaps with six which now means six comes here and nine comes here. And now we've created a max heap out of all of these elements. Now that we have the max heap, first of all, to create the max heap took us n log and time. The reason it took us n log n time is because for every single element we have in our array, which is n, we need to insert into the heap which we know takes log base two of n time. So multiply those together, because that's the operation
1:40:28
you're doing at every step and you get n log n. So we created the heap in n log n. Now we need to remove or extract elements from the heap and place those into a new array. So we start by extracting nine. When I extract nine I put that there. Then I need to get the next root element which will be six. Now I don't want to go through the whole heap process again because we've already looked at this in previous videos. What happens is
1:40:50
we just keep extracting the maximum key from the heap every time we extract. That's a log base two of n time complexity operation, which means again to create this new array, now we get another n log. If we can write log correctly here log base two of n time complexity operation. Now the thing is to create the heap took n log n time okay. And then to remove all the elements from the heap and place that into a new array that takes and log n time. However we add them.
1:41:21
So we get two n log n base two of n time, which means we simply remove the two and we get the time complexity of n log base two of n. So that's essentially the process. Again, I won't go through the whole kind of heap creation insertion deletion because we've already looked at that in previous videos. But that's what we're doing. We create a heap which we know takes n log n time with all the elements are right. Then we extract the maximum element or the minimum element from that heap,
1:41:45
and then we insert those elements into a new array, either in ascending or descending order, depending on the kind of way that we want to sort the array. Okay. So all of these sorting algorithms work both forwards and backwards, meaning you can sort ascending or descending. All you have to do is change the comparison that you're doing. And if you're inserting at the back or the front, depending on how you want to sort it. All right. That is heap sort. Now let's move on to quicksort. All right.
1:42:08
So quicksort this runs in n log base two of n time. It is an unstable sorting algorithm. It is definitely the most complicated algorithm on this list yet typically it's the fastest. And the most preferred. Most programing languages actually use quicksort as the default implementation of a sorting algorithm, so take that for what you will. Now I'm not actually going to dive into all the implementation details of quicksort because it is fairly complicated.
1:42:33
It's not something that you're going to be expected to implement on your own. And I just don't think it's super valuable for me to spend the time here explaining it and potentially confuse you quite a bit because it is, again, fairly complicated. I know it's one that I struggled with a lot when I was in my computer science degree, and since then I've never had to use it, learn it, etc. so I don't know if it's worth the hassle.
1:42:53
Regardless, to give you a super, super quick kind of preview of what it does, the quicksort algorithm selects a pivot element. Then what it does is it attempts to place all of the smaller elements in the array to the left side of that pivot, and all of the larger elements in the array to the right side of the pivot. Now that seems trivial, right? It seems. Oh, that's easy. I can take all the smaller ones puts left, all the greater ones puts them right.
1:43:15
However, the way in which it performs these swaps is a bit more complicated, and it does this recursively such that it's not running in big O of n squared time. It runs in big O of n log base two of n time. Now, similar to merge sort, what it does is continually split up the array based on the pivoting elements, and then keeps adding these new pivots and swapping elements to the left and right side of the pivot until it's recursively done. All of these swaps and the entire array is sorted.
1:43:42
I know, sounds a bit complicated, hence why we're not going to dive into it and you don't really need to worry about. Okay, so let's just quickly go to a summary here. And this is just for you in case you want to see all of the different time complexities. And if they're stable or not. Obviously all this information is on the previous slides as well. But selection sort time complexity big O of n squared is stable. No insertion sort and squared stable. Yes. Bubble sort and squared.
1:44:07
Is it stable? Yes it is. Merge sort n log base two of n is stable. Yes. Heap sort. Is it stable. No. Because we're using that heap structure and it runs in n log base two of n quicksort. Is it stable. No runs an n log base two of n. So I just put that there. So you guys had one slide that had all of the algorithms. So you can see the time complexity of each. Now I was going to dive into the code, but I realized this video is already extremely long. And it's not again crazy valuable for me
1:44:35
to walk through all of the steps in the code now that you already understand the algorithms. So what I'll do is I'll attach the code as files to this lesson, and if you're interested, you can walk through them. Now, full disclosure the code that you're going to download was not written by me. I actually got it from the internet, but all of the sources for where I found that code is available at the top of the code file, and you can go to those links if you want to see some more information
1:44:57
and see the person who originally wrote that. Again, with these types of algorithms, you don't typically need to implement these yourself. Yes, it can be good practice to write them, but it's not something that you're going to be expected to write on a job like no, no, boss, an employee is going to tell you, hey, implement bubble sort. And by the way, you can't use Google, right? So I don't think it's crazy valuable for me to go through and explain to you
1:45:18
line by line how all of these algorithms work, when you can just reference the code yourself. If you want, you can attempt to write it on your own, and that's something that you can kind of do at your own discretion. For something like the final exam of this course, I will not be asking you to implement these algorithms. I may simply ask you to look at them or identify which algorithm is which by seeing the code. Right. So hey, this is the code.
1:45:40
Is this insertion sort bubble sort or selection sort. And just by knowing how these algorithms work and being able to read code, you're able to do that without having ever seen that code before. All right. So what is Dijkstra's algorithm? Well, first of all, this is an extremely famous pathfinding algorithm that allows you to locate the smallest distance and path from any starting vertex to every other vertex in the graph. So, for example, we may start at a and after we run Dijkstra's algorithm,
1:46:08
we'll know the shortest distance as well as the shortest path to every vertex inside of this graph. Now for this graph. It's fairly trivial because it's a small one, but you can imagine in a very large graph, even us as humans, when we get 20, 30, 40, 50 nodes deep, we actually can't do that visually. Or if we can do it visually, it takes us a very long time. So having computer systems that can do things like determine the shortest possible path in a graph is actually very powerful.
1:46:35
And this is used in literally millions of different programs. I mean, think of a GPS that's a pathfinding algorithm, probably a bit more advanced than what we're doing here, but something where we need to be able to very quickly calculate the shortest possible distance between any two points in that graph or in that situation, something like a road system. Regardless, let's have a look at Dijkstra's algorithm and see how this works. So for Dijkstra's algorithm we need to set up a few things.
1:47:00
Right now they're going to seem very abstract as we go through the video to make more sense. So we begin by getting our graph. Now we're usually going to represent our graph as an adjacency matrix, which we talked about previously. We can also use an adjacency list. Anyways we have our graph on the left hand side of the screen. We then set up this table. Now in reality this will be implemented using a data structure like a heap. But for now we just kind of write it as a table
1:47:24
for this to be visually, you know, accessible to us. Now in the table we have three columns. The first column is our vertex column. The second one is our distance column. And the last one is the previous node that we visited the node from. So what this table is going to store is the current shortest distance that we have to find or get to any one of these nodes. And the node that we went from to get to that node. That's what the table will hold for us as we run the algorithm.
1:47:53
Then we have this visited set. Now what this visited set will hold is all of the nodes that we've currently visited. Now the reason we need to have this visited set is because for Dijkstra's algorithm, we typically run this on an undirected weighted graph. That means that I need to keep track of the nodes that I've currently reached, because if I don't do that, I will continually keep traversing across this undirected edge here and get into kind of an infinite loop.
1:48:19
As we've seen in some of the other algorithms, when I was talking to you about graphs, regardless, that's the set up, okay. So we have a visited set. This tells us which nodes we've currently kind of visited and ran our algorithm on. And then we have this table which is keeping track of the shortest possible distance. Now for the initialization of Dijkstra's algorithm we begin by picking a start vertex. In this case I'll pick a. That means that I now need to go inside of my distance table here,
1:48:45
and I need to update the value for a to B equal to zero. That's because the distance to get to the start node is simply zero. Seems trivial, but this will become important in a second. Then we want to set the distances for every other node that we have inside of our graph to be infinity. That's because we currently don't know what the distance is. So we're going to make this extremely large so that as we go through here,
1:49:10
we update this value with any shorter distance that we find to reach that node. So for our algorithm we begin at the start vertex from the start vertex. We visit or at least look at all of the adjacent or neighboring nodes, ones that are connected to this node with an edge. So we see that we have B and we have c, so we'll go in some order. We can go to B first. And we see that we have an edge to B that has a weight of one. That means from A we can reach node B and that costs us a distance of one
1:49:39
or a weight of one. So what we need to do since we've seen this edge here is we need to go to our table and we need to update the distance to B to be one. The reason for that is we found a distance that's less than infinity. So we update this now to say okay well the shortest possible distance we found so far to reach B is one. And then we set the previous node for b to be equal to a because we reached b from the edge that was connected to a. All right. Next we go to C.
1:50:08
Now by the way we're only going to look at these adjacent neighbors if they're not in this visited set. In this case they're not. Hence why we're looking at them. All right. So from a we can see that we reached C with a distance of six. So same thing. We look at the distance in the table. We see this distance is greater than six which means we found a smaller distance. So we update that distance. Let me just write my six a little bit better here inside of the table. And then same thing.
1:50:33
We mark the previous node to get to see as six. Great. So now we have no more neighbors from a. So what we do is we insert a into the visited set and we kind of mark that, okay, we're done with a we've already kind of traversed through its neighbors. Now what we do is we find the node in our table that currently has the shortest possible distance to it that we've not yet visited. In this case, that node's going to be B, so we take out B. We kind of extract B from this table here.
1:51:07
And we now go to B and we start looking at its unvisited neighbors. So from B we have three neighbors. We have a C and D. However we're only going to look at neighbors that we haven't yet visited. Notice that we've already visited a. So I don't need to go back to A because if I were to do that, then what would happen is I would try to update A to B equal to one. For example, if I hadn't set this to zero. Right? So there's no point in me going back across an edge that I've already looked
1:51:34
at. If I've already looked at that edge, I don't want to visit it again, which is kind of how this visited set is working. So A is done. I don't need to look at that from B though. I need to look at C and I need to look at D because we haven't yet visited them. So I first start by going to D or sorry by going to see. When I go to C, I see that I have a distance now of whatever the distance was to reach B plus the distance to reach C, so from A
1:52:00
to B was a distance of one from B to C was a distance of two. So my total distance to reach the node C from node A, which is what I'm trying to calculate here is three. So I look at three, and I compare that to the current distance that I have to reach C. And I see that it's smaller than that distance. So what I do now is I update my table. So I go to C and I set this to be equal to three. And then I set the previous node to be b okay.
1:52:29
So when I update the distances I'm adding whatever the distance is to the current node plus the edge weight to the new node. And then I'm using that as the shortest distance. So now we visited C. Now we need to visit D. So when I go to D same thing here I have a distance of one to reach B a distance of one to get to D, which means my total distance to reach d from a is two. So I go and I see if that's less than the current distance in the table it is.
1:52:54
So I update that and then I set then the previous node. Sorry for this node to be b. All right. So now I'm at the point where I have visited all of the neighbors of B. So what I do is add it to the set. Okay. So now I've visited both A and B. Next I need to visit the node that has the shortest possible distance that I haven't yet visited from this table. Already done and already done B so the next distance or the next node. Sorry, that has the shortest distance to it is D.
1:53:27
So I now pull out D and I start going through that. So now we're on D from D I'm going to visit all of its unvisited neighbors. So we see that it has a neighbor to see E and B. Now we've already visited B so we don't need to look at that. So we can just go directly to C. Now the distance to get to D is two. So that means the distance to get to see from D becomes four. So now I see this distance of four. So I go and I look at C in my table and I see okay is four less than three. It's not.
1:54:00
Which means this is not a shorter path to reach C. So I don't do any update. Now I need to look at the next neighbor which is E. Now to get to E, I have two plus five which is seven. So the distance reach D plus the distance to get to E from D, so that's seven. So now I go and look at E in my table and I see that it's infinity. So that means I can update this now to be seven. And then I set the previous node to be equal to D okay.
1:54:28
So now I've exhausted the neighbors from D. So what I do is I add D to the visited set and I continue my algorithm. Now what I need to do again is grab whatever node from this table has the shortest possible distance that I haven't yet visited. I've already looked at A, already looked at B, already looked at D, the next node to look at is C, so we go to C, we kind of pull this out here
1:54:52
from C. We need to exhaust all of its neighbors that we haven't yet visited. Now we've already visited A, B and D. Now notice if we were to visit them we'd be going across edges that we've already looked at, so there's no point in doing that. Hence why we have that visited set. So from C the only neighbor I need to visit is E. Now the distance to get to C is three. So I take three, I add five and that gives me eight. So now I update the distance.
1:55:19
If it's smaller than the current distance to get to E. Now we can see when I look at E that the current distance to get there is seven. Well this is not smaller, so there's no update that needs to be made. So what we do is we now finish with C, we add that to the set and we repeat our process. So now we go to E. E is the only node that we haven't yet visited. And it is also the smallest node well that we haven't yet visited. I mean really it's just the node that we haven't visited yet.
1:55:46
So we pull it out and now we look at E from E! We visit all of the neighbors that we haven't yet visited. Now, in this case, we've already visited both the neighbors, so we simply add E into the visited set. And then that concludes our algorithm. Now we have determined the shortest possible distance from one node to every other node in the graph, and we know the path to reach those notes. So now at this point, since the algorithm is finished, if we want to find the path.
1:56:12
So the nodes that we need to take to reach any other node, we can do that quite easily by using this previous, kind of labeling. Okay. The way to do that is pick the node that you want to find the shortest path to. In this case, maybe we want to find the shortest path to E. So from E I know that I'm going to be kind of reaching that from a right. So I start on E and I look at the previous node. Now I'll just kind of write this here. So we start on node and we see the previous node is D.
1:56:39
So we mark d there. Now how do we get to d. Well if we go look at D we see that we reach that from B. So now we put B and then we go to B and we see that we reached B from a. So now we mark a. So now we know the path is e d ba or a b d e whatever order you want to read it in. So I go from E to D from D to be
1:57:03
and from B to A or the reverse order again however you want to read it. We see that has a distance of seven, and that is the shortest possible distance for me to get to E. I could try some other ways, but we would see that those would be a larger distance. There you go. That's how you perform them. Now let's do one more example. Let's say we want to get to see well, if we want to get to see. Same thing I kind of right see here I go and look where I came from.
1:57:29
Well I came from B so I write b I see where B came from, B came from a. All right we're there. So now if we want to get to see we go from A to B and then to C not directly from A to C. So that is Dijkstra's algorithm. And that is how you find the shortest possible distance from any node in the graph to every other node. Now let me just clean up the screen a little bit here, and let's leave some space to discuss some more implementation details. All right. So I've just clean this up a bit
1:57:57
and I want to go through a quick recap of exactly what we're doing so we can derive the time complexity and talk about kind of the implementation details here. So recall that what we're doing is we're visiting every single vertex that we have inside of our graph. And for every one of those vertices we are updating all of the neighbors shortest possible distances okay. So we first need to extract whatever node or whatever vertex currently has the smallest distance. And we're doing that v times.
1:58:26
We're doing that v times because we need to do that for every single node that we have. We don't know in what order we're doing it. We just know that it's going to happen v times where V is the number of vertices. Now, for every single vertice we then need to look at all of the edges connected to it, and potentially update every single value or every single node that's connected with that edge. So first of all, what we need to understand here is that what we need to continually do is extract
1:58:51
the minimum possible value from some data structure. Now, what is an efficient data structure to constantly extract the minimum or maximum value? Well, that data structure is actually a heap. We've looked at this before. So what we're going to do is we're pretty much going to represent our kind of distance structure here, this distance table using a min heap. That means that any time we do a removal operation from our min heap,
1:59:17
that's going to be log base two of V, where v is the number of vertices inside of the heap. And at most we'll have the maximum number of vertices v. Hence what's log base two of v. Now we are doing that removal operation v times right. So we have v multiplied by the log base two of v. That's the basis for our time complexity. However we're not done yet. The reason we're not done yet is because for every single vertex, we need to look through all of its edges.
1:59:43
And for all of those edges, we potentially need to update their weight or update. Sorry, the nodes shortest possible distance inside of our heap. Now, I might not have talked about this before, but to perform an update to have, a key value inside of your heap that's going to take log base two of V time, which means will we actually end up getting for our time complexity is V plus e multiplied by the log base two of v. Now let me break this down a little bit more.
2:00:11
But this is the time complexity of this implementation of Dijkstra's algorithm. There's some ways to speed this up. We're not going to get into that complexity in this video anyways. Let's look at this. So the maximum number of kind of removal operations where we're grabbing the minimum key from the heap is V. And then the maximum number of update operations is E. Because we only do an update once for every single edge. And we only do a removal once for every single vertex.
2:00:37
So all we have to do is say if we add the vertices and the edges together, and then multiply that by log base to a v, that's going to be our time complexity. So that is the time complexity of Dijkstra's algorithm. Hopefully that makes a little bit of sense. But by having that visited set that means we're never repeatedly doing update operations for an edge. So we only do at most e update operations and at most V removal operations, both of which take the same time.
2:01:02
Hence why we can multiply them by the same value here. So that's the time complexity of Dijkstra's. And that's pretty much it for Dijkstra's algorithm. You should at this point be able to kind of replicate this algorithm by hand and go through what I just showed you here. By remembering that step by step process, you start at the starting vertex. You update all of the unvisited neighbors, then you remove whatever, vertex has the shortest possible distance to it, update
2:01:27
all of the unvisited neighbors, and repeat that process until you've gone through every single vertex. All right, so that's great. However, if we have a more kind of complicated graph or just a different graph persay, in fact, let me erase all of this. You'll see the Dijkstra's algorithm can actually be fairly inefficient. For example, imagine that rather than having like a standard graph, we have this grid structure which we can kind of represent as a graph.
2:01:51
Okay, we kind of looked at this in one of the previous videos when I showed you, pathfinding with breadth first search. But if we have a look at this here, we can technically say that this is a graph, right, where every single node is one of our entries. And then all of the neighbors, right, are just adjacent elements. Now we could have different weights, or we can just say the weight is one doesn't really matter. Regardless if we have this type of graph,
2:02:13
let's say we're going from this node here. And we want to find the shortest possible distance to this node. Well, if that's the case we can run Dijkstra's algorithm. But if we run Dijkstra's algorithm what happens is we're going to find the shortest distance to every single node. And we might not necessarily care about the distance to the node here. We only care about the distance here right. So ideally we'd want a path kind of like this right. Or like this or like this.
2:02:39
There's multiple paths that are the same distance. We just want to find that path. I don't care about the distance to this, this, this, this, this and a bunch of other places. Now, if that's the case, we can't use Dijkstra's algorithm, because if we use that, as I'm saying, it's going to find every single distance which is inefficient and unnecessary. So if all we're trying to do is find the shortest path, well, what we can do is use something known as the A-Star pathfinding algorithm.
2:03:04
Now, the A-Star pathfinding algorithm is a variation of Dijkstra's algorithm that uses something known as a heuristic. Now, this only works in specific situations, but what this does is attempt to estimate what the distance is from any given node to the end node, and then use that heuristic when we're picking nodes to visit. Okay. So in Dijkstra's algorithm we used whatever the current shortest path was, which means this node, this node,
2:03:31
and any other nodes we visit end up getting a very similar value constantly. Right. Like this node in this node have the same distance value inside of our heap. This one has the same distance value if we're able to go diagonally, etc.. Okay, so we have a bunch of nodes that always have the same distance. Whereas we know looking at this visually, that really the direction we're attempting to go in is this direction. And we know that this node here is further away from that node.
2:03:58
Then say this node, we can see that visually in this graph structure. So what we can actually do is for every single node inside of our graph we can calculate something known as a heuristic. And the heuristic is the estimated distance to reach this node okay. So in this type of graph situation we can use Euclidean distance which is essentially just taking the kind of straight line distance based on the graph x y coordinates. I won't get into that right now.
2:04:26
And then we can use the Euclidean distance. Add that to whatever the current minimum distances we found to reach a specific node, and then prioritize nodes based on their current minimum distance plus the predicted distance. Hopefully this makes a little bit of sense, but what we do is add this heuristic in, and that now means that we end up prioritizing nodes that are closer to this node than ones that are further away. So if we expand the graph, this becomes a little bit more clear, right?
2:04:52
I know this is a little bit messy, but if I have some more squares over here rather than me first going here and trying to find the distance to this node. So going like all the way here, I would simply only look at nodes that are kind of within this bounding square, because any nodes that are further away, they're going to have a much larger heuristic distance to go from here to that node to this node. So it essentially allows us to eliminate a significant amount
2:05:16
of the nodes that we would have to typically traverse, because we're doing an estimate of the distance to the final note. Now obviously we have to go through this whole thing until we find the final node, because we could have more complicated, what do you call it, kind of mazes here where we have like obstacles. If that's the case, we can still use a heuristic. But since we have obstacles, that means that we still might have to traverse
2:05:38
through more nodes to be able to find a viable path to get to this end. Note I don't know if this makes any sense at all, but I'm just trying to give you some brief introduction without going into a ton of details here about A-Star, because this is a bit more complicated when it comes to the implementation. So with that said, I think I'm going to wrap up this video here. If you're interested in the A-Star pathfinding algorithm, please feel free to look it up.
2:05:58
There's all kinds of great visualizations and tutorials on YouTube. It's just not something that we really need to focus on in this course. But I did want to give you kind of that little piece of information and a bit of insight in case you're interested in how all of this stuff works. So we have a graph here. Now what is the minimum spanning tree of this graph. Or what is first of all a spanning tree? Well, a spanning tree of this graph is simply a set of edges
2:06:21
such that they connect all of the different vertices. But there is no cycle. Okay. So if we're doing a spanning tree, we can come up with quite a few for this graph. So I'll kind of do it in purple here. We have these edges this edge and this edge okay. This is a spanning tree. The reason for that is all of our vertices are connected here. And there's no cycle between these different vertices. Now finding this spanning tree is possible in this undirected graph. Okay.
2:06:51
Now the minimum spanning tree is exactly this. Except it's the set of edges such that the weight that we would take to go across all of these different edges is minimum, right? It's the smallest possible weight that we can have. So if we're trying to find the minimum spanning tree this is actually a non-trivial operation. Now in this small graph it might be easy for us to do this visually. But again imagine a graph with 5000 10,000 nodes.
2:07:17
It's not easy for us to locate what the minimum spanning tree of that is, because it might seem like, oh, I'll include B, but by including B using this edge here, that means that I might be forced to use another edge that has a very, very large weight. So instead, I might want to use two medium weights rather than one small weight and one very large weight. Maybe you get what I'm saying here, but the idea is to locate this minimum spanning tree.
2:07:40
There's a few different ways that we can do this, right. So the first way, in the kind of naive way to locate the minimum spanning tree would be to find every single possible spanning tree and then just find the minimum of that. Now, that's going to be a very poor time complexity operation, because first of all, finding a spanning tree is not that easy to do. And then finding every single one of the spanning trees and comparing them, well, that's just going to be inefficient.
2:08:05
So there must be a better way to do that. And in fact, there is. So let me walk you through an algorithm which is known as crew School's algorithm. Now, I should probably write this out because I'm definitely mispronouncing the name. So crew schools algorithm. And again I have no idea if this is actually how you pronounce it. So apologize here. Then this finds the minimum spanning tree, which is also denoted the MST. Okay. Now the basic, kind of I don't know, overview of this algorithm
2:08:32
is that what we're going to do is sort all of the different edges that we have by their weights. Then what we're going to do is we're going to pick the smallest edge, and we're going to check if it forms a cycle with the spanning tree that we found so far. If it doesn't form a cycle then we're going to keep it. If it does we're going to get rid of it. And then we're going to repeat this step until we have v minus one edges in the spanning tree.
2:08:59
As soon as we have v minus one edges that means that we will have located the minimum spanning tree. Now this assumes that we have a connected graph. Okay. If we have an unconnected graph then this isn't going to work. Exactly. Kind of how I'm showing it to you. But in this case we're going to assume that we have an undirected weighted graph that is connected, okay. For the school's algorithm to function properly.
2:09:22
All right. So how do we do this. Well let's make this a little bit smaller. And let's start with step one which is to sort all of our different edges. So let me sort all of the edges that we have here. And then I'll be right back. All right. So step one is complete. I've sorted all of the edges. Now what I'm going to do is just kind of box this off here. And I'm going to start drawing out with the minimum spanning tree will be. All right.
2:09:45
So we begin by selecting the first edge with the minimum weight that's b to d. So what I do is I write b to D
2:09:55
and I select this edge and kind of place this as my minimum spanning tree. So right now this is what we currently have. Obviously we need to go through the rest of the edges. Now the only reason I could insert that in my minimum spanning tree is because we don't form a cycle when we use this edge. So right now we'll kind of mark this as yes, we've used it. Okay. Now we move to the next edge which is a B with a weight of one. Now if I insert the edge a b, does that cause a cycle?
2:10:23
Well it doesn't. And we can just look at this visually. There is a way to determine this algorithmically. We're not going to go through that right now. But for now we can see that it doesn't form a cycle. Okay. So this is perfectly valid. So we insert that edge. We now go to the next edge. We have an edge from B to C with a weight of two. Does that cause a cycle. No it doesn't. So that means we can now insert C here with the edge between B.
2:10:45
And what I could probably do is just write the weights here. So we have those in. All right. So now we have included three edges. Now we have an edge from C to D with a weight two. Now if I attempt to insert this edge here you're going to see that we get a cycle between BC and D. So we can't insert that. So we leave that one out. Then we have an edge from D to E with a weight of five. Now that's not going to cause a cycle. So I add that in here and I write five.
2:11:12
Now at this point I have v minus one edges. So I can go ahead and stop my algorithm. Now I could continue through the rest of them, but there's no point in me doing that, because all the rest of these edges that I want to add are going to form a cycle. The reason we know these are going to form a cycle is because we've already added v minus one edges. So if I add up to v edges, that means I would be having to connect another node to a different node that already has a connection.
2:11:39
Like I have to do this, this, this, something like that. Which would cause me to have a cycle. I don't know if that makes sense what I've described here, but what I've just located is the minimum spanning tree using Cru school's algorithm. It's actually fairly straightforward, right? You sort the edges. You then insert every edge into the spanning tree until one of the edges that you insert causes a cycle to occur. Now in this case, the three edges that are in our minimum
2:12:03
spanning tree are the ones that are check marked. So we have a total minimum spanning tree kind of weight of nine. Right. Because we have one one, two and then five. So the minimum spanning tree has a weight of nine. And this is one of the minimum spanning trees. Now we could actually have another minimum spanning tree that's the same as this. So for example, if for some reason we had sorted the edges such that this one and this one were swapped,
2:12:28
then what we would end up getting is a different minimum spanning tree. So let's write that one out where let's say we didn't include that and we included this. Then that means we would now have an edge from C to E. This would have a way to five. This is another valid MST that has the same weight as nine. Okay. So it doesn't really matter which one you find, so long as you find one that has that minimum weight. In this case the weight is nine. And there's two, different edges.
2:12:53
We can add here that will cause that same minimum spanning tree. Okay. So that was Cru school's algorithm. Now there is another algorithm to find a minimum spanning tree, which is known as Prim's algorithm. Now I'm not going to get into Prim's algorithm because it's not really necessary for this video. But now that you understand Crusoe's, you know how to find an MST. All right. So now that we've done this and we've located the minimum spanning tree, and we know that we have another
2:13:15
algorithm like Prim's algorithm that you guys can look into on your own time if you want to do that. Let's quickly talk about the time complexity of this algorithm, which is actually quite a bit simpler than something like Dijkstra's. Let me move that over here. So what are the steps in our algorithm? Well, the first and actually most computationally heavy step is to sort all of our edges. So to sort our edges. How long does that take. Well that's going to take e multiplied by the log base
2:13:42
two of E time where e is the number of edges that we have. Okay. There you go. That's how long it takes to sort the edges. Then what do we need to do. Well we simply need to traverse through every single one of these edges and determine if they cause a cycle. So traversing through all of the edges takes at most e time. So for every single one of our edges, we need to find if they cause a cycle when being inserted. Now I'm not going to go into how that algorithm works, but
2:14:12
I will tell you that is called the union find algorithm. And that algorithm runs in a time complexity of log base two of the time. Okay. You don't have to implement this. We're not even going to look at the code. Just know that there's something called a union find algorithm runs in log base two of V and determines if a cycle is caused by inserting an edge. So that means that the two things we have right is we have this first operation E log base two of E plus e log base two of V.
2:14:40
Now what we need to do here if we want to simplify this is we need to essentially swap out some of these variables. So we have v. If we can write v as e then we can simplify this time complexity. So the way to do this is the following. We need to assume that v is equal to e. Now e is always going to be at least v minus one okay. So e is always greater than or equal to v minus one. Because v minus one is the minimum number of edges required to have a connected graph.
2:15:11
And in this case we have a connected graph. So if we say the number of edges is greater than or equal to v minus one, then that means that we can remove the one when we do this right. And we can just say that e is greater than or equal to v. Now if e is greater than or equal to v, if I say v equal to e. If I do this assumption here, that's fine. The reason that's valid is because this variable is always larger than this variable.
2:15:35
So if I assume that my vertices are larger than my edges or they're the same story, then that means that I can now replace any instance of V with E, so I can come here and I can make this E. I can't do it the other way around because my vertices will oftentimes be less than my edges. But as long as my edges is always greater than or equal to my vertices, then I can assume that my vertices are equal to my edges. So that's what I'm doing here.
2:15:57
And now I get e log base two of e plus e log base two of e, which means I have two e log base two of e, which means I can simply cancel out the two and write the Big-O notation as the Big-O of e times log base two of e, meaning the time complexity of finding the minimum spanning tree is simply that. Okay. If you want it to be more granular, you can write it out how I had it. So e log base two of E plus e log base two of V. That would give you a more accurate time complexity.
2:16:28
But this is fine to write it in this kind of, format right here that we have. Now. Dynamic programing is an algorithmic technique for solving an optimization problem. Typically what we'll do with dynamic programing is store results to previous subproblems and use those results to allow us to more efficiently compute the results of the overall problem. So don't worry too much. Again, about the definition. The general idea is that in a lot of instances,
2:16:56
what we can do is use results of smaller problems. Having all of those results allows us then to solve the larger problem. And typically again, we're going to be storing those results or at least storing one of those results. So to illustrate that to you, I'm going to introduce a pretty famous algorithmic problem. This is actually something you might get during a coding interview. And I'll kind of walk you through how we solve this with dynamic programing.
2:17:20
So the problem I'm going to introduce to you here is something known as the minimum sum of a subarray. So the goal here is to look through any arbitrary array and determine what the minimum possible sum is of any continuous subarray. Now a continuous subarray is any subarray that contains elements that are adjacent to each other. So three and four. That's a continuous subarray. Three negative two. Negative three continuous subarray. You get the idea okay. Even an element which is just itself.
2:17:49
That's a continuous subarray. However, an array like negative seven and negative four that's not a continuous subarray. So it's not what we're discussing. So let's naively go through this and figure out what the minimum possible sum of any given subarray is inside of this array. So let's actually start from the end, because I don't want to kind of spoil it by starting at the beginning. So if we start at the end here we can see the negative three is a minimum subarray.
2:18:16
So we'll write negative three right here because you can have a subarray with one element. Then we can move to the next element. And we can kind of look at these two together. And we can say okay our negative three and negative one added together. Is that a minimum subarray that gives us negative two. So no that's not a minimum. Then we could go from -3 to 1 and two negative three. And we could add all these together and say okay well we get negative five.
2:18:39
Well that's actually less than negative three. So let's update that. Let's continue. That gives us negative seven. Okay. So let's put negative seven here. Let's continue. Well that's going to give us negative three. Well negative three is not less than negative seven. So let's continue. Now we add three that gives us zero. Well that's not less than negative seven. And you get the idea. And we would continue this. Let me just kind of draw some better lines here.
2:19:03
For every single element we have inside of the array. So in this example we'd have to find the sum of every single subarray that includes every single element. So you can kind of see how I'm drawing this out here just for one element alone. We have n minus one possible subarrays. Right. Or actually we know we have n subarrays because this is included. Now that's going to be the same for every additional element. So now imagine we moved to one. Well then same thing with one.
2:19:31
We need to find all of the subarrays that include one. So you get this kind of massive amount of arrays that we need to look at. And then of all of the subarrays you're going to find with a minimum service. So this is the naive approach to solving this problem. You go you find every single subarray that exists. You find the sum of the subarrays. And then you figure out what the minimum, sum is of all those different subarrays. So that's possible.
2:19:55
All of you can probably write that code, but that is not optimal. So at least hopefully that explains the problem. Anyways, let's quickly look at what the code implementation be of that approach. So here we have minimum sub subarray. This is the JavaScript code that does exactly what I was trying to illustrate to you. What we do is we make sure the array dot length is not equal to zero. If it is, we just return zero. That's the minimum sub sum. Sorry, not sub of an empty array.
2:20:22
We then set the minimum sub to be equal to infinity. And then we go through and we generate with this nested for loop every single possible subarray that exists. So we say for I and the range of write out length. Then we set j equal to I plus one to make sure we don't duplicate subarrays then we say this goes up again to the array dot length. Then we create the subarrays using I and j. So we take a slice here of the array. Actually this should be j plus one I believe.
2:20:48
But anyways, don't worry about that for right now. And then we calculate the sum here of the subarray using the reduce function. And then we set the minimum sum to be equal to whatever the current minimum is or the sum that we just calculated. Now in this example this actually runs in big O of n cubed time. Now the reason it runs in n cubed time is because this takes n. This takes n. And then actually creating this slice here of the array takes big o of n time as well.
2:21:17
So you have n times n times and giving you n cubed. Now if we imagine that this would run in big of one time, then we would be able to reduce this to n squared time. But even in this situation, this is a very poor time complexity for this algorithm. We shouldn't have to do this because we're going to be doing a ton of repeated work. All right. So I've got a new example on the screen here. And as we saw in the previous kind of naive approach here, the reason why we had n squared time
2:21:41
complexity is really because we're repeating a ton of different additions operations. So the first thing to think about when we're doing this, some kind of optimization, is how can we avoid doing any repetitive tasks. So the first thing to kind of keep in mind here is that if I've already calculated the sum of, say, these elements here, I don't know what it is off the top of my head. But let's say, you know, we've calculated x that's the sum of this subarray.
2:22:05
If I want to add negative four into this subarray, I don't need to re add every single one of these values. I already know what the sum is or to calculate it, all I need to do is take x and add negative four. Then that gives me a new sum and we can continue right. If I want to add six again I don't need to repeat this calculation. I just take whatever the sum of this subarray is. If I've stored that and add that to six. So that's the first thing you should kind of be thinking of
2:22:34
when you see something like this. How am I going to avoid doing repeated in this case addition operations. Now that alone is not going to allow us to solve the problem, but it will let us kind of be in a mind space where we're thinking, all right, how do we avoid these repetitive operations? Now, typically speaking, the way you avoid repetitive operations is you cache the results or you store the results. So what I was just showing you there
2:22:57
would, would have been an example of us storing the sums of previous subarrays. So we can then use those values when we calculate new Subarrays. Now what we actually want to do here is we want to ideally only look through this array one time. I don't want to have an n squared time complexity. I'd like to try to get down to n. So how do I get down to n. Well, the only way for me to get down to N is going to be for me to store values. But what values am I store?
2:23:23
Well, what we're going to do is we're going to start by looking at the first element in our array. For the first element we're going to ask the question what is the minimum. Some subarray that I can create using this element that includes this element. Now right now we'll say that that is 20 okay. Because we're going to look kind of to the left here. You'll see what I mean in a second. So I'm going to mark down 20 here being the minimum sum. And I'm just going to come say min equals 20.
2:23:49
And we'll update this variable. Now we'll move on to the next value which is negative seven. At this point we've already calculated the minimum possible sum that we can have with the value 20 is 20. So now we're on negative seven for negative seven. What I'm going to ask myself is the same question. What's the minimum possible sum that I can use or that I can create with a subarray that includes negative seven. Now the way to do this is to say all right, I can either
2:24:16
just have this element here or I can have this element and the sum of the previous minimum subarray. Now the previous minimum subarray is 20. So if I decide to include the element to the left hand side here, then the sum that I'm going to get is 20, which means I'm going to have 20 plus negative seven which is going to give me 13. Now is 13 larger or smaller than negative seven. Well it's larger the negative seven which means I don't want to include
2:24:48
the left side here in the subarray that includes the element seven. So I just write negative seven here to indicate okay. If I have a subarray that includes negative seven, the minimum possible sum I can have at this point in time is negative seven. So then I write the minimum sum here of negative seven. Don't worry this will become clear as we go through the rest of the examples. So now we come here to negative three. Now a negative three. We asked the same question.
2:25:13
We say what is the minimum possible sum of a subarray that we can make that includes this element. Well I have two options. I can either just use this element or I can use this element. And then anything that comes to the left of it as long as I'm moving continuously. So what I do now is I look to my left, and I specifically look at the minimum sum that we can create using a subarray that includes the element to the left. Now, the minimum possible sum of the element to the left here
2:25:43
so of a subarray that includes the element to the left is negative seven. So that means that if I use that I'm going to get a better sum here a lower sum. Then if I were to just use this element. So I'm comparing negative three and negative ten. Obviously negative ten is larger. So I place negative ten here. And then I change my sum to be negative ten. So hopefully you see what's going on here at every single element I'm asking the question okay.
2:26:09
If I include the previous element what is the minimum possible sum that including the previous element gives me. Well, from the previous element it's the same question what's the minimum possible sum that having this element or potentially the last element gives me? So in this case we're really using this as our minimum sum subarray. We're not including 20 which has already been decided when we got to negative seven because a negative
2:26:35
seven the minimum possible sum subarray is just negative seven. It could have been the previous element if the previous element had a lower sum right, like a lower sum than zero, then it would have been negative. Okay. Anyways continue here. So now we move on to nine. So now in nine again I asked same question. Well what's the minimum possible sum I can create. It's either going to be nine. The element itself, or I can include whatever the minimum
2:27:00
sum is of the previous element that's included in some sum subarray. Sorry. So in this case I want to include the previous element. Because the minimum sum that I can have is negative ten. So now I'm going to have negative ten plus nine which is going to give me negative one. Now negative one is not less than negative ten. So we don't update negative ten. But you can see that now if we were going to use this here right. Like these three elements this subarray has a sum of negative one.
2:27:28
So the subarray including nine the minimum sum we can have is negative one I know I keep saying the same words 100 times. It's not really avoidable. But hopefully you kind of see what's going on here. Every element decides do I include just myself or the element previously. And then what will end up happening as we move through this is we'll find whatever the largest continuous subarray is based on kind of all of these operations that we're doing. So now we move on to negative four.
2:27:53
Now in negative four we ask okay do I want to include the subarray that includes the last element. Well since the sum is negative one I do because that's going to give me a sum here of negative five. So that would be here to here right. Negative five okay. So I do include that. Otherwise it would have been negative four which is less than negative five. So now I move on to six from six I ask myself do I want to include the subarray that contains the previous element.
2:28:20
Now the minimum subarray sum that includes the previous element is negative five. So obviously I want to include that. That means the sum here is one. So if we have the subarray like this then the sum of that that's going to be one. Okay. Moving on. We have negative nine. Now from negative nine we ask ourself do we want to include the previous sum subarray or the subarray that includes this previous element. Now if I look here we see that we have one.
2:28:46
So if I decide to include this that's actually going to make the subarray sum of this larger than if I just have the element itself. So at this point I say no I just want to have the element. So I just write negative nine. So this is now the subarray with negative nine. The minimum we can create. We don't want to include this again because that would make it larger. Then we move on to ten from ten. Obviously we want to include negative nine. So that gives us one.
2:29:12
Now we have gone through every single element inside of our array. This only took us Big-O of n time, and we have determined the minimum sum sub array by using dynamic programing. And what we did is we stored all of the results as we went through here and built our way up until we went through the entire array. And the way this works, just to recap one more time, is we're saying at every single element, do we want to include the minimum subarray of the previous element,
2:29:45
and the previous element already knows what the minimum sum is? It can make by having itself in a subarray, and we keep kind of going right from the smallest possible case where we have one element, to a case where we have a subarray of like 7 or 8 elements. We don't need to know what the subarray actually is. We just care about the minimum sum that we can generate which is negative ten. So let's have a look at the code implementation and this will make a bit more sense.
2:30:09
So this is the code implementation actually right here. Sorry not that other one. Okay. So let's have a look at this. So minimum subarray sum dynamic programing. What we do is we check if the array dot length is zero. If it is we just return zero. We then have an array here that we use to store the results that I showed you over here. Okay. So coming back this is the array where we're going to store those different results. We then have whatever the current minimum sum is.
2:30:38
Now we just start at index one or index zero here. And we say okay well the minimum sum. So far we'll just set it to be equal to the value of the first element. And then we'll store that first element value inside of the array as kind of the base case here for our dynamic programing. Then we go and we have one pass through the array. At each pass we grab whatever the current element is. So we just get that number and then we say what is the minimum
2:31:03
sum of a subarray that we can make that either just is this number or is this number plus whatever the previous minimum sum is. So using that previous element. So that's why we have I minus one because we're looking back one position in this array. We get that current minimum. And then we push that minimum value into this array. So now we're storing all of those results. Then we update the minimum sum to be equal to either the minimum of whatever the current minimum sum is,
2:31:34
or this new minimum that we just generated by using this current element. Okay. That's the whole algorithm. Now this runs in Big-O of n time.
2:31:45
However this also takes big O of n space takes bigger event space because we have this array. Now remember what I said at the beginning of this kind of optimization? Is there a way that we can avoid repeating? Or is there a way that we can get rid of unnecessary information? Well, if we go back here, notice that we don't actually need any of the previous values in our array to generate the next value. What I what I kind of mean by that, there was a backwards way of saying it is
2:32:15
that if I'm at this position right here, I don't need to know any of these. I just need to know what the previous one was. Right? So there's actually no reason for me to store every single one of these values when I'm only ever using the previous value. So what we can do to optimize this, even further is we can go to this new solution here, where what we have is the following. We just store whatever the minimum sum is using the last element. We don't store an entire array
2:32:44
because again we only have to access that last value. So now this is the exact same thing as before, except we've reduced the space complexity to constant space. So we've now gone from a big O of n squared or n cubed time algorithm to a big O of n time algorithm with constant space using dynamic programing, which allowed us to kind of solve these smaller subproblems and build up to the solution of the larger problem. So with that said, I'm going to wrap up the video here.
2:33:15
Hopefully this was helpful and gave you some information about this problem solving technique. This is quite useful and something that you'll see quite a bit if you start studying more about data structures and algorithms. Anyways, I hope you enjoyed this video and I look forward to seeing you in the next one.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat