Introduction to Data Structures and Algorithms

hey what's up everybody it is Caleb and welcome to your introduction to data structures and algorithms this is going to be a fantastic video if you're in school and you aren't paying attention or if you're trying to get a career in software development computer science whatever it might be but no matter what it is somehow you landed on this video and I'm super glad to see you here because this is going to give you all of the fundamental principles to understand algorithms and data structures when I went through computer science school I had a data structure than algorithms class and it seemed like every single algorithm or every single data structure I was introduced to was this entire new mountain I had to climb looking back I didn't realize there were some key principles I could have learned that would have made learning all of them a whole lot easier so if you stick with this video and also the videos in this playlist you'll probably build that foundation such that you can learn any of the data structures or any of the algorithms with ease now I still am it it is a lot of work and there's a lot to wrap your mind around so it is gonna be a challenge but I'm gonna make it easy for you guys so let's just get started and we'll just see where we go so first thing why is algorithms always associated with data structures how are they related well algorithms process data that data is stored in a data structure that is why they are connected all over the time because it's kind of like this does the work this stores the data so they need to be paired together so algorithms we're going to take a look at those first and then we're gonna take a look at data structures so an algorithm is just a process of doing something and we're gonna think about it really generally here and then we'll try to get into some examples so anytime you write code even if it's something super simple let's just say all we do in our code is we just print hello this is like the smallest line of code you could ever possibly write you could consider this an algorithm your code what does it do it prints hello more than likely though the code you write is going to be numerous of code but basically I want you to think of an algorithm as just a section of code that does something oftentimes this code that we create for these algorithms will be put inside of a function functions are just names for a series of code that we can then call to save ourselves some time and energy so here's an example we might have a function sort data and then this requires us to pass some data in and when we do this we will get a sorted thing of data back what do I mean by sorted most likely at least a greatest or alphabetical whatever it might be so since this does all of the work for us we can just assign the end result to a variable so we would have a variable sorted data and we would assign it this call here so this is what invoking this function might look like and now let's talk about where this data comes from trying to erase here we might have a list up here or an array and we just have some data in here so we take this variable data we pass it to sort data and the end result is sorted data let's talk about now where the algorithm is and where the data structure is so this would be the data structure the algorithm is this right here functions make our life a whole lot easier because we don't need to worry about all of the code that actually does the sorting and that's often what will happen when you're using Java or Python you can just invoke different functions that do things for us but if we're in a algorithms and data structures class we're probably going to want to know the actual steps that are taken such that we can just call sort data and get a sorted list back so that is where algorithms focuses it focuses on what this function actually does now data structures well here's a simple example I said this was a list or you can think of it as a dynamic array it really depends on what programming language you're going with but I was thinking Python here so we have this list and it's a way to store data however we just use it very easily but behind the scenes it needs to decide how this memory is going to be allocated where the data is going to be stored and so forth so the data structure is part of data structures and algorithms is learning the behind the scenes of how something like this works how does it look inside of a memory how do we add data to this list how do we delete data from this list now when you start studying data structures and algorithms you're going quickly realize that there are a ton of different options there's so many different algorithms out there and there's so many different data structures out there and the reason that is is because different ones are ideal for different purposes so as an example this here let's just say this is a very general list what does that mean exactly doesn't really matter but behind the scenes this can store the data in various ways just as an example here it could use a dynamic array or it could use a linked list these are two examples of data structures that could be used in the case of Python actually uses a dynamic array but for the point of this it doesn't really matter all we know is that we just use it we put data in there and it works behind the scenes these are two totally different ways of storing information and they both have their pros and cons so you'll quickly realize that the reason there are so many different options is because they're all optimized for different things you might want to use a linked list in certain situations and you might want to use a dynamic array in certain situations so don't let it scare you if you see a bunch of different ways to store data there's a raised dynamic arrays linked list queues stacks and it just goes on and on and for algorithms just an algorithm to sort data there's like a kajillion of them you know there's bubble sort there's insertion sort and you can find lists and figure out which ones are best for what scenarios so if there are so many different options for algorithms and data structures there's got to be a way to measure which ones are good and which ones are bad for certain things this is where the concept of Big O notation comes in it's basically a system to measure performance for different algorithms and data structures so I mentioned there might be 40 different sort algorithms well one might be faster than the other so let's take a break from all this crap and take a look at Big O notation and it is a very Matthew subject I'm not going to get too much into the math I'm primarily going to focus on giving you what you need to pass a computer science class or to develop a career in software development so let's go over that now before we talk about the notation on how to decide which algorithms are faster let's just go through a simple example and say you are standing right next to your friend so this is you you're hideous and I'll be your friend in this scenario so this is me and this is you and right now you're super super close together I mean we could practically hold hands we're not going to but I'm just saying we're pretty close and let's say we start walking together so we're walking this way now you might not be able to see here but it might be the case that I'm just walking at a slight angle this way so let's say that's the case and I'm walking this way and you're walking straight at the start it doesn't really matter because we still stay pretty close together but imagine we take one Katrien steps well at that point we're gonna be so so so far away from each other that we no longer could even see each other this concept is very important to understand with algorithms because when we're working with really really small amounts of data that's like working up here and which algorithm you choose doesn't make a whole big difference it's better that it just works correctly however when you start growing your data to very very large like thousands or hundreds of thousands or millions of pieces of data well now it makes a very very big difference if an algorithm is slower than another algorithm you're probably not going to notice with a very small number of pieces of data it's kind of like just taking a few steps next to me but just slightly different angles but that difference is going to be extremely obvious as we increase the size of the data so as a computer scientist it is your job to basically figure out different classifications of these algorithms some being pretty slow some being just drop my chalk some being extremely fast some being somewhere in the middle and again as a reminder with small data sets you're not going to see a huge difference but as that data set grows and grows and grows the difference is going to be extremely different another way you can think about it is my gosh dude seriously I just dropped and broke another piece of chalk it's like for now so I want to go through a very simple example and to do this I want to imagine that we have some data so let's create an array which is basically just a bunch of pieces of data together in memory and I'm just gonna put some data in here and now I tell you hey I want you to get the very last element in this array well it's probably fairly simple the last one is this one here if you know how much memory each one of these numbers takes up you can just jump to that position in memory that's because these are all sequential in memory you start here and you just say oh whatever the size is multiplied by 5 and boom you're here so you can get this number for me very quickly now let's say here's a different example instead of using an array we're using a linked list this is structurally different and we're going to do videos dedicated to linked lists here soon but in this situation the data is not connected instead they are separate and they point to each other the first one points to the second one the second one points to the third one and so forth well because these are not all together in a line inside of memory in order to get this piece of data you actually have to start here go to the next element go to the next element next one and then the next one so it actually took us five different operations whereas this one you just jumped right to the end and you were done so with a data set of only five members it doesn't you make a difference because computers are so extremely fast it's just going to get that data almost instantaneously you're not even going to notice but if instead we had ten million pieces of data starting at the very beginning and going all the way to the very end is going to take a whole lot longer than just automatically jumping to the end so this one is in a whole different class of speed than this one so how would we actually write that what's the notation to say the speed of this thing well what's the operation we're trying to do we're trying to retrieve data and for the operation we assume the worst case so at the very end so we're trying to retrieve data and this one is an array so for an array the way we would write this is oh and then in parentheses a 1 so this is the classification for retrieving data from an array another way to say this is it's constant time now let's take a look at the same thing with a linked list well in this situation to get that fifth element we actually had to go five times so it's whatever the size of the list is and if you say n is the size in this situation it's five but we're being more general here we're saying n is the size of the list you would say o of n so retrieving data from an array is Big O of one retrieving data from a linked list is Big O of n there are other classifications about as well so there is N squared which is really bad there's n factorial which is like worst case scenario that is absolutely horrendous then there are other ones such as log n these classifications are only noticeable as the data size increases so for example n factorial this is going to get extremely extremely slow in this situation if you had 100 elements an N factorial algorithm would be 100 times 99 times 98 all the way down to 1 and whatever the final answer is that is how long it would take that's how many operations it would take so as the size increases this one just gets extremely extremely large so we're going to focus on this chunk a little bit more in the next video the main thing I wanted to share with you guys is that there's different classifications of algorithms and different data structures sometimes require different ways of doing things in this situation the linked list required o of n here in order to grab that last element now when you are doing interview questions you'll often be asked about optimization so that's what I want to talk about now all right so you just finished your interview for senior software engineer at Google and you developed a linked list and they want you to grab that last element and you do and you can clearly tell that it is o of n and they say we need you to optimize this how can you make this more efficient we don't have time for o of n we're Google we're processing unlimited data here well this is where you use your brain power but there's often different things you can do it might be a small trade-off but the reward is very significant when you're working with large amounts of data here's a solution so often when you have a linked list you're going to have a pointer to the start that way you know how to get the data if you wanted the fifth element you go to the start and you would just go to the fifth element who want to add time there if you're regularly going to be grabbing that last element or up ending data then you can keep a pointer to the end and now to grab that last element you just get the value of end and you're done so you just brought this from oh uh ven down to o of one so you brought it from dependent on the list size to a constant time algorithm very very awesome so the downside here is you have to have another pointer you no longer just have star you also have end but that is a small consequence to save so much time when you are appending data to this list all right so the Big O that is a way to measure complexity we talked about classifying algorithms by the different complexity you could also classify them by different things such as implementation so you could create an algorithm to process data recursively or you can make it iterative there are also other optimizations you can do such as dynamic programming if you want a taste of some other stuff when it comes to data structures and algorithms there are trees and graphs so a tree is basically nodes that are connected and you can create algorithms to process or basically traverse this tree there's also graphs which are very similar to trees it's just not necessarily in that same structure so we can have them pointing all kinds of places and a good example of this might be imagine a map these are the major cities you know and you want to create an algorithm to go from Los Angeles up to New York City well there's a ton of different paths you could take so let's say we wanted to create a GPS app to tell you how to get from Los Angeles to New York City well that app is going to have to analyze the different paths to these different cities which one's going to be the shortest or which one's going to be the most highway or avoid tools or whatever it might be and you need to make that decision algorithmically to tell the driver where to go these are the kinds of things algorithms do they are tightly paired with data structures because oftentimes the data structures contain the information that the algorithms process without this data structure here there would be no algorithm to follow a path it wouldn't make sense so that's why algorithms and data structures are so close together whoo so it looks like I tried to cram an entire semester in one video which we can just know is not possible so stay tuned for the next video because we're gonna get into some more information and if you need some code samples for this check out my program code breakthrough I will try to leave a link in the description for you guys and that's all I got so do me a favor and just hit subscribe it's my personal value indicator so if you want me to feel good about myself and you got a subscribe right now I'm just playing but I definitely appreciate all subscribers and I'll see you guys in the next one [Music] you

Channel: Caleb Curry

Views: 71,068

Rating: 4.9742846 out of 5

Keywords: data structures and algorithms, data structures, algorithms, big o, big o notation, time complexity, arrays, lists, trees, graphs, tree vs graph, shortest path, computer science, cs50, python, java, c++

Id: 4RLhuZ3N9nc

Length: 19min 42sec (1182 seconds)

Published: Sat May 16 2020