[ Silence ] >> Alright, hello every body. Welcome to Walkthrough 3. This week's Pset, among my favorites, implementing the game of Fifteen although I still can't solve the Fifteen puzzle. So, today's music was Kesha, always entertaining and so this is the agenda for today. So our problem set this week is kinda split up into two parts. There's that part Find and there's that other folder 15 and so here is basically a breakdown of all the things that you need to do with our help. So, first thing you need to do is look at this generate file and your task for this part is pretty simple where you're given a C file, it already works, we promise, and all you need to do is comment it. So, if we are to comment it you'd kinda need to understand how it works, so let's take a look at what's going on. So, you have this generate file. Now when you run generate it takes two arguments, N and this optional argument S, so and when you supplied an N which it needs to have, that tells generate how many random numbers that you want it to generate, just gonna spit them out one per line. Now, this C value is used in what's called a pseudo-random number generator. So, because computers can't actually generate random numbers, we have this pseudo-random so that it appears random but it's not actually random. So what do I mean by that? So, using this built-in function called rand, this was again written by someone else and given to us for free, and rand can openly take a seed value or kind of a starting value. That's not gonna be the first value that's generated but if you start everything off at the same seed, you're gonna get back the same sequence of random numbers. So, let's just take a look at what I mean by that. So, I'm inside my Pset 3 folder. I should note before you start the Pset we're actually giving you some code this time, so in order to get that code as the problem set mentions, you wanna open up a terminal in your appliance, go into your home directory and execute this guy, git clone and then this long URL. What this is gonna do is it's going to download some of the code that we've written from that server and it's just gonna put it inside your home directory, so you're all set up and good to go. And so we'll see more about git later in the semester but basically what this does is it allows you to keep track of different versions of your files. And so when we've been using submit50 all semester we've actually been using this thing called git and so every time you're on submit50, we have a different version of your submission on our servers, of course I'm gonna grade the latest one but what that allows you to do is kinda make backups and let's say, oh man, I messed up, I really wish I could go back to 10 minutes ago. We'll with git you can and we'll learn how to do that later in the semester. So, right now all you need to know is just run this incantation and it's gonna download all the files you need to start your Pset. So, back to generate, so once I run that git clone, I have two folders, Fifteen and Find, so let's go into Find and now we have this generate.c that I mentioned so if you say make generate, it's gonna create this generate [inaudible] and if I say generate, I just want three random numbers, so there we go. So, there's three random numbers or so it appears. I'll run it again and I get three different random numbers. So, you notice here I didn't specify a seed and so you kinda have to figure out by reading generate.c, what that's actually doing. So, now if I say generate 3-1, I'm specifying a seed value of 1 so I get these three random numbers. So, now let's run it again with the same seed, I got these three random numbers which just maybe coincidentally they're the same three, let's try again, it's probably not so coincidental. So, this seed thing determines what you're gonna get out of your random number sequence so random but not really random, so why is this useful? So, let's say that you're running your sorting algorithm and it works sometimes and not some of the other times. So let's say, okay, these random numbers, I really wish I could generate this sequence of 1024 random numbers again. Well, you can if just specify the same seed. So, that's super helpful that it can do that. So, also super helpful are these little command line tricks. So, if you wanna take the output of some program and instead of displaying it, out in the terminal you wanna write it to some file, you can just use this right arrow or the greater than operator. So, if I have the name of my program like generate and then the greater than and then where I wanna write it to, so this is probably just gonna be a text file. So, if I do that, I can say the same thing, generate 3-1 but now I wanna pipe it to numbers.txt. So, I ran it and you know instead, I didn't get any random numbers, that's because we no longer output it to the terminal but if we open up this file, numbers.txt, there are my three random numbers. So, similarly, if you wanna go the other way around, you're gonna use the less than operator. So, this says, okay, I have some file and inside that file are lines. I want to send each of those lines as input to this program, so finally we have the pipe. And the pipe is really just a combination of these two things. So if I have a program, a pipe and then another program, so let's say generate a pipe and then I call my other executable find, what that's gonna do is send all the output of program 1, it's gonna send it as the input to program 2. So, there's a nice little trick where you can generate a thousand numbers and then run find over those 1000 numbers using this pipe. I mentioned how to do that in the Pset, just generate so then we're gonna generate other numbers and then we're gonna send all those to instead of a file, the input of another program which is gonna run once that's all done. So, the Pset explains all this in a little more detail but any questions on this cool little hacky Unix trick we're doing here? Yup. >> How are all these seeds chosen if not specified? >> So, how are these seeds chosen if you don't specify, so that's where you have to regenerate that C and find out. So, if we just open up generate.c, you'll see we have to do a comment me, comment me, comment me, comment me, comment me, so here we have a mention of RT equals 3 or RT not being equal to 3 and it's doing these two different things. And so you need to explain in this comment what's actually going on here. So, you have one, two, three, four things that you need to comment inside of generate, just to prove to us that you know what's going on. So, questions on generate? Okay, cool. No code, you actually have to write. So, there, here are those examples, that is examples we just looked at if you want to instead of write out to the terminal, write to a file or take that file and read it in somewhere else or combine the two, yeah? [ Inaudible Remark ] >> Oh sure, so how to open that file in G edit, sure. So, if we go into G edit, we noticed that we piped it to this file, numbers.txt, so I'm in my Pset 3 Find, this is after I ran my git clone and downloaded all the files. You'll see I created this numbers.txt file. So, if I remove it, let's say remove it, so now it's gone, that RM for remove. And now let's do generate 3-1 into numbers.txt, so this file doesn't exist anymore but after I pipe to it, I now have this numbers.txt file, and now if I wanna look at it, I can just go into G edit, open, and now I have this numbers.txt right here and those are the three random numbers I generated. Other questions? Okay, so also kind of not necessarily the problem set but we've seen these, we've seen these for the first time, are these things called Makefiles. So, in Pset 1 and 2 you noticed that you type things like, make scissor or make pennies and we just kinda took for granted what Make was actually doing. And so, what this program Make does is it's gonna look for this file named Makefile with the capital M and it has to be named that, that's what Make is gonna look for and inside of this Makefile, you're gonna specify what happens when you make something. So, here's an example from the Pset kind of condensed so it fits in the slide. So you see find colon, then a list of files and then some line of what's going to happen. So, when I say Make Find, this is the command that's gonna get executed, this GCC, GDB whatever. So, after the find, there's a colon and after that colon is a list of all the files that I'm going to use in this command down here. So, if the file doesn't exist or something like that Make can yell at you and say, you need this file before you can do anything with it. So, really frequently you're gonna--yup. >> If you make your own Makefile, can you define your own functions in it? >> So, if you make your own Makefile, can you define your own function? Sure, so just be careful when editing Makefiles because this here needs to be a tab and get it is gonna default two spaces and it's not gonna work if there's spaces so just make sure that's a tab, if you wanna play around with it. So, you definitely don't have to for this Pset, it's good to go as is but if you wanna learn a little bit how Makefiles work, yeah, you're definitely welcome to have your own different targets. So, Make Find, this is gonna compel find and we also have things like Make Clean, so this isn't gonna compile something, it's just gonna execute some other command, in this case it's gonna execute anything that's not dot C file or dot H file. So, anything you compile there or any time you save files in it, it's just gonna get rid of those, you have a clean directory again. So, yes, you're definitely free to write your own Makefiles, just be careful about that whole tabs and spaces thing and just to be clear, you don't need to write your own Makefile, it's done for you this time but it's good to learn how those things work. So questions on Makefiles or Make? Alright, so let's get into the actual find problem set. So there are two things we need to do here, we need to implement sorting and we need to implement searching. So, we have this file find.c and it's written for us, so what this file is gonna do is it's gonna prompt the user for a bunch of numbers and they're going to fill a haystack, so using that clever finding a needle in a haystack metaphor, which is actually like not just us. It's a really common programming thing beyond me. >> So while we're prompting the user for numbers we need to eventually tell us to stop prompting, so to do that we're gonna hit Control D on our keyboard. What that does is it's gonna send a special character called the end of file which is something that's obviously not a number and find is gonna say okay, if you type Control D I'm just gonna stop asking you and the haystack is full. So after you've entered all the numbers that compose your haystack find.c is gonna use these two functions to find in helpers.c to find it. So let's take a look at find.c so we can see what's going on. So up here we have a nice, well, a commenting book that tells us what's going on including some social files. You also notice we're including helpers.h, so you notice this is not a library file that someone else has written but helpers.h is something that we have written and it's included in that same directory. So now we just have a constant for--well, you know, the maximum number of pieces of hay you can implement. This const in front of int just means that this is a constant. It means you can't change it. So if you try to change it then C is gonna yell at you and not like you. So now we're into our main so first thing, we just wanna do a quick sanity check, make sure that we've supplied a number that we need to find, if not then we're just gonna quit right away. We're not gonna ask him for it or anything and so now just like in Pset 1 we use this a2i [phonetic] and does anyone remember what a2i does? Yeah. [ Inaudible Remark ] >> Exactly. So it converts a string to an integer so when I say something like find 13 that 13 is actually a string and we want to get the integer value of that. So saying a2i just says okay, take the string, make it an int and so now I have the integer value of what I'm searching for. So now you can see that we're just iterating until we reach this maximum bound, this hay max that we specified and until we don't have that many we're asking the user for a number and if they give us a number then we're just putting it as the next space in the haystack. So this for loop just fills up the haystack until we hit Control D and now we're doing two things, the sort and search. So these are the two functions that are defined in helpers.c. So sort is just kinda take this array, it's gonna put it in ascending order and then search is gonna see if the number we specified, remember that needle came from the command line argument after we call a2i on it and the haystack is just the array that we're searching. So if this returns true that means that we found it and if it returns false we didn't. Question. [ Inaudible Remark ] >> Oh, that's a good question. So why I'm including helpers.c but not helpers.h? So actually, if we open up our Makefile, so right here, capital M, Makefile, you'll see this. So GCC blah, blah, blah, so this O just says I want the resulting file to be called Find and now we have not just one C file but two C files, so find.c and helpers.c so when Make compiles this it's gonna look in both of those files to form the executable. So now why do we include the header file and not the C file? So if we open up the header file you'll see all this includes are two function prototypes. You know remember what these do is this just tells the compiler that these functions exist. Don't worry, they're defined somewhere. So as in compiling my code if I run into one of these functions as the compiler says okay, no worries, this exists somewhere and it exists in helpers.c which we are also including because we put it here. So in short it's kind of a C convention to have all this prototypes and variables defined in dot H files so that the compiler knows they exist but actually define what they do in C files. So when you include the H files that's gonna tell the compiler everything is good to go and if you include the C file we're actually compiling, so running that GCC, that's gonna make sure that the functions that you define are included in the resulting executable. So we'll see more about how that process works in future weeks but any questions on a high level? Yeah. [ Inaudible Remark ] >> So then a good question, so why is that helpers.h surrounded in quotes instead of curly brackets. So if we go back into helpers, yeah, so we have two things. So the cs50.h, this is kind of a system library, right. It's something that someone else wrote for us and they put it somewhere on our computer and GCC knows where to look. But this helpers.h actually exists in the same directory as the rest of our files. So if I do an LS there's helpers.h so that quote means I want you to look right here for this file or some other places I've defined and those brackets mean that this is some system file and I want you to go look for all the secret system files stored. So that's the difference there. Other questions on how we're compiling? Alright. So now inside of helpers we have these two functions. Sort is gonna take two arguments. The first is an array that you actually want to sort. And the second argument is going to be the size of that array. So you all remember in C there's no way of simply determining how big an array is. So instead we need to explicitly pass around the size of the array so we don't try to go too far in segfault or not consider all the elements. So in both of these functions you're gonna be passing the size explicitly so you don't have to do anything fancy to try to figure out how long the array is you just know because it's an argument. So similarly with search, it's gonna take an array, it's gonna take something to look for and it's also gonna need the size of the array. So the sort is actually a void, it doesn't return anything. Instead this array is gonna be sorted in place. So after the function finishes, the argument that was passed to it is probably gonna be different and this was already sorted whereas search on the other hand does return something. It's gonna return true if it's found and false if it's not. So if we open up helpers.c we'll see that all we have is this, so sort it's not gonna do anything. Okay, we have a little note here. You wanna implement it other than [inaudible] sort which we'll take a look at. Search on the other hand has something here and what this is, is basically a linear search so this is gonna look at every single element in the array and try to find the one you're looking for. So this isn't what we want you to do because this is super slow. Instead we're gonna ask you to take--rip this out and implement your own binary search. So let's take a look at both of these things. So again, we're not going to try to return an array from sort, we're just going to change the one that was passed in and that's possible because arrays are passed by reference in C and so we're gonna see more about this in lecture shortly but their basic difference between passing something like an integer and passing an array is that when you pass an integer C is basically gonna make a copy of that integer and pass it to the function. So it's not gonna be changed once the function is finished. Within array on the other hand it's not gonna make a copy. It's just gonna say here's the array if you wanna change it, go ahead. So again, we'll see more about that in lecture but just know that these arrays, when you pass an array through a function, it's treated specially and that if you change it in the function it's gonna be changed from where you called the function. So let's take a look at two different sorting algorithms. So the first is called bubble sort, so this is the simpler one. So what this says is I wanna keep going through every element in this list and if two elements are in the wrong order I want to switch them. So this has the effect of elements kinda bubbling over to their correct location because they're gonna get a move one more with each iteration and kinda make their way slowly to where they need to be. So we know when to stop once no elements have been swapped. So if we have the condition that every time elements are out of place we make a swap. If we know that we haven't made a swap that must mean that every element is in place. So here's some pseudo-code for that. So we have some while loop and while the elements have been swapped you wanna say okay, at this iteration we haven't swapped anything yet so now we just wanna go through everything in the array and if the current element is bigger than the element next to it then that means that these two elements must be out of order because you wanna start with low elements and have them to order from low to high. So if anything is higher than the thing to the right of it they're not in order. So we can just swap them and now we want to remember that okay, we did swap elements this time so you probably wanna check over it again because we're not guaranteed that we're sorted yet. So let's take a look t how this is gonna run. So let's say I have this list 50164. So I'm gonna start at the beginning of the list, I'm gonna look at 5. I'm also gonna look at the element that's next to 5. In this case it's a 0. So 5 is greater than 0 so I need to switch these. So now I have 05164. So now I'm gonna look at the 5 and the 1, again they're out of order so I switch them. Now we have a 5 and a 6. In this case we don't need to do anything because the 5 is less than the 6 we don't need to swap. However, once we get to 6, 4 we again do need to swap. So now we have 01546. So now we're gonna go through it again. We need to switch no, no, yes, now we do need to switch and again 5, 6, we're good to go and that means that our list is sorted. So any questions on how bubble sort works? [ Inaudible Remark ] >> Yup. [ Inaudible Remark ] >> Sure. So if we go back to the pseudo-code so how do we make sure that we go--that looks not cool. So how do we make sure that we go through this list? So notice that my for loop, I'm maintaining this index, right? So after every iteration of the for loop, I'm gonna update this value of I. And this case this value of I is effectively the left element. So after everything continues, I'm gonna have a new left element. So if I have new left element and I add one to it that means my element is different. So that means even if we swap, we're still gonna move I forward and compare it to the next one. Other questions on bubble sort? Yeah? >> Once I'd make the final swap, does it need to go back over and make sure everything is right or like you just stop there once it does that last little switch? You won't have to like go one more over and make sure that's-- >> Right. So I kind of just, you know, instead of copying-pasting 5 slides, I just kind of [inaudible] there. So, af--so yes. So after we just made this 4, 5 swap. At this point the algorithm doesn't know that it's done. Because looking at our pseudo-code strictly, we said, did we make a swap? Yes. If we did make a swap, we need to go over again. So now we're gonna go over again and at no point do we make a swap so now we break the condition of our while loop because we did not make a swap which means that we're done. So yes, so we're gonna need to make sure we go through every time. Yup? [ Inaudible Remark ] >> So do we have two loops? So yes, so they don't necessarily have to be a while and a for or a for then a while, they could be whatever you want. But bubble sort has a run time of O N squared. So that means that there's gonna be a for loop inside of a for loop. So for every single element, I need to look at every single element. And that's where that N squared comes in instead of N or log N. So we definitely need two loops because we need to compare every element by at least that many times. Question? [ Inaudible Remark ] >> So why is it I equals zero to N minus 2? So this, you know, could just be indexing to pseudo-code but we wanna make sure that we don't ever use the last element as our left, right? Because if we're at the end of the array, and we look one element ahead, we're now outside of the array and we're in trouble. So one way of solving that is to say, okay, I don't wanna--I wanna make sure that I stop at the second to last element and that's my left. They don't necessarily have to look right, you could also say, okay, that I is gonna be the element on the right. Now I'm gonna look one behind me. And if those are out of order then you can swap them. At this case you'd wanna start I instead of at 0 at 1 then you'd wanna iterate until the end of the list instead of the second to last element. So yes, so be really careful here, if you segfault, that probably means that you're either looking too far to the right or looking too far to the left. Yeah. [ Inaudible Remark ] >> So is there a command for swapping? No. So this is a function that you have to write yourself. So you may have seen that in lecture, how we can swap two numbers and how we can't actually swap two numbers, but so this isn't something that is written for you. But basically what you just need to do is you need to say I have some value here, I have some value here, I wanna store one temporarily, swap it, and then put the temporary variable back into the value that I swapped. So there's definitely an example in lecture of how we can swap something in array, in an array. But basically we're gonna have some temporary variable, put something there for a minute, swap the value and then put it back. Other questions on bubble? Yeah. [ Inaudible Remark ] >> So there could--yes, so there could be different variants on bubble sort. So this is just kind of the most basic one, just if and then keep going to the list and if I know the list is wrong, I'm just gonna swap things. So yes, so you're definitely welcome to implement, you know, a variation that you might have seen elsewhere. But this is the most basic version. Yeah. [ Inaudible Remark ] >> So why is it N minus 2? So as I mentioned before, we just wanna make sure we don't go outside of the array. So if we're at the last element and we try to go one more, that means that I'm gonna index outside of the array, yeah. So remember that array start at 0. So if I have an array of length 5, that means my last element is at index 4, not 5. Easy mistake to make. Other questions? Okay, so that's bubble sort. That looks really cool. So now for our selection sort. So this is a little more complicated than bubble sort, and most of the time it's also gonna be faster. So the basic idea behind selection sort is you're going to build the sorted list one element at a time. So at first you're gonna start at the beginning of the list because we're gonna build the list from left to right. So now we wanna find out what element should be at the beginning of the list. And that element has to be the smallest element because we know that the first element has to be the smallest one. So we're gonna look through the list and we're gonna find that smallest element. And we're gonna just switch it with the element that's already there in the first spot. So we're gonna start at the beginning, find the smallest element and put it at the beginning. Now we know that the element in the first position is correct because it's the smallest so it has to start off the sorted array. So now we can move on to the next element which might be wrong. And again, we're gonna find the smallest thing that's left in the array. Obviously, we don't want the absolute smallest because we know that that's already in the right place and we don't wanna touch it. So we wanna find inside of the unsorted part of the array the smallest element and we're gonna swap them again. So we're just gonna keep going until every element has been swapped with what is the minimum element at the time and that means we're gonna have a sorted list at the end. So let's just take a look at an example and then look at the code. So here's my list again, 50164. So this blue is gonna be where I am in my list. So what the element I'm looking to swap this. Now the minimum of this list is going to be 0. So that means I need to swap this 0 and this 5. So after I do that, we know that this 0 is in the correct place because it's the minimum. So we don't--we need, we can just forget that that 0 exist. So now we're looking at the 5 and we wanna swap something into where the 5 is. So again, we're gonna find the minimum, not counting the 0 because it's done, we can forget about it, so the new minimum is now 1. So we're gonna swap the 5 and the 1 and now we know that these first 2 elements are in the correct position. So now you move it over again and this 5 just keeps getting kicked out. So the new minimum in these last 3 elements is the 4. So we swap the 5 and the 4, now we have the 6, we can swap that with the 5 and we know that we're done because once you reach the last element, there is nowhere else to look, so that must mean that it's also in the right location. So the pseudo-code for this, although it looks cool. So the pseudo-code for this, again we're O N squared, so that means, for every element, we need to look at every element at least once. So we're gonna have a loop within a loop. So we're gonna start off at the absolute left of our list because we're moving basically from left to right and swapping elements as we move to the right. So that means that our minimum value is gonna start off at the left. So now we need to find anything that's smaller than that minimum value. So we're gonna start at that location and find the minimum. So that's why we have J equals I plus 1. So wherever we're looking we wanna start looking for the minimum right after that. So if we find an element that's smaller than our current minimum that means that we found a new minimum. We can update what our minimum index is. So that min is always gonna hold where the smallest element is, and this J is gonna hold where we're looking. So now once we've iterated through every element to the right of our sorted position, we found the minimum element because we're always--excuse me--we're always updating what our minimum is. So now once we have our minimum, we just wanna swap them, we just also have this extra check. Well, if I'm already--my minimum is already in my place, there's nothing really to swap so we can save ourselves to swap there. So does everyone see how this is working? This J equals I plus 1 is a little confusing but it just says, that as I'm looking over elements, I don't need to look over the whole list again. I just need to look at everything to the right of what I know is already sorted. Because that's probably wrong and everything to the left we know is correct. So selection sort questions? Yeah? [ Inaudible Remark ] >> So yes, so asymptotically yes, they are the same. Just in practice usually selection sort is gonna run a little bit quicker. [ Inaudible Remark ] >> So is there a preference? No, we wanna implement whatever you think is more interesting or more straightforward or what you wanna learn more about by actually writing. So yeah, so both of these are definitely good to go to implement. If you--I don't know if David showed this yet but there's like a graphic that you'll see of like the sorting algorithms raising and so bubble sorts usually kinda last and some of the better ones are gonna finish faster even though they're same big O. Yeah. [ Inaudible Remark ] >> Exactly, so now let's look at the omega case of both of these algorithms. So selection sort, the omega case, what is that gonna do? At every element list, well it's gonna find the minimum, it's gonna realize the minimum is already there and move on. So it's still gonna be O of N squared. Now if we back up the bubble sort, we have this, while the elements have not been swapped, so let's say the list is already in order which is our omega or our best case. It can't get any better then what we have to do is already done. So bubble sort is gonna realize that the list is already sorted just going over it once. So yes, in the best case, bubble sort is faster because it's not gonna waste time doing an O of N squared operation. Instead it's just gonna go through it once and say I'm sorted, I'm done. Where selection sort is going to go--a lot simple. So selection sort is every single time, no matter what the list I talk with, look at every element and for every element look at every element. However, when I say that selection sort is usually faster, that's because that omega is pretty rare and rarely do we have to solve list--sort list that are already sorted. So on average, selection sort is probably faster but in the best case, you're right yes, bubble sort is both asymptotically and in terms of actual machine time, faster. Yeah? [ Inaudible Remark ] >> Yeah. So why is it faster? You could just kinda see that selection sort, you know where we're kinda moving, we're more efficient. Like we know that this part of list is sorted. With bubble sort, we can just kinda, you know, bounce back and forth and keep going over the list that many times wherein selection sort, we're kind of reducing the size of the problem each time. Right after we know that these 3 elements have been sorted, we're not looking at every element of the list again. So little optimizations like that, that don't change the big O, make it faster when you're actually running it. So selection sort kind of reduces the size of problem and bubble sort just kind of bounces around and fix things. So, other questions on either of these sorts? Okay. So let's take a look at search. So that's sort, that's done. So let's take a look at binary search. So right now it's implemented as I said as linear search. So this has a big O of N, we need to look at every single element. So this actually doesn't require that our array is sorted. So right now if you just run generate and find, it find, it's gonna work, you know, like oh you're done. Not really. So the reason that this works is 'cause sort doesn't do anything but linear search doesn't require a sorted list. However, what we wanna do is implement binary search which as you recall does require a sorted list. And the benefit of this is that it's O of log N which is much faster than just O of N. So this is our pseudo-code for binary search. So while the length of our list is greater than 0, so while we still have some elements to look at or you know while we haven't looked at everything yet, we wanna look at the very middle of our list. We wanna look at that element and we wanna compare it to the number we're looking for. If we found it, that means true, we're done. If our number is too high that means that everything to the right of that number is also too high. So we can forget that the right half--that that half of the list exists. So the same thing with the other way around, if our number is too low, then we can forget the other half of that list exists. So let's just look at an example. So here are 10 numbers. Yeah. So if our number is too high, that means we only need to look at the left half because everything to the right we know is also too high. So if our number is too low, we only need to consider the right half because everything that's to the left of that number is also too low. So we can definitely forget about it. Yeah. [ Inaudible Remark ] >> Exactly. So what happens if the list is 10 digits? So at this point you kinda need to make a decision, do I need to, do I wanna round up or do I wanna round down? So let's just look at this case. So here I have 10 elements. So I'm gonna calculate the middle, I have 10 over 2 and that's 5. So that's fine. So I can go over 0, 1, 2, 3, 4, 5 and I'm at element 161. So in this case, I'm just looking for 164. So, some little messaging intended. So I'm looking for 164. 161 is too low, so what are we gonna do? We're gonna throw away everything to the left of the 161 including the 161 because we don't need to look at that either, we know that it's too low. So now we just have this list. So, now as you said when we divide by 2, we're not--well, I know we still are. So we have 0--we have 4 elements, so we have 0, 1, 2, 3, 4. 4 over 2 is 2, we're gonna look at 0, 1, 2 and we're at the 175. So in this case the 175 is too high. So we can forget about this whole left half. So this 175 and the 182 don't exist anymore because they're definitely wrong. So now I have the 161 and the 1--I actually got rid of that. So we actually just have the 164 left. So to answer your question what happens, we basically need to round. So if I had 9 elements here, when I divide by 2, I'm gonna get 4 and a half. So probably just wanna make that 4. As long as I do that consistently, I'm always gonna find the middle element. Other questions on binary search? Yup. [ Inaudible Remark ] >> So, yes. So, in this case, we took something that was O of N, just [inaudible] search and we made it O of N squared log N. So yes, that is true. But, that's what you did for Pset, so yes, in general, technically, if you combine the two it's faster. We do have sorting algorithms that are faster than O of N squared which we'll learn shortly, and using those faster algorithms where it can actually get a better time. However, yes, in this case you are technically making it slower, but you're making better, so it's so much better design, and so there's so much more edification out if this. Yeah. [ Inaudible Remark ] >> So this one? Yes. So, right now, so there's nothing wrong, correcting is wise, with what's done now, but if you're having this thing you're gonna get a one for design, because you can do so much better than just looking at every single element. So, there's nothing correct me if I was wrong, it works, and whatever you throw at it, it's gonna work, but we wanna change it, so that it's better designed and so you learn about binary search. Question. >> How do you get it to forget half of them, half of the list? >> Yeah, so that's a good question, so how do we effectively forget about half the list? So there are basically two ways you can do binary search. That algorithm we just looked at is effectively iterative, right. We're using a for loop, that's what we've been using so far in all of our Psets. This week in lecture, we're gonna look at something called recursion, and recursion is basically one function calls itself, and it can continue to call itself until we reach some goal or we know that we're never gonna find it. So in the iterative case, we can forget the left half of the list by just updating some left bound. So if we say we have a left bound like this is the most, left most element and this is the right most element, and I can calculate the middle based on these two bounds so after I need to move left to right, if I just move like say the right bound, that means that this is effectively the new end of the list as far as you're concerned. So we don't actually need to remove the elements from memory. In fact, C has a really hard time with resizing arrays, so instead of physically removing it, we just wanna kind of pretend that it doesn't exist anymore, so same thing with recursive, you're gonna continue to call search, but each time you call it, you're gonna supply a different set of arguments and effectively you're gonna say forget the left half and use this middle, forget the right half and use this middle, so you see more about that this week but just now that you can do it both ways. I know--do whichever way you prefer, in which way you find more straightforward. But in both cases, you're gonna need to be able to determine the middle element based on some current left bound and some current right bound that have to change based on what number you've already look at in the list. So, questions on either of these approaches, both of which are fine. So, because we haven't seen recursion yet, I definitely recommend you know trying the iterative and if, you know, you're down to Pset early and you wanna do recursion, just to see and learn it, go for that but definitely not required to wait until we learn about recursion, wrap your head around it and then use it, using the iterative method is fine, and if you're starting right now, go for it. So that was the Find folder, that sort and search, so any final questions on either one of those? Okay. Let's get to the fun part. So now, we're looking at the game of Fifteen. So there are four functions that we need to write in order for this game to work. The first is init which is gonna initialize the game, we need to implement draw, which is gonna output the state of the game onto the user, we need to implement move and finally, which is gonna move tiles around and then finally, we need to implement a function that checks if the game has been won and we can congratulate the user for doing something I can't do. So we have this file 15.c supplied for us and the main function is already written. Woohoo, we're done. So this main function, what it's gonna do is it's gonna accept and parse the command line argument, create the board, check if the game is won and exit, and it's gonna get input and move the tiles. So, let's take a look at what's going on there. It sounds like, you're done right? So if we open up 15, and scroll through this, we have this nice comment, don't worry about this define open source 500 thing, so we're just including some libraries here, the usual folks that you wanna include, and so now we have some constants. So, as you saw, might have seen a section, this define statement creates what's called a constant. So, this is not a variable, it doesn't have a type or a size, when you compile your code, one of the first thing that compiler is gonna do, it is effectively gonna do a find and replace. Every time it sees DIM_MIN, it's gonna delete that and type in the number 3. So, these aren't variables, but they're constants, and that usually leads to better designed and easier to read code. So now, we have a couple of global variables and now we have our function prototypes, so these are all the functions that exist so far. Question? [ Inaudible Remark ] . >> So what's the difference between const and define? So if I say const that is actually a variable. So it's gonna be find and replace. It's actually gonna go somewhere in RAM and you can read from it. When I say define it's never actually gonna be put in the computer's memory. Instead before the executed was created every time we see those two word, DIM_MIN or DIM_MAX, they're just gonna be wiped out and replaced with the number three. So they are the same in that you can't change them but different in what the compiler does with them. Yeah. [ Inaudible Remark ] >> Yeah so basically what the function prototype is, is kinda the first line of the function. So if I go down here to the function clear which was written for us. Okay. Okay, so you have void clear void. Remember the function prototype just said what this first line was. So basic convention is you should match--the function prototype should match whatever the declaration of your--the definition of your function is down here. So, in this case, we're just supplying void just like we did to main at the beginning of the term, just as they don't need any arguments. I can get rid of this void and it would be fine. This is just one style of writing that if there aren't any arguments I can just say void. So after our function prototypes, we have our main. So this function greet is written for you. It's just gonna say hello. And as usual we make sure they supply the right number of arguments like the good programmers we are. Take that number and we're to convert that number to the size of the board. So when I run Fifteen, I wanna supply a number between 3 and 9. And that's going to be the size of the board. So now I'm just gonna printf, if they give me the wrong number that needs to be between 3 by 3 and 9 by 9 and return 2. So this is just a different area code. So if I return 1, that means I didn't supply the right number of arguments and if I return 2 that means I supplied an argument but it was wrong. So here's just the use of as we saw in the last Pset, these different arrow codes or return values. Here's one thing we can use them for. Different things went wrong so returning different things. So now we're calling this function init which is not written for you and this is as the comment says we wanna initialize the board and get everything ready to go. So now, we're gonna enter in this main loop that kind of is gonna keep looping as you're playing the game. So while true. This is called an infinite loop. This is not going to exit until we tell it to exit. So while true, we're gonna clear the screen so we can redraw the board. Call draw. So now we're gonna have the board on the screen and before we allow the user to move we wanna check if they won. So if they did win, we want to break out of this infinite loop because the user is not playing anymore. So now, we're going to ask the user what tile they want to move. So we're not gonna prompt them infinitely, we're going to prompt them once and then after they input we're gonna go back and prompt them again. So after we get the tile or the number of the tile, they want to move, we're gonna try to move it. If we can't move it, never gonna say illegal move. And just kinda wait a minute so that it can animate okay. And after they do--after they select the tile to move and we move it then it's just gonna slip again to enemy. So even though this move is inside of this it condition, it's still calling the function move. Which means it's still going to execute move and if you wanna do something in move like move a tile, which sounds a good idea, that's still gonna happen. So even though it doesn't just say move tiles semicolon and it's inside of this condition, it's still being executed the same way it would other wise. So that's it for me. And so now, this is just the wait and see to clear the screen, don't worry about that. Print the welcome message in all caps 'cause we're yelling. And so now here are the four functions we have to do, to do on all of them and comments explaining what we need to do. So let's first take a look at init. So we saw these two global variables. One called board and it specifies two dimensions. So this means that we have a two-dimensional array which is basically a grid. So this DIM_MAX and DIM_MAX you remember are the defined constants and may have a value of 9. So that means no matter what when we start our game we have a 9 by 9 grid representing as big as the board is allowed to be. We also have a global variable called D. So this is the size of the board. So this is basically what the user typed in, so this is gonna 3, 4, 5, et cetera. So because C can't really resize a raise and we don't wanna bother dynamically creating a different size array based on what the user typed in, we're just gonna create this huge 9 by 9 array. So even if we're only working with the board of 3 by 3 we don't--we still have this 9 by 9 array but we don't wanna look at the whole thing. We never really wanna go outside of the first three squares sideways or vertically but they do exist because we've created this array that's 9 by 9. So board, after init is complete, board needs to contain the starting state of the board. So notice init doesn't return anything, that's because it's just going to update this global variable. So because this variable is global it was declared outside of main and outside of any functions. That means any function we want can access it and change it. So there are few ways you could represent your game board. Let's say you have board XY so some first dimension and some second dimension. That could either be the element XY which should be column X row Y or you might find it easier to work with that meaning row column. So you often see row I and column J or something like that. So that decision is up to you. How you wanna represent the board is your call. But you also wanna make sure that regardless of your representation that the board starts off in descending order. So 15 should be first if it's 4 by 4 and 14. There's also this condition to make sure that the board is actually solvable that if there are an odd number of total tiles like 15 tiles, not counting the blank space, if that number is odd then you need to swap the 2 and the 1. So the last row should be 312 instead of 321. That's just to make sure the board is solvable. 321, you actually couldn't solve it. That'd be really meaningless. So we also need to make sure that we keep track of the blank tile so that's really important when moving because we can only move things into a blank space or else we have a whole new game if we can. So you need to choose some representation of your blank tile. However, we can't just use a string blank or a letter B for blank for something like that because our board needs to contain only ints. Now remember that we declare this as int board 99. So that means we can't put anything in there that's not an integer. So you probably wanna choose some integer value that will never appear on the boards that are given 'cause if it did then you can easily confuse the blank tile for an actual numbered tile. So here, this could be where define comes in handy. So instead of trying to remember oh, I choose the number 1, 2, 3, 4, 6 as my blank space. Instead of trying to remember that everywhere I probably wanna use define to create some constant representing my blank space that everywhere in my program I wanna use that constant not the value of the constant because let's say that you chose the value 16 for your blank space. So now I come along and I say well, I want a larger board. In that case 16 is now a tile so if I had chosen 16 and just use the number 16 everywhere, I have to go through and change every 16 to some other number like a million. If I use a define I only need to change that at the top of my program and then everywhere else in the code I've effectively changed what the blank tile means. So it's a really good idea to use define 'cause it also makes your code a lot more readable instead of just hitting random numbers everywhere, you'll see words like blank space. So questions on what we need to do with init? Okay, so basic idea, we're just not gonna return anything, just fill up some global array that other people can use. So now we need to worry about draw. So what draw is gonna do is output the current state of the board to the terminal. So remember that board IJ, so whether that means like the coordinates XY or row I column J, whatever that means, that's going to give you the value of the tile that's in that place. So each tile has a different number. We probably wanna store those numbers inside of the board array. So again, what this mean, what I and J mean are up to you, but depending on how you choose to represent your board that's gonna change how you output it. So you need to make sure that we output things in the right order. We wanna stay in one row at a time and output every element in one row before moving on to the next row. So you can't just print out a column and then print out another column just because of the way printf works. Right? We can print out a row and once you print a new line, we can't really easily go back up to the previous line and try to add something. So we wanna make sure that we print things row by row. So some tips for writing draw, make sure that you only print the new line at the end of the row. So make sure--you know, print out all the columns then print the new line to move on to the next row and make sure just for formatting that you have some spaces between columns and maybe some other characters like a pipe or a plus or something just to kinda create a grid. And so there's a little printf trick we can use. See I noticed that if we wanted to print 15, we wanted to print 5. Instead of our grid if we wanted to make sure everything lines up that's kinda messes up, right, because 15 has two digits and 5 has next digit so we need to make sure that we somehow compensate for that by printing a space. So printf, this is really cool way to do this if you just say present 2 so that 2 is gonna say what the minimum number of digit is. So if I just print a 5 there, it's actually going to print space 5 instead of just 5. So you can need to determine you know what the best value for your grid is depending on what it looks like. But just--so you don't have to worry about is it less than 9 and put the space and put the number. You know, it gets even worse once you get into three-digit numbers. >> So you don't have to worry about that, there is that quick little printf shortcut. So questions on draw? Okay, so now let's get into actually playing the game. So the Move function is going to allow the user to move tiles around on the board. So to move a tile all we really need to do is change the board we're in, right? If we wanna move 15 from the top left corner into the space next to it, we just need to take the 15, put it into that slot in the board array and take our blank space and put it into whatever slot the 15 was in. However, not all moves in the game of Fifteen are legal. So we can't--if our blank space is in the bottom right and we wanna more a tile in the top left, we can't because we can't move the tile over another tile. So Move needs to determine if a move is legal before it actually makes it. So you notice that Move is a Boolean which means it's gonna return true or false and if we can't make a move, then you should leave the board array alone and return false. So remember in 15.c it's gonna check if move was true or false. And if it's false, meaning the user can't make that move, it's gonna say something. So you need to make sure that you're returning true or false appropriately and making sure not to update the board. So also with move, you notice it only takes one argument. And that's the number of the tile that I want to move. So the number of the tile and where the tile is aren't necessarily the same, right? My tiles are in some 2D array but I'm only getting a number. So that means I need to look for where that tile is. And the only way to do that is to search through the board array and look for the number that the user specified. So we can go through row by row or column by column, whatever you want, and get some pairs, some XY or some IJ that says, Mike, the tile I wanna move is right here. So we also need to determine where the blank tile is because a legal move is when the blank tile is immediately adjacent to the tile that you wanna move. So a little design question here, we don't really need to look at the entire board every time to find the blank space, right? Once we move, once we move a tile, we know exactly where the blank space is. It's not gonna change until we try to make another move. So we're searching over the whole thing to find a number and then searching over the whole thing to find a blank space is little wasteful. So you can think about what the best way to avoid wasting that. So now if the positions are adjacent, that means that the values in the board can be swapped. So basically four cases either, you know there, one is to left of the other, one is to the right of the other, one is above the other, one is below the other. So you need to consider that case and you also need to think about what the size of the board is. So you wanna make sure that you never end up somehow moving tiles off the board or something like that. So any questions on making sure the move is legal in moving it? Yeah >> Is the size of the board going to change? >> So is the size of the board going to change? It will never change within the same game but it will change among different games. So when I run 15 and then some number, that number says how big the board is. So if I run 15, 4, I'm gonna get the game of 15 because I have a 4 by 4 grid, that's 16 tiles minus 1 for the blank tile, so that's 15 tiles. So once I'm in that game, I can't like convert that to a 6 by 6 grid instead. But when I run the program again, I can run it with a different number. So your code needs to be able to handle inputs from 3 to 9 as those defined constants say. And also remember that even though your board is 3 by 3, your array is 9 by 9, so you need to make sure by hand you don't go outside of the actual dimension of the board regardless of how big the array is. Are there questions on moving? Alright. So that's done, now our last function is won. So this is also a Boolean and it's going to return true if the game has been won. So that means that all the tiles are in increasing order. That means there's a 1 in the top left, there's a 2 next to that, and there's a 3 next to that and then on the next row there's a 4 or on the same row depending on how big your board is, and all the way down until all the numbers are in order and the blank tile is in the bottom right. So in order to check if the game has been won, we need to iterate over the entire board array, again, just like when we're moving, and we need to check every single value. And if each value matches up to what we expect it to be, that means that the game has been won. Now as soon as one thing is out of order, we know that the entire game is not won. So if we find the 2 in the left, we don't need to go through everything in order to find out, you know, how many tiles are left or something like that. Once one tile is wrong the whole game is wrong. So think about that when you're implementing your won function. And we also need to make sure we look at things in the right order. You know we can't just look at--we can't say the columns are in order. We need to make sure that the row--everything is in order in rows. So 1, 2, 3, next row, 4, 5, 6, next row, 7, 8, 9, et cetera. So again, depending on how you represented your board that's going to change so just one thing to think about when you choose your board representation, just think about what is actually being stored in that array and if in memory you drew a little grid where the numbers would be if I say something like board 2, 3. So any questions on won or any part of Fiftee or Find? Yeah. [ Inaudible Remark ] >> Yes, so is there a default structure so if we look at--back into the Fifteen code. So you noticed that it's already declared for us. We didn't even have to declare it. So we just know that there are some 9 by 9 grid in memory and we can do something with it. So this is what you should be using to save your board state. So I mentioned that variable board and that's already declared for us. Other questions on anything? Yeah. [ Inaudible Remark ] >> Yes, so the arrays will always be square. We can never have a 3 by 4. We're just supplying one number and that one number says that many rows and that many columns. [ Inaudible Remark ] >> Right. So if they entered a 9 by 9 there'd be 80 tiles. 81 if you count the blank. Yeah. [ Inaudible Remark ] >> Oh sure, so in section this week you're gonna learn all about GDB but what GDB is a debugger. So as you're writing your Psets 1 and 2 you might have, you know, oh, I'm stuck. My program isn't working right. Let's put a printf here and see what this variable is. That's a really common debugging technique and it definitely works. What GDB is, is a way to kind of make that a little easier. What it will allow you to do is say that "Okay, once I get to this function won I wanna stop. My program is gonna stop executing." I'm not gonna like print out variables and look at where things are in memory then I can actually step through like line by line of my program. And so you see how to do that in section but it's really, really simple and so if you say "Okay, my game isn't working right. I don't where it's going wrong" so I can go in to say the move function and say "Okay, is this line right?" Yup! Go to the next line. Is that right? Check my board array and things like that. So it is really, really helpful as you're writing your code to be able to step through it line by line without saying printf a million times, compile it then I gotta hand it in, you know lay out printf's. GDB is just a way of making that faster. Yeah. [ Inaudible Remark ] >> So to be clear this problem set has two parts. One is Find and one is Fifteen. So they're not really related to each other like they're gonna be run independently but you do have to do them both. You do have to comment, generate, write sort, write search and then in Fifteen write those four functions. So they're both parts of the problem set, you know find is not being used by Fifteen anywhere so they're independent, you can start them in either order but they're both part of the assignment. You need to do them both, sorry. Other question on the problem set? Yeah. >> How do we switch the blank tile so somebody enters the game of 80 then how do we know how to switch them the same time? >> So how do we switch the blank tile? So remember that our board is just some array and inside of that grid or that array are values and inside one of those spots in the grid is the blank tile. So when we make a move we're switching the blank tile, the position of the blank tile and the position of the tile we wanted to move. So to determine that we need to say "Okay, given some number 80 I need to find out where that 80 is." So once I found that 80 I need to find out where the blank space is and say "Okay, if they're next to each other somehow I just need to swap their locations inside of that board array." So it's up to you to find out where the tile is, where the blank space is, if they're next to each other and then swap them. So that now the board says the blank space is no longer in the bottom right but it's the space left of that because that's where the 80 was or something like that. [ Inaudible Remark ] >> So what--how you represent the blank space is up to you. You can choose any constant that makes sense to you but just make sure that it's not a number that's ever going to be used by a tile. So if I say my blank space is 15 and I'm playing a 4 by 4 grid then I have two things that are 15 and I'm probably gonna get confused. Yeah. >> How do you get it to not show the integer that you choose to represent your blank space in the array? >> Okay, so the question was how do we make sure that we don't output the value that that number we chose represent the blank space out on our grid. So when we output the grid we can't--suddenly can't just say printf board and then it's gonna printf the board with spacing and columns and grid, stuff like that. So when we print out the board we actually need to iterate through every space of the board. So we know what we chose as our blank space representation. So you can just say if it's our blank space then we don't wanna output that. We probably don't wanna output nothing 'cause that's gonna mess up our grid but we definitely don't wanna output that number. So as long as that's defined somewhere you can just check, is it the blank space? No, print the number if it's not, okay, I can print something else, whatever you choose that to be. Other questions? Alright, so if there are no final questions I'll be here afterwards and good luck on game Fifteen.