[MUSIC PLAYING] 

ANDI PENG: Welcome to week 3 of section. Thanks, you guys, for all coming to this earlier start time today. We've got a nice, little intimate group today. So hopefully we'll get to finish, perhaps, early, a little bit early today. So quickly, just some announcements for the agenda today. Before we start, we're going to just go over some brief logistical issues, pset questions, debrief, things like that. And then we'll dive right in. We'll use a debugger called GDB to start debunking our code, which David explained in lecture the other day. We'll go over the four types of sorts. We'll go over them pretty quickly since they're pretty intensive. But know that all the slides and source code are always online. So feel free, at your perusal, to go back and take a look at that. 

We'll go through asymptotic notation, which is just a fancy way of saying "runtimes," where we have the big O, which David explained in lecture. And we also have Omega, which is the lower bound runtime. And we'll talk a bit more in-depth regarding how those work. And lastly, we'll go over binary search, because a lot of you who have already glanced at your psets probably know that that is a question that's in your pset. So you'll all be happy that we cover this today. 

And lastly, per your section feedback, I actually left about 15 minutes at the end to just go over logistics of pset3, any questions, maybe a bit of guidance, if you will, before we start programming. So let's try to get through the material pretty quickly. And then we can spend some time taking more questions for the pset. OK. 

Quickly, so just a few announcements before we start today. Firstly, welcome to making it through two of your psets. I took a look at your-- yeah, let's get a round of applause for that one. Actually, I was really, really impressed. I graded the first pset for you guys last week and you guys did incredible. 

Style was on point besides a few comments. Make sure you're always commenting your code. But your psets were on point. And keep it up. And it's good for the grader to see that you guys are putting in as much effort in your style and your design in your code that we would like for you to see. So I'm passing along my gratitude for the rest of the TAs. 

However there are a few debrief questions I just want to go over that would make both my life and a lot of the other TAs' lives a bit easier. Firstly, I've noticed this past week-- how many of you have been running check50 on your code before you submit? OK. So everyone should be doing check50, because-- a secret-- we actually run check50 as part of our correctness scripts for testing your code. So if your code is failing check50, in all likelihood, it's probably going to fail our check as well. Sometimes you guys have the right answers. Like, in greedy, some of you have the right numbers, you just print out some extra stuff. And that extra stuff actually fails the check, because the computer doesn't really know what it's looking for. And so it will just run through, see that your output doesn't match what we expect the answer to be, and mark it is wrong. 

And I know that happened in some of your cases this week. So I went back and manually regraded everyone's code. In the future though, please, please make sure that you're running check 50 on your code. Because it's kind of a pain for the TA to have to go back and manually regrade every single pset for every single, little missed instance. So I didn't take off any points. I think I took off maybe one or two for design. In the future though, if you're failing check50, points will be taken off for correctness. 

Furthermore, psets are due Fridays at noon. I think there's a seven-minute late grace period that we give you. Per Harvard time, they're allowed to be seven minutes late to everything. So here at Yale, we'll adhere to that as well. But pretty much, at 12:07, if your pset is not in, it's going to be marked as late. And so while it is marked as late, the TA-- I'm still going to be grading your psets. So you'll still see a grade appear. However, know that at the end of the semester, all late psets will just be automatically zeroed by the computer. 

We do this for two reasons. One, sometimes we get excused, like dean's excuses, later on that I don't know about yet. So we like to make sure we're grading everything just in case, like, I'm missing a dean's excuse. And secondly, keep in mind, you can still drop one pset that has full scope points. And so we like to grade all of your psets just to make sure that your scope's there and you're trying them. So even if it's late, you'll still get credit for scope points, I think. 

So moral of the story is, make sure your psets are in on-time. And if they aren't in on-time, know that it's not great. Yeah, before I move on, does anyone have any questions regarding pset feedback? Yeah. 

AUDIENCE: Did you say we can drop one of the psets? 

ANDI PENG: Yeah. So there's nine psets overall over the course of the semester. And if you have scope points-- so scope is just, pretty much, are you attempting the problem, are you putting in time, are you showing that you've demonstrated you've read the spec. That's pretty much scope. And if you are fulfilling scope points, we can drop the lowest one out of full scope. So that's in your advantage to complete and try every pset. 

Even upload-- if none of them work, upload them all. And then we'll hopefully be able to give you some of those points back. Cool. Any other questions? Great. 

Secondly, office hours-- a few quick notes about office hours. So first, come early in the week. No one is ever at office hours on Mondays. Christabel came to office hours last night. Yeah, Christabel. And what did we have at office hours last night, Christabel? 

AUDIENCE: We had ice cream. 

ANDI PENG: So that's right, we had ice cream at office hours last night. While I can't promise you that we'll have ice cream at office hours every week, what I can promise you is that there will be a significantly better student to TA ratio. Like legit, it's like three to one. Whereas, contrast that with Thursday, you've got about 150 really stressed kids and no ice cream. And it's just not productive for anyone. So moral of the story is, come early to office hours and good things will happen. 

Also, come prepared to ask questions. You know? Regardless of what TAs, I think, have been saying, we've been getting a couple students who come in on Thursday at, like, 10:50 not having read the spec being like help me, help me. Unfortunately at that point, there's not much we can do to help you. So please come early in the week. Come early to office hours. Come prepared to ask questions. Make sure that you, as a student, are where you need to be so that the TAs can guide you along, which is what office hours should be allotted for. 

Secondly, so I know professors like to surprise us with tests. I had a professor those like, yo, by the way, remember that midterm you have next Monday. Yeah, I didn't know about that midterm. So I'm going to be that TA that reminds you all that quiz 0-- because, you know, we're CS. Now that we've done arrays, you get why it's quiz 0, not quiz 1, eh? OK. Oh, I got some chuckles on that one. OK. 

So quiz 0 will be October 14 if you're in the Monday-Wednesday section and October 15 if you're in the Tuesday-Thursday section. This does not apply for those of you at Harvard who-- I think you'll all be taking your quizzes on the 14th. 

So yeah, next week, if David, in lecture, goes, yeah, so about that quiz next week, you all won't be shocked because you came to section and you know that your quiz 0 is in two weeks. And we'll have review sessions and everything. So no worries about being scared for that. Any questions before-- any questions at all regarding logistical issues, grading, office hours, sections? Yeah. 

AUDIENCE: So the quiz is going to be during lecture? 

ANDI PENG: Yeah. So the quiz, I think, is 60 minutes allotted in that time slot that you'll just take in the lecture hall. So you don't have to come in on, like, a random 7:00 PM. It's all good. Yeah. Cool. 

All right. So we're going to introduce a concept to you this week that David has already kind of touched on in lecture this past week. It's called GDB. And how many of you, while in the course of writing your psets, have noticed a big button that says "Debug" on the top of your IDE? OK. So now we'll actually get to unearth the mystery of what that button actually does. And I guarantee you, it is a beautiful, beautiful thing. 

So up until now, I think there's been two things students have been typically doing when debugging psets. One, they either add in printf()-- so every few lines, they add in a printf()-- oh, what is this variable? Oh, what is this variable now-- and you kind of see the progression of your code as it runs. Or the second method kids do is that they just write the whole thing and then go like this at the end. Hopefully it works. I guarantee you, GDB is better than both of those methods. Yeah. So this will be your new best friend. Because it's a beautiful thing that visually displays both what your code is doing at a specific point as well as what all of your variables are carrying, like what their values are, at that specific point. And in this way, you can really set breakpoints in your code. You can run through line by line. And GDB will just have for you, displayed for you, what all of your variables are, what are they doing, what's going on in the code. And in such a way, it's so much easier to see what's happening instead of printf-ing or writing down your statements. 

So we'll do an example of this later. So this seems a bit abstract. No worries, we'll do examples. And so essentially, the three largest, most-used functions you'll need in GDB are the Next, Step over, and Step into buttons. I'm going to head over there, actually, right now. 

So can you guys all see that or should I zoom in a bit? In the back, can you see that? Should I zoom in? Just a little bit? OK, cool. There we go. OK. 

So I have, here, my implementation for greedy. And while a lot of you guys wrote greedy in while loop form-- that is a perfectly acceptable way to do it-- another way to do it is to simply divide in the modulo. Because then you can have your value and then have your remainder. And then you can just add it all together. Does the logic of what I'm doing here make sense to everyone, before we begin? Kind of? Cool. Great. It's a pretty sexy piece of code, I would say. Like I said, David, in lecture, after a while, you'll all start seeing code as something that's beautiful. And sometimes when you see beautiful code, it's such a wonderful feeling. 

So however, whilst this code is very beautiful, it does not work properly. So let's run check50 on this. Check 50 20-- oop. 2? Is that pset2? Yeah. Oh, pset1. OK. So we run check50. 

And as you guys can see here, it's failing a couple of cases. And for some of you, in the course of doing your problem sets, you're like, ah, why isn't it working. Why is it working for some values but not for others? Well, GDB is going to help you figure out why those inputs were not working. 

OK. So let's see, one of the checks I was failing in check50 was the input value of 0.41. So the correct answer that you should be getting is a 4. But instead what I am printing out is the 3-n, which is incorrect. So let's just run this manually, just make sure that check50 is working. Let's do ./greedy. Oops, I have to make greedy. There we go. Now ./greedy. 

How much is owed? Let's do 0.41. And yep, we see here that it's outputting 3 when the correct answer, in fact, should be 4. So let's enter GDB and see how we can go about fixing this problem. 

So the first step in always debugging your code is to set a breakpoint, or a point at which you want the computer or the debugger to start looking at. So if you don't really know what your problem is, usually, the typical thing we want to do is to set our breakpoint at main. So if you guys can see this red button right there, yep, that was me setting a breakpoint for the main function. I click that. 

And then I can go up to my Debug button. I hit that button. Let me zoom back out if I can. There we go. So we have, here, a panel on the right. I'm sorry, guys in the back, you can't really see really well. But essentially, all this right panel is doing is keeping track of both the highlighted line, which is the line of code that the computer is currently running, as well as all of your variables down here. 

So you've got cents, coins, n, all declared to different things at this point. No worries, because we haven't actually initialized them to any variables yet. So in your computer, your computer's just seeing, oh, 32767 was the last used function of that memory space in my computer. And so that's where cents currently is. But no that once you run the code, it should become initialized. 

So let's go through, line by line, what's going on here. OK. So up here are the three buttons that I just explained. You have the Play, or the Run function, button, you have the Step over button, and you also have the Step into button. And essentially, all three of them just go through your code and do different things. 

So typically, when you're debugging, we don't want to just hit Play, because Play will just run your code to the end of it. And then you won't actually know what your problem is unless you set multiple breakpoints. If you set multiple breakpoints, it will just automatically run from one breakpoint, to the next, to the next. But in this case we've just that one, because we want to work our way from top down to bottom. So we're going to ignore that button right now for purposes of this program. 

So the Step over function just steps over every single line and tells you what the computer is doing. The Step into function goes into the actual function that's on your line of code. So for example, like printf(), that is a function, right? If I wanted to physically step into the printf() function, I would actually go into the piece of code where printf() was written and see what's going on there. 

But typically, we assume that the code that we give you works. We assume the printf() is working. We assume that GetInt() is working. So there's no need to step into those functions. But if there's functions that you write yourself that you want to check out what's going on, you would want to step into that function. 

So right now we're just going to step over this piece of code. So let's see. Oh, print, "Oh hai, how much change is owed?" We don't care. We know that's working, so we step over it. 

So n, which is our float that we've initialized-- or declared-- up at the top, we're now equalling that to GetFloat(). So let's step over that. And we see at the bottom here, the program is prompting me to input a value. So let's input the value we want to test here, which is 0.41. Great. 

So now n-- do you guys see here, at the bottom-- it's stored-- because we haven't rounded yet, it's stored in this like giant float that is 0.4099999996, which is close enough to our purposes, right now, to 0.41. And then we'll see later on, as we continue stepping over the program, after here, n has become rounded and cents has become 41. Great. So we know that our rounding's working. We know that we have the correct number of cents, so we know that that's not really the problem. 

So we continue stepping on in this program. We go here. And so after this line of code, we should know how many quarters we have. We step over. And you see we do, in fact, have one quarter because we've subtracted 25 from our initial value of 41. And we have 16 left for our cents. 

Does everyone understand how the program is stepping through and why cents has now become 16 and why, now, coins has become 1? Is everyone following that logic? Cool. So as of this point, the program's working, right? We know it's doing exactly what we want it to. And we didn't actually have to print out, oh, what is cents at this point, what is coins at this point. 

We continue going through the program. Step over. Cool. We go over dimes. Great. We see that it's taken off $0.10 for a dime. And now we have two coins. That's correct. 

We go over pennies and we see that we've got left over cents. Hmm, that's strange. Up here at the program, I was supposed to have subtracted my pennies. Perhaps I just wasn't doing that line right. And alas, you can see here, because we know that we are stepping through lines 32 and 33, that's where our program improperly had variables run. So we can look and see, oh, I'm subtracting cents here, but I'm not actually adding to my coin value. I'm adding to cents. And I don't want to add to cents, I want to add to coins. So if we change that to coins, we've got a working program. I can run check50. You can just exit out of GDB right here and then run check50 again. I could just do this. I have to make greedy. 0.41. And here, it's printing out the right answer. 

So as you guys can see, GDB is a really powerful tool for when we have so much code going on and so many variables that it's hard for us, as a human, to keep track of. The computer, in the GDB debugger, has the ability to keep track of everything. I know, in Visionaire, you guys probably might have hit some segmentation faults because you were running out of bounds of your array. In the example of Caesar, that's exactly what I've implemented here. 

So I forgot to check for what would happen if I didn't have two command line arguments. I just didn't put in that check. And so if I run Debug-- I set my breakpoint to right there. I run Debug. 

OK. Yeah. So actually, GDB was supposed to have told me there was a segmentation fault there. I don't know what was going on right there, but when I ran it, it was working. When you run lines of code through and GDB might just suddenly quit on you, go up and look what the red error is. It'll tell you, hey, you had a segmentation fault, which means that you tried to access space in an array that didn't exist. Yeah. 

So in the next problem set this week, you guys will probably have a lot of variables floating around. You're not going to be sure what they all mean at a certain point. So GDB will really help you in figuring out what they are all equalling and being able to see that visually. Is anyone confused on how any of that was working? Cool. All right. So after that, we are going to dive right into are four different types of sorts for this week. How many of you, first of all, before we start, have read the entire spec for pset3? OK. I'm proud of you guys. That's like half of the class, which is significantly more than last time. 

So that's great, because when we talk about the content in lecture-- or sorry, in section-- I like to relate a lot of that back to what the pset is and how you want to implement that in your pset. So if you come having read the spec, it'll be a lot easier for you to understand what I'm talking about when I say, oh hey, this might be a really good place to implement this sort. So those of you who have read the spec know that, as part of your pset, you're going to have to write a type of sort. So this may be very helpful for a lot of you today. 

So we'll start off with, essentially, the most simple type of sort, the selection sort. The typical algorithm for how we'd go about this is-- David went through these all in lecture, so I'll quickly move along here-- is essentially, you have an array of values. And then you find the smallest unsorted value and you swap that value with the first unsorted value. And then you just keep repeating with the rest of your list. 

And here's a visual explanation of how that would work. So for example, if we were to start with an array of five elements, index 0 to 4, with 3, 5, 2, 6, and 4 values placed in the array-- so right now, we're just going to assume that they're all unsorted because we haven't tested otherwise. 

So how a selection sort would work is that it would first run through the entirety of the unsorted array. It would pick out the smallest value. In this case, 3, right now, is the smallest. It gets to 5. Nope, 5 is not greater than-- or sorry, is not less than-- 3. So the minimum value is still 3. And then you get to 2. The computer sees, oh, 2 is less than 3. 2 must now be the minimum value. And so 2 swaps with that first value. 

So after one pass, we do indeed see that the 2 and the 3 are swapped. And we're just going to continue doing this again with the rest of the array. So we're going to just run through the last four indexes of the array. We'll see that 3 is the next minimum value. So we're going to swap that with 4. And then we're just going to keep running through until, eventually, you get to a sorted array in which 2, 3, 4, 5, and 6 are all sorted. Does everyone understand the logic of how a selection sort works? 

You just have some sort of a minimum value. You're keeping track of what that is. And whenever you find it, you swap it with the first value in the array-- or, not the first value-- the next value in the array. Cool. 

So as you guys kind of saw from a brief glimpse, we're going to pseudocode this out. So if you guys in the back want to form a group, everyone at a table can form a little partner, I'm going to give you guys like three minutes to just talk through the logic, in English, of how we might be able to implement pseudocode to write a selection sort. And there's candy. Please come up and get candy. If you're in the back and you want candy, I can throw candy at you. Actually, do you-- cool. Oh, sorry. OK. 

So if we would like to, as a class, write pseudocode for how one might approach this problem, just feel free. I'll just go around and, in order, ask groups for the next line of what we should be doing. So if you guys want to start off, what's the first thing to do when you're trying to implement a way to solve this program to selectively sort a list? Let's just assume we have an array, all right? 

AUDIENCE: You want to create some sort of [INAUDIBLE] that you're running through your whole array. 

ANDI PENG: Right. So you're going to want to iterate through every space, right? So, great. If you guys want to give me the next line-- yeah, in the back. 

AUDIENCE: Check them all for the smallest. 

ANDI PENG: There we go. So we want to go through and check to see what the minimum value is, right? I'm going to abbreviate that to "min." What do you guys want to do after you've found the minimum value? 

AUDIENCE: [INAUDIBLE] ANDI PENG: So you're going to want to switch it with the first of that array, right? That's the beginning, I'm going to say. All right. So now that you've swapped the first one, what do you want to do after that? So now we know that this one here must be the smallest value, right? Then you have an additional rest of the array that's unsorted. So what you want to do here, if you guys want to give me the next line? AUDIENCE: So then you want to iterate through the remainder of the array. ANDI PENG: Yeah. And so what does iterating through kind of imply we'll probably need? What type of-- 

AUDIENCE: Oh, an additional variable? ANDI PENG: Probably another for loop, right? So we're probably going to want to iterate through-- great. And then you're going to go back and probably check the minimum again, right? And you're going to keep repeating this, because the loops just going to keep running, right? 

So as you guys can see, we just have a general pseudocode of how we want this program to look. This iterate here, what do we typically need to write in our code if we want to iterate through an array, what type of structure? I think Christabel already said this before. 

AUDIENCE: A for loop. 

ANDI PENG: A for loop? Exactly. So this is probably going to be a for loop. What is a check here going to imply? Typically, if you want to check if something is something else-- 

AUDIENCE: If. 

ANDI PENG: An if, right? And then the swap here, we'll go over later, because David went through that in lecture as well. And then the second iterate implies-- 

AUDIENCE: Another for loop. 

ANDI PENG: --another for loop, exactly. So if we're looking at this correctly, we can see that we're probably going to need a nested for loop with a conditional statement in there and then an actual piece of code that's going to swap the values. So I've just generally written a pseudocode code here. And then we're actually going to physically, as a class, try to implement this today. Let's go back into this IDE. 

Uh-oh. Why is that not-- there it is. OK. Sorry, let me try to zoom in a bit more. There we go. All I'm doing here is I've created a program called "selection/sort.c." I've created an array of nine values, 4, 8, 2, 1, 6, 9, 7, 5, 3. Currently, as you can see, they are unordered. n is going to be the number that tells you the amount of values you have in your array. In this case, we have nine values. And I've just got a for loop here that prints out the unsorted array. 

And at the end, I've also got a for loop that just prints it out again. So theoretically, if this program is working correctly, at the end, you should see a printed for loop in which 1, 2, 3, 4, 5, 6, 7, 8, 9 are all correctly in order. 

So we've got our pseudocode here. Does anyone want to-- I'm just going to go ask for volunteers-- tell me exactly what to type if we want to, first, just iterate through the beginning of this array? What's the line of code I'm probably going to need here? 

AUDIENCE: [INAUDIBLE] 

ANDI PENG: Yeah, feel free to-- sorry, you don't have to stand up-- feel free to raise your voice a bit. 

AUDIENCE: For int i equals 0-- 

ANDI PENG: Yeah, good. 

AUDIENCE: i is less than array length. 

ANDI PENG: So keep in mind here, because we don't have a function that tells us the length of an array, we already have a value that stores that. Right? Another thing to keep in mind-- in an array of nine values, what are the indexes? Let's just say this array was 0 to 3. You see that the last index is actually 3. It's not 4, even though there's four values in the array. 

So in here, we have to be very careful of what our condition for the length is going to be. 

AUDIENCE: Wouldn't it be n minus 1? ANDI PENG: It's going n minus 1, exactly. Does that make sense, why it's n minus 1, everyone? It's because arrays are zero-indexed. They start at 0 and run up to n minus 1. Yeah, it's a bit tricky. OK. And then-- AUDIENCE: Isnt'1 that already taken care of though, by just not saying "less than or equal to" and just saying "less than?" 

ANDI PENG: That's a really good question. So, yes. But also, the way that we're implementing the checking right, you need to compare two values. So you actually want to leave the "to" empty. Because if you compare this one, you're not going have anything after it to compare to, right? Yeah. So i++. Let's add our brackets in. Whoops. Great. So we have the beginning of our outer loop. So now we probably want to create a variable for keeping track of the smallest value, right? Does anyone want to give me the line of code that would do that? What do we need if we're going to want to store something? 

Right. Maybe a better name for that would be-- "temp" totally works-- maybe a more aptly named would be, if we want the smallest value-- 

AUDIENCE: Min. ANDI PENG: min, there we go. min would be good. And so here, what do we want to initialize it to? This is a bit tricky. Because right now at the beginning of this array, you haven't looked at anything, right? So what, automatically, if we're just on i equals 0, what do we want to initialize our first minimum value to? AUDIENCE: i. ANDI PENG: i, exactly. Christabel, why do we want to initialize it to i? 

AUDIENCE: Because, well, we're starting with 0. So because we have nothing to compare it to, the minimum will end up being 0. 

ANDI PENG: Exactly. So she's exactly right. Because we haven't actually looked at anything yet, we don't know what our minimum value is. We want to just initialize it to i, which, currently, is right here. And as we continue to move down this array, we'll see that, with each additional pass, i increments. And so at that point, i is probably going to want to be the minimum, because it's going to be whatever is the beginning of the unsorted array. Cool. 

So now we want to add a for loop here that's going to iterate through the unsorted, or the rest of this array. Does anyone want to give me a line of code that would do that? Hint-- what do we need down here? What's going to go in this for loop? Yeah. AUDIENCE: So we'd want to have a different integer, because we're running through the rest of the array instead of the i, so maybe j. 

ANDI PENG: Yeah, j sounds good to me. Equals? 

AUDIENCE: So would be i plus 1, because you're starting at the next value. And then to the end-- so again, j is less than n minus 1, and then j++. ANDI PENG: Great. 

And then in here, we're going to want to check to see if our condition is met, right? Because you want to change the minimum value if it's actually smaller than what you're comparing it to, right? So what are we going to want in here? Check to see. What type of statement are we probably going ti want to use if we want to check something? 

AUDIENCE: An if statement. 

ANDI PENG: An if statement. So if-- and what's going to be the condition that we want inside of our if statement? 

AUDIENCE: If the value of j is less than the value of i-- 

ANDI PENG: Exactly. So if-- so this array is called "array." Great. So if array-- what was that? Say that again. 

AUDIENCE: If array-j is less than array-i, then we would change the min. So the min would be j. 

ANDI PENG: Does that make sense? OK. And now down here, we actually want to implement the swap, right? So recall, in lecture, that David, when he was trying to swap the-- what was it-- orange juice and milk-- 

AUDIENCE: That was gross. 

ANDI PENG: Yeah, that was kind of gross. But it was a pretty good concept demonstrating time. So think of your values here. You've got an array of min, an array of i, or whatever we were trying to swap here. And you probably can't pour them into each other at the same time, right? So what are we going to need to create here in order to swap the values correctly? 

AUDIENCE: A temporary variable. 

ANDI PENG: A temporary variable. So let's do int temp. See, this would be a better time to-- whoa, what was that? OK. So this would have been a better time to name the variable "temp." So let's do int temp. What are we going to set temp equal to here? AUDIENCE: Min? ANDI PENG: It's a bit tricky. It actually doesn't matter in the end. It doesn't matter what order you choose to swap in as long as you're making sure you're keeping track of what you're swapping. 

AUDIENCE: It could be array-i. 

ANDI PENG: Yeah, let's do array-i. And then what's the next line of code we want to have here? AUDIENCE: array-i equals array-j. ANDI PENG: And lastly? AUDIENCE: array-j equals array-i. AUDIENCE: Or array-j equals array-temp-- or, temp. 

ANDI PENG: OK. So let's run this and see if it's going to work. Where is that happening? Oh, that's a problem. See, on line 40, we're trying to use array-j? But where does j only exist in? 

AUDIENCE: In the for loop. ANDI PENG: Right. So what are we going to need to do? 

AUDIENCE: Define it outside the-- AUDIENCE: Yeah, I guess you have to use another if statement, right? So like, if the minimum-- all right, let me think. 

ANDI PENG: Guys, try to take a look Let's see, what's something we can do here? 

AUDIENCE: OK. So if the minimum doesn't equal j-- so if the minimum is still i-- then we wouldn't have to swap. 

ANDI PENG: Does that equal i? What do you want to say here? 

AUDIENCE: Or yeah, if the minimum doesn't equal i, yeah. ANDI PENG: OK. Well that solves, kind of, our problems. But that still doesn't solve the problem of what happens if j-- since j doesn't exist outside of it, what do you we want to do with it? Declare it outside? Let's try running this. Uh-oh. Our sort's not working. 

As you can see, our initial array had those values. And afterwards it should have been in 1, 2, 3, 4, 5, 6, 7, 8, 9. It's not working. Ahh. What do we do? AUDIENCE: Debug. ANDI PENG: All right, we can try that. We can debug. Zoom out a bit. Let's set our breakpoint. Let's go like-- OK. 

So because we already know that these lines, 15 through 22, are working-- because all I'm doing is just iterating through and printing-- I can go ahead and skip that. Let's start at line 25. Oop, let me get rid of that. 

AUDIENCE: So the breakpoint's where the debugging starts? ANDI PENG: Or stops. AUDIENCE: Or stops. ANDI PENG: Yeah. You can set multiple breakpoints and it can just jump from one to the other. But in this case we don't know where the error is happening. So we just want to start from the top down. Yep. OK. 

So this line here, we can step in. You can see down here, we've got an array. Those are the values that are in the array. Do you see that, how index 0, it corresponds to the value-- oh, I'm going to try to zoom in. Sorry, it's really hard to see-- at array index 0, we have a value of 4 and then so forth and so on. We have our local variables. Right now i is equal to 0, which we want it to be. 

And so let's keep stepping through. Our minimum is equal to 0, which we also want it to be. And then we enter our second for loop, if array-j is less than array-i, which it was not. So did you see how that skipped over that? 

AUDIENCE: So should the if minimum, all that-- shouldn't that be inside the first for loop? ANDI PENG: No, because you still want to test. You want to do a comparison every time, even after you run through it. You don't just want to do it on the first pass-through. You want to do it with each additional pass again. So you want to check for your condition inside. So we're just going to keep running through here. I'll give you guys a hint. It has to do with the fact that when you're checking your conditional, you're not checking for the correct index. So right now you're checking for array index of j is less than array index of i. But what are you doing up at the beginning of the for loop? Aren't you setting j equal to i? 

Yeah, so we can actually exit the debugger here. So let's take a look at our pseudocode. For-- we're going to start at i equals 0. We're going to go up to n minus 1. Let's check, did we have that right? Yep, that was right. 

So then inside here, we're going to create a minimum value and set that equal to i. Did we do that? Yep, did that. Now in our inner for loop, we're going to do j equals i to n minus 1. Did we do that? Indeed, we did that. 

So however, what are we comparing here? 

AUDIENCE: j plus 1. ANDI PENG: Exactly. And then you're going to want to set your minimum equal to j plus 1 as well. So I went through that really quickly. Do you guys understand why it's j plus 1? OK. 

So in your array, in your first pass through, your for loop, for int i equals 0, let's just assume this hasn't been changed yet. We have an array of, completely, just four unsorted elements, right? So we want to initialize i equal to 0. And i is going to just run through this loop. And so in the first pass, we're going to initialize a variable called "min" that also equals i, because we don't have a minimum value. So that's currently equal to 0 as well. And then we're going to go through. And we want to iterate again. Now that we've found what our minimum is, we want to iterate through again to see if it's comparing, right? So j, here, is going to equal i, which is 0. And then if array j plus i, which is the one that's next over, as less than what your current minimum value is, you want to swap. 

So let's just say we've got, like, 2, 5, 1, 8. Right now, i is equal to 0 and j is equal to 0. And that's our minimum value. If array-j plus i-- so if the one that's after the one we're looking at is greater than the one before it, it's going to become the minimum. 

So here we see that 5 is not less than that. So it's going to not be 5. We see that 1 is less than 2, right? So now we know that our minimum is going to be the index value at 0, 1, 2. Yeah? And then when you get down here, you can swap the correct values. 

So when you guys were just having the j before, you weren't looking at the one after it. You were looking at the same value, which is why it just wasn't doing anything. Does that make sense to everybody, why we needed that plus 1 there? OK. Now let's just run through it to make sure the rest of the code is correct. Why is that happening? Ah, it's the min right here. We were comparing the wrong value. Oh no. 

Oh yeah, down here we were swapping the wrong values as well. Because we were looking at i and j. Those are the ones we were checking. We actually want to swap the minimum, the current minimum, with whatever the one outside is. And as you guys can see down here, we have a sorted array. It just had to do with the fact that when we were checking the values we were comparing, we weren't looking at the right values. We were looking at the same one here, not actually swapping it. You have to look at the one next to it and then you can swap. So that's what was kind of bugging our code before. And what I did here is everything the debugger could have done for you I just did it on the board, because it's easier to see rather than trying to zoom in on the debugger. Does that make sense to everybody? Cool. 

All right. We can move on to talking about asymptotic notation, which is just a fancy way of saying the runtimes of all of these sorts. So I know David, in lecture, touched upon runtimes. And he went through the whole formula of how to calculate the runtimes. No worries about that. If you're really curious on how that works, feel free to talk to me after section. We can walk through the formulas together. But all you guys have to really know is that n squared over 2 is the same thing as n squared. Because the largest number, the exponent, grows the most. And so for our purposes, all we care about is that giant number that's growing. 

So what is the best case runtime of selection sort? If you're going to have to iterate through a list and then iterate through the rest of that list, how many times are you going to probably, in the worst case-- in the best case, sorry-- run through? Maybe the better question is to ask, what is the worst case runtime of selection sort. AUDIENCE: n squared. ANDI PENG: It's n squared, right. So an easy way to think of this is like, any time you have two nested for loops, it's going to be n squared. Because not only are you running through once again, you have to go back around and run through it once again inside for every value. So in that case, you're running n times n squared, which is-- sorry, n times n, which equals n squared. 

And sort is also a bit unique in the sense that it doesn't matter if these values are already in order. It's still going to run through anyways. Let's just say this was 1, 2, 3, 4. Regardless of whether or not it was in order, it still would have ran through and still checked the minimum value. It would have made the same number of checks every single time, even if it didn't actually touch anything. 

So in such a case, the best and worst runtimes are actually equivalent. So the expected runtime of selection sort, which we designate by the symbol of theta, theta, in this case, would also be n squared. All three of these would be n squared. Is everyone clear on why the runtime is n squared? 

All right. So I'm just going to quickly run through the rest of the sorts. The algorithm for bubble sort-- remember, this was the first one David went over in lecture. Essentially, you step through the entire list and you swap-- you just compare two at a time. And if one's greater, than you just swap them. So if these are greater, you would swap. I've got official right here. 

So let's just say you had 8, 6, 4, 2. You'd compare the 8 and a 6. You'd need to swap them. You would compare the 8 and a 4. You'd need to swap them. If you have to swap the 8 and the 2, change them as well. So in such a sense, you can see, played out over a long period of time, how the values kind of bubble to the ends, which is why we call it bubble sort. 

We would just run through again on our second pass, and our third pass, and our fourth pass. Essentially, bubble sort just runs until you don't make any more swaps. So in that sense, this is just the general pseudocode for it. No worries, these will all be online. We don't have to actually go over this. 

We just initialize a counter variable that starts at 0. And we iterate through the entire array. And if one value is-- if this value is greater than that value, you're going to swap them. And then you're just going to keep going. And you're going to count. And you're just going to keep doing this while the counter is greater than 0, which means that every time you have to swap, you know you want to go back and check again. You want to keep checking until you know that you don't have to swap anymore. 

So what are the best and worst case runtimes for bubble sort? And hint-- this is actually different from selection sort in the sense that these two answers aren't the same. Think about what would happen in a case if it was already sorted. And think about what would happen if it was in the case in which it wasn't sorted. And you can kind of run through why that's happening. I'll give you guys, like, 30 seconds to think about that. 

OK. Does anyone have a guess at what the worst case runtime of bubble sort is? Yeah. 

AUDIENCE: Would it be, like, n times n minus 1 or something like that? Like, every time it runs, it's just, like, one swap less that whatever it was. 

ANDI PENG: Yeah, so you're totally right. And this is a case in which your answer was actually more complex than the one we need to give. So it's going to run-- I'm going to erase all this here. Is everyone good? Can I erase this? OK. You're going to run through n times the first time, right? And they're going to run through n minus 1 the second time, right? And then you're going to keep going, n mine 2, et cetera. David did this in a lecture, where, if you added up all those values, you get something that's like-- yeah-- over 2, which essentially just reduces down to n squared. You're going to get a weird fraction in there. And so just know that the n squared always takes precedence over the fraction. And so in this case, the worst runtime would be n squared. If it was in descending order, think, you have to make a swap every single time. 

What would be, potentially, the best case runtime? Let's just say, if the list was already in order, what would the runtime be? 

AUDIENCE: n. ANDI PENG: It's n, exactly. And why is it n? AUDIENCE: Because you just have to check on each once. ANDI PENG: Exactly. So in the best possible runtime, if this list was already sorted-- let's say 1, 2, 3, 4-- you would just go through, you would check, you would see, oh, they all pan out. I didn't have to swap. I'm done. So in that case, it's just n or the number of steps you just had to check in the first list. 

And after, we now hit insertion sort, where the algorithm is essentially to divide it into a sorted and unsorted portion. And then one by one, the unsorted values are inserted in their appropriate positions in the beginning of the list. 

So for example, we have a list of 3, 5, 2, 6, 4 again. We know that it's currently unsorted because we've just started looking at it. We take a look and we know that the first value is sorted, right? If you're only looking at an array of size one, you know that it's sorted. 

So then we know that the other four are unsorted. We go through and we see that value. Let's go back. See that value of 5? We take a look at it. We compare it to 3. We know that it's greater than 3, so we know that that's sorted. So we now know that the first two are sorted and the last three aren't. 

We take a look at 2. We first check it with 5. Is it less than 5? It is not. So we have to keep looking down. Then you check 2 off 3. Is it less than? No. So you know a 2 has to be inserted into the front and 3 and 5 both have to be pushed out. Do this again with 6 and 4. And we just keep checking essentially, where we just check, check, check. And until it's in the right position, we kind of just insert it into the right position, which is where the name of it came from. 

So that's just the algorithm, pseudocode per se, kind of, on how we would implement an insertion sort. Pseudocode is here. It's all online. No worries if you guys are trying to copy this down. So once again, same question-- what would be the best and worst runtimes for insertion sort? It's very similar to the last question. I'll give you guys, like, 30 seconds to think about this as well. 

OK Does anyone want to give me the worst runtime? Yeah. 

AUDIENCE: n squared. 

ANDI PENG: It's n squared. And why is it n squared? 

AUDIENCE: Because in reverse order, you have to go through n times n, which is-- ANDI PENG: Yeah, exactly. So same thing as in the bubble sort. If this list is in descending order, you're going to have to check first once. And then with every additional value, you're going to have to check it against every single value, right? And so altogether, you're going to make an n pass times another n pass, which is n squared. What about the best case? Yeah. 

AUDIENCE: n minus 1, because the first one is already squared. 

ANDI PENG: So, close. The answer is actually n. Because while the first one is sorted, it may not actually-- it we just lucked out, in that example, that 2 happened to be the smallest number. But that won't always be the case. If 2 is already sorted in the beginning but you look and there's a 1 here, the 1 is going to bump it. And it's going to end up being bumped anyways. 

So in the best case scenario, it's actually just going to be n. If you have 1, 2, 3, 4, 5, 6, 7, 8, you're going to run through that entire list once to check to see if everything's fine. Is everyone clear on running times of selection as well? I know I'm going through these really fast. But just know that if you know the general concepts, you should be good. OK. So I'll just give you guys maybe, like, a minute to talk to your neighbors on what are just some of the main differences between these types of sorts. We'll go over that soon. AUDIENCE: Oh, OK. ANDI PENG: Yeah. OK. Cool, let's reconvene as a class. OK. So this was kind of an open-ended question in the sense that there's lots of answers to them. And we'll go over some of them briefly. I just wanted to get you guys thinking about what differentiated all three types of sorts. And I heard, also, a great question-- what does merge sort do? Great question, because that's what we're covering next. 

So merge sort is the one sort that functions very differently from the other sorts. As you guys can see-- did David do that demo where he had all the cool noises of seeing how merge sort ran, like, infinitely faster than the other two types? OK. So that's because merge sort implements that divide and conquer concept that we've talked about a lot in lecture. In that sense that we like to work smarter, not harder, when you divide and conquer problems, and break them down, and then put them together, good things always happen. 

So the way that merge sort essentially works is that it divides an unsorted array in half. And then it's got two halves of arrays. And it just sorts those two halves. It just keeps dividing in half, in half, in half until everything is sorted and then recursively puts it all together. 

So that's really abstract. So this is just a bit of pseudocode. Does that make sense in the way it's running? So let's just say you have an array of n elements, right? If n is less than 2, you can return. Because you know that if there's only one thing, it must be sorted. Else, you sort the left half, and then you sort the right half, and then you merge. 

So while that looks really easy, in reality, thinking about it's kind of difficult. Because you're like, well, that's kind of running on itself. Right? It's running on itself. So in that sense, David touched upon recursion in class. And that's a concept we'll talk about more. It's that this, these two lines here, actually is just the program telling it to run itself with different input. So rather than run itself with the entirety of n elements, you can break it down into the left half and the right half and then run it again. 

And then we'll look at it visually, because I'm a visual learner. It works better for me. So we'll look at a visual example here. 

Let's say we have an array, six elements, 3, 5, 2, 6, 4, 1, not sorted. All right, there's a lot on this page. So if you guys can look at the first step here, 3, 5, 2, 6, 4, 1, you can split it in half. You have 3, 5, 2, 6, 4, 1. You know that these aren't-- you don't know if they're sorted or not, so you keep breaking them down, in half, in half, in half, until eventually, you only have one element. And one element is always sorted, right? 

So we know that 3, 5, 2, 4, 6, 1, by themselves, are sorted. And now we can put them back together. So we know the 3, 5. We put those together. We know that's sorted. The 2's still there. We can put the 4 and the 6 together. We know that that's sorted, so we put that together. And the 1 is there. 

And then you just look at these two halves right here. You have the 3, 5, 2, 2, 3, 5. You can just compare the beginning of everything. Because you know that this is sorted and you know that that's sorted. So then you don't even have to compare the 5, you just compare the 3. And the 2 is less than 3, so you know 2 must go in the end. 

Same thing over there. The 1 must go here. And then when you go to put those two values together, you know that this is sorted and you know that that is sorted. So then the 1 and the 2, the 1 is less than 2. That tells you that the 1 should go on the end of this without even looking at 3 or 5. And then the 4, you can just check, it goes right in here. You don't have to look at the 5. Same thing with the 6. You know that the 6-- it just doesn't need to be looked. 

And so in that way, you're just saving yourself a lot of steps when you're comparing. You don't have to compare every element against other elements. You just compare against the ones that you need to compare it against. So that's kind of an abstract concept. No worries if it's not quite hitting you right yet. But generally, this is how a merge sort works. Questions, quick questions, before I move on? Yeah. 

AUDIENCE: So you said that you take the 1, and then the 4, and the 6 and put them in. So aren't those-- aren't you looking at them as separate elements, not as the whole? ANDI PENG: Yeah. So what's happening is that you basically are creating a brand new array. So you know that, here, I have two arrays of size 3, right? So you know that my sorted array needs to have six elements. So you just create a new amount of memory. So you're kind of like being wasteful of memory, but that doesn't matter because it's so small. So you look at the 1 and you look at the 2. And you know that the 1 is less than 2. So you know that 1 should go in the beginning of all of those. 

You don't even need to look at the 3 and the 5. So you know 1 goes there. Then you basically chop off the 1. It's, like, dead to us. Then we just have 2, 3, 5, and then 4 and 6. And then you know that, you compare the 4 and the 2, oh, the 2 should go in there. So you plop the 2 down, you chop it off. So then you just have the 3 and the 5 in the 4 and the 6. And you just keep chopping it off until you put them in the array. 

AUDIENCE: So you're just always comparing the [INAUDIBLE]? 

ANDI PENG: Exactly. So in that sense, you're just comparing, essentially, one number against the other number. And because you know that it's sorted, you don't have to look through all of the numbers. You just have to look at the first one. And then you can just plop them down, because you know they belong where they need to belong. Yeah. Good question. 

And then if any of you are a bit ambitious, feel free to look at this code. This is actually the physical implementation of how we would write merge sort. And you can see, it's very short. But the ideas behind it are pretty complex. So if you feel like drawing this out in your homework tonight, feel free to. 

OK. So David also went over this in lecture. What are the best case runtimes, worst case runtimes, and the expected runtimes of merge sort? A couple seconds to think. This is pretty hard, but kind of intuitive if you think about it. All right. 

AUDIENCE: Is the worst case n log n? ANDI PENG: Exactly. And why is it n log n. 

AUDIENCE: Isn't it because it becomes exponentially faster, so it's like a function of that instead of just simply being n squared or something? ANDI PENG: Exactly. So the reason why the runtime on this is n log n is because-- what are you doing in all of these steps? You're just chopping it in half, right? And so when we're doing the log, all that it's doing is dividing a problem in half, in half, in half, in more halves. And in that sense, you can kind of eliminate the linear model that we've been using. Because when you chop things in half, it's a log. That's just the mathematical way of representing it. 

And then finally, at the end, you're just making one last pass through to put all of them in order, right? And so if you just have to check one thing, that's n. And so you're kind of multiplying the two together. So it's like you've got that final check for n down here with a log of n up here. And if you multiply them, that's n log n. 

And so the best case and worst case and expected are all n log n. It's also like another sort. It's like selection sort in the sense that it doesn't matter what your list is, it's just going to do the same thing every single time. OK. So as you guys can see, even though the sorts that we've gone through-- n squared, it's not very efficient. And even this n log n is not the most efficient. If you guys are curious, there's sort mechanisms that are so efficient that they're almost essentially flat in runtime. 

You've got some log n's. You've got some log log n's. We don't touch upon them in this class right now. But if you guys are curious, feel free to google, what's the most efficient sorting mechanisms. I don't know, there are some really funny ones, like-- there's some really funny ones that people make. And you wonder how they ever thought of that. So google, if you have some spare time, on, what are some funny ways that people-- as well as efficient ways-- people have been able to implement sorts. OK. And here's just a handy little chart. I know all of you, before that quiz 0, will be in your room probably trying to memorize that. So that's nice in there for you guys. Just don't forget the logic that made-- why those numbers were occurring. If you're always lost, just make sure you know what the sorts are. And you can run through them in your mind to figure out why those answers are those answers. 

All right. So we're going to move on, finally, to searching. Because as those of you who have read the pset, searching is also part of this week's problem sets. You'll be asked to implement two types of searches. One is a linear search and one is a binary search. 

So the linear search is fairly easy. You just want to search element of a list to see if you get it. You just have to iterate through. And if it equals something, you can just return it, right? But the one that we're most interested in talking about is binary search, right, which is the divide and conquer mechanism which David was demonstrating in lecture. 

Remember the phone book example that he keeps bringing up, the one that he kind of struggled a bit on this past year, where you divide the problem in half, in half, in half, again and again, until you find what you're looking for? And you've got the runtime of that as well. And you can see, it's significantly more efficient than any other type of search. 

So the way that we would go about implementing a binary search is, if we had an array, index 0 to 6, seven elements, we can look in the middle, right-- sorry, if our question first-- if we want to ask the question of, does the array contain the element of 7, obviously, being humans, and having such a small array, it's easy for us to say yes. But the way to implement a binary search would be to look in the middle. 

We know that index 3 is the middle, because we know there are seven elements. What 7 divided by 2? You can chop off that extra 1. You've got 3 in the middle. So is array of 3 equal to 7? It is not, right? But we can do a couple of checks. Is array of 3 less than 7 or is array of 3 greater than 7? 

And we know that it's less than 7. So we know that, oh, it must not be in the left half. We know that it must be in the right half, right? So we can just chop off half the array. We don't even have to look at it anymore. Because we know that half of our problem-- we know that the answer is in the right half of our problem. So we just look at that now. 

So now we look at the middle of what's left. That index 5. We do the same check again and we see that it's smaller. So we look to the left of that. And then we see that check. Is the array value at index 4 equal to 7? It is. So we can return true, because we found the value in our list. Does the way I went through that make sense to everybody? OK. I'll give you guys maybe, like, three, four minutes to figure out how to pseudocode this in. 

So imagine I asked you to write a function called search() that returned a value, a Boolean value, that was true or false-- like, true if you found the value, false if you didn't. And then you were passed in the value you were looking for into values, which is the array-- oh, I definitely put that in the wrong place. OK. Anyways, that should have been to the right of values. And then int n is the number of elements in that array. How would you go about trying to pseudocode that problem in? I'll give you guys like three minutes to do that. No, I think there's only-- yeah, there's one right up here. AUDIENCE: Can I? ANDI PENG: Yeah, I got you. Is that working? OK, cool. 

OK. All right guys, we're going to rein it in. OK. So assume we've got this lovely little array with n values in it. I didn't draw the lines. But how would we go about trying to write this? Does anyone want to give me the first line? If you want to give me the first line of this pseudocode. 

AUDIENCE: [INAUDIBLE] AUDIENCE: You'd want to iterate through-- AUDIENCE: Just another for loop? AUDIENCE: --for. 

ANDI PENG: So this one's a bit tricky. Think about-- you want to keep running this loop over and over again until when? 

AUDIENCE: Until the [INAUDIBLE] value is equal to that value. ANDI PENG: Exactly. So you can actually just write-- we can even simplify it more. We can just do a while loop, right? So you can just have loop-- we know that it's a while. But for right now, I'm going to say "loop"-- through what? Loop until-- what is our ending condition? I think I heard it. I heard someone say it. 

AUDIENCE: Values equals middle. ANDI PENG: Say it again. AUDIENCE: Or, until the value you're searching for is equal to the middle value. 

ANDI PENG: What if it's not in there? What if the value you're searching for isn't actually in this array? AUDIENCE: You return 1. 

ANDI PENG: But what do we want to loop until if we have a condition? Yeah. 

AUDIENCE: Until there's only one value? ANDI PENG: You can loop until-- so you know that you're going to have a max value, right? And you know that you're going to have a min value, right? Because also, that's something I forgot to say before, that something that's critical about binary search is that your array is already sorted. Because there's no way of doing this if they're just random values. You don't know if one's larger than the other, right? 

So you know that your max and your mins are here, right? If you're going to be adjusting your max in your mins and the mid-- let's just assume your mid value is right here-- you're going to basically loop until your minimum is about the same as your max, right, or if your max is not the same as your min. Right? Because when that happens, you know that you've eventually hit the same value. So you want to loop until your min is less than or equal to-- oops, not less than or equal to, the other way around-- max is. 

Did that make sense? I took a few tries to get that right. But loop until your max value is essentially almost less than or equal to your minimum, right? That's when you know that you've converged. AUDIENCE: When would your maximum value be less than the minimum? ANDI PENG: If you keep adjusting it, which is what we are going to be doing in this. Does that make sense? Minimum and max are just integers that we are probably going to want to create to keep track of where we're looking. Because the array exists regardless of what we're doing. Like, we're not actually physically chopping off the array, right? We're just adjusting where we're looking. Does that make sense? 

AUDIENCE: Yeah. 

ANDI PENG: OK. So if that's the condition for our loop, what do we want inside of this loop? What are we going to be wanting to do? So right now, we've got a max and a min, right, probably created up here somewhere. We're going to probably want to find a middle, right? How are we going to be able to find the middle? What's the mathematical-- AUDIENCE: Max plus min divided by 2. ANDI PENG: Exactly. Does that make sense? And do you guys see why we didn't just use-- why we did this instead of doing just n divided by 2? It's because n is a value that's going to stay the same. Right? But as we adjust our minimum and maximum values, they're going to change. And as a result, our middle is going to change too. So that's why we want to do this right here. OK. 

And then, now that we've found our-- yeah. 

AUDIENCE: Just a quick question-- when you say min and max, are we assuming that it's already sorted? 

ANDI PENG: Yeah, that's actually a precondition for a binary search, that you have to know it's sorted. Which is why sort, you write in your problem set before your binary search. OK. So now that we know where our midpoint is, what do you want to do here? 

AUDIENCE: We want to compare that to the other one. ANDI PENG: Exactly. So you're going to compare mid to value, right? And what does that tell us when we compare? What do we want to do afterwards? 

AUDIENCE: If the value is larger than the mid, we want to cut it off. ANDI PENG: Exactly. So if the value is larger than the mid, we're going to want to change these minimum and maxes, right? What do we want to change? So if we know the value is somewhere in here, what do you we to change? We want to change our minimum to be mid, right? And then else, if it's in this half, what do we want to change? 

AUDIENCE: Your maximum. ANDI PENG: Yeah. And then you're just going to keep looping, right? Because now, after one iteration through, you've got a max here. And then you can recalculate a mid. And then you can compare. And you're going to keep going until the mins and the maxes have essentially converged. And that's when you know that you've hit the end of it. And either you've found it or you haven't at that point. 

Does this make sense to everybody? OK. This is pretty important, because you'll have to write this in your code tonight. But you guys have a pretty good sense of what you should be doing, which is good. OK. So we've got about seven minutes left section. So we're going to talk about this pset that we'll be doing. So the pset is divided into two halves. The first half involves implementing a find in which you write a linear search, a binary search, and a sorting algorithm. 

So this is the first time in a pset where we'll be giving you guys what's called distribution code, which is code that we have pre-written, but just left some pieces off for you to finish writing. So you guys, when you look at this code, you might get really scared. If you're just like, ahh, I don't know what that's doing, I don't know, like, that seems so complicated, ahh, relax. It's OK. Read the spec. The spec will explain to you exactly what all of these programs are doing. 

For example, generate.c is a program that will come with your pset. You don't actually have to touch it, but you should understand what it's doing. And generate.c, all it's doing is either generating random numbers or you can give it a seed, like a prearranged number that it takes, and it generates more numbers. So there's a specific way to implement generate.c in which you can just make a bunch of numbers for you to test your other methods on. 

So if you wanted to, for example, test your find, you would want to run generate.c, generate a bunch of numbers, and then run your helpers function. Your helpers function is where you're actually physically writing code. And think of helpers as a library file you're writing that find is calling. And so within helpers.c, you'll do searching and sorting. 

And then you're going to essentially just put them all together. The spec will tell you how to put that on the command line. And you'll be able to test whether or not your sort and search are working. Cool. Has anyone already started and encountered problems or questions they have right now with this? OK. 

AUDIENCE: Wait. I have a question. 

ANDI PENG: Yeah. 

AUDIENCE: So I started doing the linear search in helpers.c and it wasn't really working. But then later, I found out we just have to delete it and do binary search. So does it matter if it doesn't work? 

ANDI PENG: Short answer is no. But since we're not-- AUDIENCE: But no one's actually checking. ANDI PENG: We're never going to see that. But you probably want to make sure your search is working. Because if your linear search doesn't work, then chances are your binary search isn't going to work as well. Because you have similar logic in both of them. And no, it doesn't really matter. So the only ones you'll turn in are sort and binary search. Yeah. 

And also, a lot of kids were trying to compile helpers.c. You're not actually allowed to do that, because helpers.c doesn't have a main function. And so you should only be actually compiling generate and find, because find calls helpers.c and the functions within it. So that makes debugging a pain in the butt. But that's what we have to do. AUDIENCE: You just make all, right? ANDI PENG: You can just make all as well, yeah. OK. So that's it in terms of what the pset is asking you all to do. If you have any questions, feel free to ask me after section. I'll be here for, like, 20 minutes. 

And yeah, the pset's really not that bad. You guys should be OK. These, just follow guidelines. Kind of have a sense of, logically, what should be happening and you'll be fine. Don't be too scared. There's a lot of code already written there. Don't be too scared if you don't understand what all of that means. If it's a lot, it's totally fine. And come to office hours. We'll help you take a look. 

AUDIENCE: With the extra functions, do we look those up? 

ANDI PENG: Yeah, those are in the code. In the game of 15, half of it's already written for you. So those functions are already in the code. Yep. All right. Well, best of luck. It's a disgusting day. So hopefully you guys don't feel too bad about staying inside and coding.