[ 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.