hey guys welcome back to the Cs classroom um so what we're going to do today is we're going to talk about topic five which is abstract data structures now this video is meant to be a review of topic five um my recommendations for how to approach this topic would be first to Not freak out a lot of students interpret this topic as being extremely difficult kind of being beyond their capability but the reality is that once you learn the fundamentals you can definitely get past it the level of content seems sophisticated at first but it's not as difficult to grasp as you think it might be once you start solving problems and actually using them in practice so the next thing I would also recommend is to practice your reading comprehension like one of the reasons why this topic can be difficult is because a lot of the problems that are involved with it on the IB exam are very very long and require you to analyze and digest a lot of information just to figure out what the question is asking you and what information you have access to so we're going to go through some IB problems in this video make sure and practice your reading comprehension skills both when looking at some of these problems in the video but also in practicing on your own and finally this is probably kind of repetition of like everything I just said but you need to do practice problems um which is why again that's what's going to be in this video so to conclude do practice poems now we're going to be talking about two types of data structures the first one is static data structures static data structures are basically arrays that's the most common static data structure that you see in the IB now what a static data structure means is that the number of elements is determined at the creation of the data structure so it can't be changed later on so you might have an array called nums that looks something like this that means that you have an array called nums with 500 elements and that cannot be changed we can't have 501 or we can't have 502. now one of the problems with static data structures is that they can be Memory inefficient because because these 500 elements are allocated in memory as soon as this array is created so that means that if you don't fill in any of the 500 positions in this array they just stay empty and that memory space is being unused for no real reason at all now I would say that the other the other thing about static data structures is that it can be iterated through using for Loops in fact with static data structures one advantage we have over the other type of data structure which we'll go over is the fact that static data structures inside data structures you can go forward you can go backwards using Loops but also you can access individual elements um you can access them directly like this versus as we see next in Dynamic data structures we're not able to do that so just being able to move through the data structure in multiple directions and directly to elements is a significant advantage of static data structures now Dynamic data structures are probably nearly all of the data structures that you will use in topic five or rather I mean it kind of depends with uh with some of them but generally collections which you should have learned about in the SL curriculum are examples of dynamic data structures so there's no need to predetermine the number of elements any number of elements can exist at any time we can add elements to Dynamic data structures unlike with arrays um we don't need to pre-allocate uh specific we don't need to pre-allocate the size or memory addresses for dynamic data structures so basically with the dynamic data structure each element exists at a particular memory address which is also true for um for static data structures but for static data structures we tend to have all of our memory located together like this so all of this so basically continuous memory addresses so if you have a memory address of zero one two three four five six seven we're looking at a static data structure now with Dynamic data structures we also have particular memory addresses but these don't have to be located next to each other unlike in static data structures and each one of these is called a node and the node has a pointer to the next element in the data structure which could actually be anywhere else in the ram so for example if we have a if we have a node of a dynamic data structure with some information in position zero in the ram this being position zero then we might have what's called a pointer to another position in the ram maybe right here and there will be some information there as well what that means is that when we're iterating through a dynamic data structure we're going we're going to go to zero then next we have a pointer to four so we're going to go to four and then we're going to go wherever else that um that particular node at Four Points to this means that we're more memory efficient than static data structures because we can basically put memory anywhere and we're not pre-allocating a certain amount of memory next to each other so we can have memory for the same data structure stored all over our Ram where like basically where we want and there's not really going to be any just empty spaces that are sitting there in this data structure now with Dynamic data structures we can iterate through using while loops again one of the differences from static data structures is that we can only move forward in a dynamic data structure we can't move backwards and we can't access specific elements so if we have a collection called like nums called nums we cannot just go access nums 53. like we would in Array this is not possible additionally right off the bat we don't necessarily know how many elements are going to be in that collection so we can iterate through the whole collection have a counter and figure it out but we don't have a predetermined we don't have a predetermined number of elements so you kind of have to iterate and find out for ourselves there's no dot length like there might be in a static data structure that doesn't exist here so that's the big difference between Dynamic data structures and static data structures I would say that all the data structures we're going to go through in topic five are going to be dynamic data structures there's some caveats to that but by and large that's the way that it works here is just a table that basically illustrates what we just talked about um I think the only thing missing from this table is the fact that with static versus Dynamic with static we can move forward and backwards with Dynamic you can only move forwards and with static we can also access uh specific indices or specific elements in our structure in our data structure so we can just say specific elements versus in a dynamic data structure we can't do that we can iterate through our data structure and try to like find that particular element but we can't go directly to a specific element and again an example of a set data structure is an array and an example of a dynamic data structure is going to be a um a collection among many others that we'll figure find out about today so what we're going to deal with now is a very static data data structure which is 2D arrays now the typical 1D arrays that we're used to look something like this so we've got an array and we've got just you know a couple of elements like this 2D arrays are essentially the same thing except instead of having elements that are integers or or Floats or strings we have an array of arrays so what we're going to have now is we're going to have something like this or okay that's let's say it's zero two three that is what a 2d array looks like now 2D arrays are as we said arrays of arrays and if we're representing a 2d array we're going to represent it in this format now I want to clarify by saying that 2D arrays are typically uh displayed as a as a grid and in general they are used to they are used to display data that can be represented in two Dimensions so this is a 2d array but on the IB exam and in general you're most likely to see a 2d array like this so 0 2 3 five four six uh seven eight nine so that's something you're most likely to see now if we want to go to specific elements on a 2d array um we would look we would write something like this so let's say this array is equal to nums or the name of this array is nums we wanted to go to nums or if we were to go to nums 0 2 sorry that's not the way you'd write it technically I'm writing it like a coordinate because it's really in 2D this is the way it would actually look in pseudocode if we were to go to nums02 that would be row zero uh column two so that means we'll be right here if you were to go to if you were to go to nums uh uh one two that would be Row one uh column two so that would be so this is going to be Row one zero one two and then column two which would be this element right here so that's how we can actually navigate uh through a 2d array um now as I said before they're used to display data points with two dimensions and often grids and that's the way you're going to see them you're going to be working with them the IB exam and just in general in real life whenever you do use 2D arrays now what we're going to do now is we're going to shift over to visual studio and do a little bit of pseudocode coding um and we're going to complete some basic tasks involving 2D arrays if you've watched my part one video it's very it's a very similar concept to What was seen in that video where these are kind of the basic things you should know how to do um this may not be like exactly like on the IB exam you're going to have tasks or some variation of this but if you understand how these basic tasks function you should be able to tackle those so let's go write some code so let's start with identifying specific positions in 2D arrays as part of this particular task what we're going to do is we're actually just going to create a 2d array we'll call it grades so these might this might represent grades for different students index 0 could be one student index one could be another student uh index two could be another student and so forth so let's assume you have three students and we have three grades for each of them that are being represented in this particular 2D array oh man let's give someone some really bad grades okay not that it makes difference but anyways so notice these are separated by a comma again it's like a regular array except your elements are arrays themselves now if we wanted to for example output this entire row we could actually just do grades we could do output grades zero however if we wanted to Output the last value or actually so this one would be grade 0 right here if we wanted to Output this one right here that'd be grades one and that would allow us to Output the entire row now within this row if we wanted to Output let's say 94 then we would have grades one two if we wanted to Output 93 it'd be 1 1 we wanted to Output 92 would be 1 0 and so forth so this is basically how we can represent and how we can access individual values in a 2d array using pseudocode now our next task is to iterate through 2D arrays so basically what we're going to use is we're going to use two for Loops we're going to have one index that will iterate through each row and then we'll and then we'll have a another index that will iterate through individual values in the row so if you have we're going to do loop I from zero to grades.length minus one and then we're going to do Loop J from 0 to grades.length her grades I dot length minus one so what that means is that we're going to go for we're going to go 0 1 2 and then each time so for example when I equals 0 we're going to go 0 1 2. now actually all of these don't have to be the same length so we could have something like this we could have more grades for one um or we could have fewer grades for another but regardless of what that is the top Loop is going to go to each one of these rows and then each time we go to an individual Row the bottom row is going to get the length of that particular row through grades I um dot length and then we're going to go all the way to the end of that so basically we need to know is that we're going to use nested Loops the top Loop allows us to go to each row or each individual array element and then the second Loop allows us to iterate through that individual array element so our task was basically to iterate through 2D arrays and we're just going to assume that means we want to Output every value so if we do that what we can do is we can say output I we can say output grades i j uh and loop and then end Loop okay so that's how we iterate through a 2d array and just output all the contents you're going to always use a nested Loop so next how do we iterate through just rows into the arrays we kind of just went over that if we just want to print out rows like if you just want to print out this row and then this Row in this row so basically we wanted to print out three arrays we would just do loop I from zero to grade stop length for grades.length minus one and then we just do output grades I and what that basically do is that would just print out uh this and then this and then this just in sequence just printing out each individual row um now this is actually simpler than this one but it's good to know because maybe some situations in which you need to do something different with each row or you need to be able to analyze each individual array element in a different way um it's just something that should be considered now iterating through columns in 2D arrays that's actually kind of a misnomer because iterating through columns means basically this right basically we're just outputting every single element um we're going to print out this one and print out 78 like for example this piece of code we just went over would print 78 uh 89 89 94 uh 92 31. I would say let's say for example you wanted to Output only everything in the first element like so let's say we had these all the same it was like a perfect grid and you just wanted to Output everything in just position zero right here then what we would do is we would just do loop I from 0 to grades dot length minus one and then we would just output um grades I zero because all that means is that we're going to go to every single one of these individual array elements and just print out whatever is a position zero and that's just printing out everything in one column now the last thing I'm going to do is Count values in 2D arrays and this kind of gets us to um like calculating averages maybe calculating the minimum and maximum um I'm not going to go through all the minimum maximum stuff because like literally the same rules apply as a 1D array it's just you're going to use a nested Loop well I think it's worth going through how to count and just you know some of these basic operations that goes beyond iterating [Music] oh by the way right here I just want to make sure that before I move on I do end Loop I know I leave that out sometimes and that's not intentional it's just that like I'm so used to coding in Python where we don't do stuff like this that sometimes even for me it's hard to adapt so I'm going to go ahead and erase all this and what we're going to do is we're just going to count how many elements are in grades so this is basically a review we're going to say loop I from zero to grades.length minus one and then we're going to have Loop J from 0 to grades dot length I [Music] minus 1 iterating through each individual array element and we should just have a count variable up here equals zero I spelled length wrong right there and then we're just gonna have count um I guess we could even let's say we wanted to calculate the average we could have a sum right here right um and we could have uh sum equals sum Plus grades i j and then we're going to have count equals count plus one every time we iterate through an individual element and we're going to end the loop here and the loop here and then we might just do some average equals sum slash count and then output average so again I mean these are this is really the this is really the the main piece you need to know right here the rest function is pretty similar to how it would if we were just using a 2d array we could say the same thing if you were calculating a maximum or minimum you could just say you know Max equals zero if if grades uh or Max equals rather I'd probably say the first value in zero in grades so you'd say Max equals grades uh zero zero rather so have Max be equal to the first value in our 2D array and then we would say if grades uh I uh J is greater than Max then Max is going to become water whatever element that's at so you can say Max equals grades I uh J and then we're going to have and if and we'll just output Max at that point if we wanted to keep track of the indices of or what position that maximum is at you could say uh pose I would actually say pose row equals uh zero and pose column equals zero and then we would just say pose row equals I and pose call equals J and that'll give us the particular position of that maximum wherever it is in the 2D array so this is how you can complete some basic tasks of 2D arrays in reality it's not that difficult particularly if you've got a good foundation in how to work with one erase so right here what we've got is a an IB problem that involves 2D arrays and it starts out with just a pro a basic problem with methods um so right here we have a it says uh envelope a and we've got two parts a and it says assume a equals three and b equals five so you've got two parameters for this method called swap and set the value of a and b after the execution of swap a b so we're going to have temp equals three and then b equals three and that is so temp is going to be equal to three and B ends up being equal to three as well and then again a is equal this is just really weird um so the values of A and B would actually just both be three and accordingly like this isn't a trick it's just how the algorithm used in method swap would be would need to be modified to successfully exchange the values of variables A and B um so I'm just going to go ahead and write what the function would look like if we had a swap uh A and B and we wanted to exchange the values so assuming like we had we just had we'll just say like if we had a equals three and b equals five we would just want those values to be exchanged so or really like I guess the way this would work out would just be swap three five right so in order for that to be possible in order to fix any error right here what we might want to do instead is just have uh temp equals a uh a equals B and then b equals 10. and then we can just have n Swap and then both of those values would be swapped so that should generally be your answer for these two questions um and that's basically what we have right here in the mark scheme now right here we've got a method swap rows that swaps the elements of two rows so row K and row L in the two-dimensional array mat so for example right here we have Row one and we have row four and we can swap rows uh so we have one parameter as the actual array which in this case is matte and we can swap rows one and four so now array one has what is in Array four but one so basically the array at index one is the same as what was at index four and vice versa so here's this use pseudocode to construct an algorithm for the method swap rows so I'm going to go ahead and just say swap rows a or k is kind of going to be our first row okay that's what's going like and L is going to be the set okay so let's go ahead and select actually construct a little a little array right so say we've got that um so what we want to do basically and let's just say math equals that now this is just an example so we can work with it pretty easily here in the code so basically the idea is we'd want if we had if we put 0 and 2 it's okay if we had uh Matt we had swap row um that uh zero and then two you could actually just exchange those uh these different rows um so I would say like the way that I would do this is I'd probably create a new I guess one way we could do it we could actually just create a new array um or what we could do so if you go right here it says use pseudocode to construct an algorithm for the method swap rows um in this question actually there are a couple of ways to do it I actually assume that you could use the swap function but even even so if not what we can do is we can just go through the index for each of these and then we can just kind of swap those rows so basically what that means is that what we're going to do is we're going to say um we're going to say four uh loop from 0 to let's say Matt K dot length Okay these should all have generally you're gonna have when you have two D arrays in the IB they're all going to have all the individual array elements around the same length but whatever so that means we're going to go from 0 1 2. okay um and basically what I want to do is I want to say for each of those we're going to have temp equals Matt k or I'm going to say loop I rather from zero to Mac a so we're going to say temp equals mat uh k I um and then we'll say Matt J Matt well yeah so Matt l uh Matt l i equals the 10. that's what we want to do she will say we've got temp right there actually I think I want to say Matt k i equals Matt l i and then once you transferred that over you can say matte l i equals temp so that's actually probably how we could do that um so basically we're doing is we're iterating through this this one right here and for each element we are swapping whatever is in uh row row K with whatever is in row L this way and we're going to the first element here swapping them putting the second element here swapping them going in the third element here and then just swapping them and I'm pretty sure that's what yeah that's basically what the um boxing says so it's a good example of how to work with 2D arrays actually in this one we only need to use one Loop and we were just kind of working with one row and then swapping that with another row okay what we're going to do next is we're going to talk briefly about recursion so recursion is basically like this example right here when we have we write a function and we call the function itself inside the function so right here this is part of the function but we're making a function called right here so that's basically what recursion is um now with recursion like generally we're using recursion situations where the next result of an operation depends on the current result some good examples include the Fibonacci sequence or a factorial function factorial function looks like this so we might have four factorial it goes four times three times two times one that means we're going to multiply two times one and then 3 times 2 equals six and then four times the result of that which would give us 24. that's an example of when we would use recursion now we have two terms right here we have a base case we have a recursive step if you look right here this right here is going to be our base case and this right here is going to be our uh recursive step to visual base case is what it takes for the whole recursive process to end so right here for example if we input 3 right here okay we're going to have return 3 times fact two okay um and then we're going to put 2 in here right for this part right here so then we're going to have 2 we're going to check is 2 equal to one no so we're going to return 2 times fact 1. I will say Fact one okay and now we've got Fact one we're going to put one in here and we're going to say if n equals one then return n which means that we're actually going to return one this time because our input is just one so Fact one is one so this is going to give us 2 right here two times one so that means that then this return statement corresponds to Fact Two which means Fact Two is just going to be equal to two fact 3 ultimately X access to return three times Fact Two so Fact Two is going to be 2 then our output is going to be 6. now notice we stopped we stopped right here when we actually had a whole number instead of another return statement with our function in it let me stop there because n was equal to one now that's why n can be considered our base case that's the lowest parameter that we go down to and we're just going to return a value rather than another function call and then work our way back up from there to what we actually want which was fact three or three times fact2 which is equals six so that's like this is like a basic example of recursion now on the IB exam there well the thing is like I what I want to do right here is I want to cover like the very basic uh tasks that you need to do for recursion now on the IB exam you may see recursive functions and generally you're only going to have to either understand how they work or calculate the output of a recursive function now there are situations in which um you may see recursive code but you're never going to have to actually write a recursive solution like you'll there may be questions that say you can use a cursion but that doesn't mean you have to moreover to actually teach how to like detect and write recursion would be a much longer tutorial than this so I'm just going to focus on like really really like basically what you're going to see on the IB and we're going to look at some recursion related IB functions okay so right here it says consider the following recursive algorithm fun X9 where X and N are two integers the return statement gives the value that the algorithm generates determine how many times multiplication is performed from this algorithm as executed so in this whole function right here we are just performing uh multiplication right here so that means however many times we hit this line of code uh that's gonna be the number of times in multiplications is performed so let's say for example um I actually want to start so I mean the next question is going to be fun23 and we need to find the value so we can use that to kind of like work with this and see how many times we have to do multiplication so if we start if we have fun two three um the first time we're going to return uh two times fun two two then we're going to return uh two times uh fun two one because we had a parameter of 2 then and then we're going to return two times fun uh two zero [Music] um and that's we're going to do that we're just going to stop right there because we're going to have a parameter of 0 for n and right here we can see if n is less than or equal to zero we just return one so that means that if we have right here so right here we had an N of three okay and we saw that every time we were just subtracting one from that value until we got to zero so that means that basically we were we had two one zero so similarly if we had a n of four I mean so each one of these times we had to do multiplication we should do multiplication three times so looking at the sequence that also means if we had a value um if we had um fun x 4 or fun24 we would have had to multiply four times um if he had fun to fight we ever had to multiply five times so just by working this out and looking at this value right here we can tell that the number of times the multiplication is performed is going to be n now in kind of gaming this problem out or kind of tracing this problem actually what we can also what can also do is we can determine the value of fund two three now right here we know that if the pre if our n is zero then we're going to return one right here so that means we're gonna have two times one equals two so that means that fun two one for which this was the return statement is going to be equal to 2. so that means that in this return statement right here uh we're going to have fun two one is two so that means it's fun to two or sorry I should put that right there fun two one it's probably not that clear but that means that fun uh two two is going to equal to um four because you got 2 times 2 right here and then we still have this return statement right here so we're going to do 2 times fund 2 2 so that means that fun uh two three is going to equal eight okay so the value of fun23 is just eight [Music] now let's take the purpose of this recursive algorithm so notice how you went 2 4 8 right um if we had like fun uh three two for example okay that would have been 3 times that would have been three times one three times two or three times three and then three times nine if we had four uh three that would have been like four times one four times two and then four times three so the purpose of this algorithm is really to calculate X of n to calculate an exponential uh to calculate x to the power of n so some sort of exponential value when there are two integers um now that we've kind of now you have a basic idea what recursion is we've seen some problems we're going to look at some of the pros and cons of recursion so the pro recursion is like the code is cleaner and more elegant which it's just a simpler way to solve problems uh complex tasks can be broken down into your repetitive series of similar sub problems basically it's very um it's just a lot simpler to um visualize or to work with when we're trying to solve certain types of problems that have a lot of other sub problems that need to be solved and sequence generation is much easier than with nested Loops so it's easier for estimate calculations like for example the factorial that we looked at the advantages is that recursions is hard sometimes recursive logic can be difficult to follow um additionally it's usually more efficient it's usually more inefficient because every time you make a function call we're taking up memory so that can add up really quickly and partly because recursive logic is hard to follow it can be harder to debug recursive functions now again I want to emphasize that in order for you to like fully understand recursion you need to write some recursive code and solve some recursive problems this is just kind of a basic review of what you'll see in the IB that being said you don't really need to learn how to write recursive code like it might help you understand it but you don't really need to learn how to um like solve problems using recursion um because any any problems in the IB will give you the option of either using recursion or iteration to solve the problem so understanding how recursion works is kind of the most basic thing you need to do on the IB and frankly as I said before if I have to completely reteach recursion that would probably take a lot longer than you'd want to watch this video for anyways that's the end of part one um part two we're going to cover uh Stacks and stacks and cues binary trees and linked lists um if you if you are currently preparing for the IB acceler HL exam please be sure to check out the link in the description which contains links to study guides for both SL and HL paper one as well as HL paper 3 with some sample practice questions and paper and answers moreover if you found value in this video please remember to like and uh subscribe to the channel have a nice day