[Review] [Quiz 0] 

[Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University] 

[This is CS50.] [CS50.TV] 

Hey, everyone.  Welcome to the review session for Quiz 0, which is taking place this Wednesday. What we're going to do tonight, I'm with 3 other TFs, and together we're going to go through a review of what we've done in the course so far. It's not going to be 100% comprehensive, but it should give you a better idea of what you already have down and what  you still need to study before Wednesday. And feel free to raise your hand with questions as we're going along, but keep in mind that we'll also have a little bit of time at the end— if we get through with a few minutes to spare—to do general questions, so keep that in mind, and so we're going to start at the beginning with Week 0. 

[Quiz 0 Review!] [Part 0] [Lexi Ross] But before we do that let's talk about the logistics of the quiz. 

[Logistics] [Quiz takes place on Wednesday 10/10 in lieu of lecture]  

[(See http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf for details)] It is on Wednesday, October 10th.  

That's this Wednesday, and if you go to this URL here, which is also accessible from CS50.net—there's a link to it— you can see information about where to go based on  your last name or school affiliation as well as it tells about exactly what the quiz will cover and the types of questions that you're going to get. Keep in mind that you'll also have a chance to review for the quiz in section, so your TFs should be going over some practice problems, and that's another good chance to see where you still need to study up for the quiz. Let's start at the beginning with Bits 'n' Bytes. Remember a bit is just a 0 or a 1,  and a byte is a collection of 8 of those bits. Let's look at this collection of bits right here. We should be able to figure out how many bits there are. Where we count there's just 8 of them, eight 0 or 1 units. And since there's 8 bits, that's 1 byte, and let's convert it to hexadecimal.  Hexadecimal is base 16, and it's pretty easy to convert a number in binary, which is what that is, to a number in hexadecimal. All we do is we look at groups of 4,  and we convert them to the appropriate hexadecimal digit. We start with the right-most group of 4, so 0011. That's going to be one 1 and one 2, so together that makes 3. And then let's look at the other block of 4. 1101. That's going to be one 1, one 4, and one 8. Together that's going to be 13, which makes D. And we'll remember that in hexadecimal we don't just go 0 through 9. We go 0 through F, so after 9, 10 corresponds to A, 11 to B, et cetera where F is 15. Here 13 is a D, so to convert it to decimal all we do is we actually  treat each position as a power of 2. That's one 1, one 2, zero 4s, zero 8s, one 16, et cetera, and it's a little hard to compute in your head, but if we go to the next slide we can see the answer to that.  

Essentially we're going across from right back to left, and we're multiplying each digit by the corresponding power of 2. And remember, for hexadecimal we denote these numbers with 0x at the beginning so we don't confuse it with a decimal number. Continuing on, this is an ASCII Table, and what we use ASCII for is to map from characters to numerical values. Remember in the cryptography pset we made extensive use of the ASCII Table in order to use various methods of cryptography,  the Caesar and the Vigenère cipher, to convert different letters in a string according to the key given by the user. Let's look at a little bit of ASCII math. Looking at 'P' + 1, in character form that would be Q, and remember that '5' ≠ 5. And how exactly would we convert between those 2 forms? It's not actually too hard. In order to get 5 we subtract  '0' because there are 5 places between the '0' and the '5.' In order to go the other way we just add the 0, so it's sort of like regular arithmetic.  Just remember that when something has quotes around it it's a character and thus corresponds to a value in the ASCII table. Moving into more general computer science topics. We learned what an algorithm is and how we use programming to implement algorithms. Some examples of algorithms are something really simple like  checking whether a number is even or odd. For that remember we mod the number by 2 and check if the result is 0. If so, it's even. If not, it's odd. And that's an example of a really basic algorithm. 

A little bit of a more involved one is binary search, which we'll go over later in the review session. And programming is the term we use for taking an algorithm and converting it to code the computer can read. 2 examples of programming is Scratch, which is what we did in Week 0. Even though we don't actually type out the code it's a way of implementing this algorithm, which is printing the numbers 1-10, and here we do the same in the C programming language. These are functionally equivalent, just written in different languages or syntax. We then learned about boolean expressions, and a boolean is a value that's either true or false, and here oftentimes boolean expressions go inside of conditions, so if (x ≤ 5), well, we already set x = 5, so that condition is going to evaluate to true. And if it's true, whatever code is beneath the condition is going to be evaluated by the computer, so that string is going to be printed to standard output, and the term condition refers to whatever is inside the parentheses of the if statement. Remember all the operators. Remember it's && and | | when we're trying to combine 2 or more conditions, == not = to check whether 2 things are equal. Remember that = is for assignment whereas == is a boolean operator. ≤, ≥ and then the final 2 are self-explanatory. A general review of boolean logic here.  And boolean expressions are also important in loops,  which we'll go over now. We learned about 3 types of loops so far in CS50, for, while, and do while. And it's important to know that while for most purposes we can actually use any type of loop generally there are certain types of purposes or common patterns in programming that specifically call for one of these loops that make it the most efficient or elegant to code it in that way. Let's go over what each of these loops tends to be used for most often. 

In a for loop we generally already know how many times we want to iterate. That's what we put in the condition. For, i = 0, i < 10, for  example. We already know that we want to do something 10 times. Now, for a while loop, generally we don't necessarily  know how many times we want the loop to run. But we do know some sort of condition that we want it to always be true or always be false. For example, while is set. Let's say that's a boolean variable. While that's true we want the code to evaluate,  so a little bit more extensible, a little bit more general than a for loop, but any for loop can also be converted to a while loop. Finally, do while loops, which may be the trickiest to comprehend right away, are often used when we want to evaluate the code first before the first time we check the condition. A common use case for a do while loop is when you want to get user input, and you know you want to ask the user for input at least once, but if they don't give you good input right away you want to keep asking them until they give you the good input. That's the most common use of a do while loop, and let's look at the actual structure of these loops. They typically always tend to follow these patterns. 

On the for loop inside you have 3 components: initialization, typically something like int i = 0 where i is the counter,  condition, where we want to say run this for loop as long as this condition still holds, like i < 10, and then finally, update, which is how we increment  the counter variable at each point in the loop. A common thing to see there is just i++, which means increment i by 1 every time. You could also do something like i+ = 2, which means add 2 to i each time you go through the loop. And then the do this just refers to any code that actually runs as part of the loop. And for a while loop, this time we actually have the initialization outside of the loop, so for example, let's say we're trying to do the same type of loop as I just described. We would say int i = 0 before the loop begins. Then we could say while i < 10 do this, so the same block of code as before, and this time the update part of the code, for example, i++, actually goes inside of the loop. And finally, for a do while, it's similar to the while loop, but we have to remember that the code will evaluate once before the condition is checked, so it makes a lot more sense if you look at it in order of top to bottom. In a do while loop the code evaluates before you even look at the while condition, whereas a while loop, it checks first. Statements and variables. When we want to create a new variable we first want to initialize it. 

For example, int bar initializes the variable bar, but it doesn't give it a value, so what is bar's value now? We don't know.  It could be some garbage value that was previously stored in memory there, and we don't want to use that variable until we actually give it a value,  so we declare it here.  Then we initialize it to be 42 below. Now, of course, we know this can be done on one line, int bar = 42. But just to be clear the multiple steps that are going on, the declaration and the initialization are happening separately here. It happens on one step, and the next one, int baz = bar + 1, this statement below, that increments baz, so at the end of this code block if we were to print the value of baz it would be 44 because we declare and initialize it to be 1 > bar,  and then we increment it once more with the ++. We went over this pretty briefly, but it's good to have a general  understanding of what threads and events are. We mainly did this in Scratch, so you can think of threads as multiple sequences of code running at the same time. In actuality, it probably isn't running at the same time, but sort of abstractly we can think of it in that way. 

In Scratch, for example, we had the multiple sprites. It could be executing different code at the same time. One could be walking while the other is saying something  in a different part of the screen. Events are another way of separating out the logic between different elements of your code, and in Scratch we were able to simulate events using the Broadcast, and that's actually When I Receive, not When I Hear, but essentially it's a way to transmit information from one sprite to another. For example, you may want to transmit game over, and when another sprite receives game over, it responds in a certain way. It's an important model to understand for programming. Just to go over the basic Week 0, what we've gone over so far, let's look at this simple C program. The text may be a little bit small from here, but I'll go over it really quick. We're including 2 header files at the top, cs50.h and stdio.h. We're then defining a constant called limit to be 100. We're then implementing our main function. Since we don't use command line arguments here we need to put void as the arguments for main. We see int above main. That's the return type, hence return 0 at the bottom. And we're using CS50 library function get int to ask the user for input, and we store it in this variable x, so we declare x above, and we initialize it with x = GetInt. 

We then check to see if the user gave us good input. If it's ≥ LIMIT we want to return an error code of 1 and print an error message. And finally, if the user has given us good input we're going to square the number and print out that result. Just to make sure that those all hit home you can see the labels of different parts of the code here. I mentioned constant, header files. Oh, int x. Make sure to remember that's a local variable. That contrasts it from a global variable, which we'll talk about  a little bit later in the review session, and we are calling the library function printf,  so if we hadn't included the stdio.h header file we would not be able to call printf. And I believe the arrow that got cut off here is pointing to the %d, which is a formatting string in printf. It says print out this variable as a number, %d. And that is it for Week 0. Now Lucas is going to continue. Hey, guys. My name is Lucas. I'm a sophomore in the best house on campus, Mather,  and I'm going to talk a little bit about Week 1 and 2.1. [Week 1 and 2.1!] [Lucas Freitas] As Lexi was saying, when we started translating your code from Scratch to C one of the things that we noticed is that you cannot just write your code and run it using a green flag anymore. Actually, you have to use some steps to make your C program become an executable file. Basically what you do when you're writing a program is that you translate your idea into a language that a compiler can understand, so when you're writing a program in C what you're doing is actually writing something that your compiler is going to understand, and then the compiler is going to translate that code into something that your computer will understand. 

And the thing is, your computer is actually very dumb. Your computer can only understand 0s and 1s, so actually in the first computers people usually programmed  using 0s and 1s, but not anymore, thank God. We don't have to memorize the sequences for 0s and 1s  for a for loop or for a while loop and so on. That's why we have a compiler. What a compiler does is it basically translates the C code,  in our case, to a language that your computer will understand, which is the object code, and the compiler that we're using is called clang, so this is actually the symbol for clang. When you have your program, you have to do 2 things. First, you have to compile your program, and then you're going to run your program. To compile your program you have a lot of options to do so. The first one is to do clang program.c in which program is the name of your program. In this case you can see they're just saying "Hey, compile my program." You're not saying "I want this name for my program" or anything. 

The second option is giving a name to your program. You can say clang -o and then the name that you want  the executable file to be named as and then program.c. And you can also do make program, and see how in the first 2 cases I put .c, and in the third one I only have programs? Yeah, you actually should not put .c when you use make. Otherwise the compiler is actually going to yell at you. And also, I don't know if you guys remember, but a lot of times we also used -lcs50 or -lm. That is called linking. It just tells the compiler that you will use those libraries right there, so if you want to use cs50.h you actually have to type clang program.c -lcs50. If you don't do that, the compiler is not going to know  that you're using those functions in cs50.h. And when you want to run your program you have 2 options. If you did clang program.c you didn't give a name to your program. You have to run it using ./a.out. A.out is a standard name that clang gives your program if you don't give it a name. Otherwise you're going to do ./program if you gave a name to your program, and also if you did make program the name that a program is going to get is already going to be programmed the same name as the c file. Then we talked about data types and data.  

Basically data types are the same thing as little boxes they use to store values, so data types are actually just like Pokémons. They come in all sizes and types. I don't know if that analogy makes sense. The data size actually depends on the machine architecture. All the data sizes that I'm going to show here  are actually for a 32-bit machine, which is the case of our appliance, but if you are actually coding your Mac or in a Windows also probably you're going to have a 64-bit machine, so remember that the data sizes that I'm going to show here are for the 32-bit machine. The first one that we saw was an int,  which is pretty straightforward. You use int to store an integer. We also saw the character, the char. If you want to use a letter or a little symbol you're probably going to use a char. A char has 1 byte, which means 8 bits, like Lexi said. Basically we have an ASCII Table that has 256  possible combinations of 0s and 1s, and then when you type a char it's going to translate the character that inputs you a number that you have in the ASCII table, like Lexi said. We also have the float, which we use to store decimal numbers. If you want to choose 3.14, for example, you're going to use a float or a double that has more precision. A float has 4 bytes. A double has 8 bytes, so the only difference is the precision. We also have a long that is used for integers, and you can see for a 32-bit machine an int and a long have the same size, so it doesn't really make sense to use a long in a 32-bit machine. 

But if you're using a Mac and 64-bit machine, actually a long has size 8, so it really depends on the architecture. For the 32-bit machine it doesn't make sense to use a long really. And then a long long, on the other hand, has 8 bytes, so it is very good if you want to have a longer integer. And finally, we have string, which is actually a char *,  which is a pointer to a char. It's very easy to think that the size of the string is going to be like  the number of characters that you have there, but actually the char * itself has the size of a pointer to a char, which is 4 bytes. The size of a char * is 4 bytes. It doesn't matter if you have a small word or a letter or anything. It's going to be 4 bytes. We also learned a little bit about casting, so as you can see, if you have, for example, a program that says int x = 3 and then printf("%d", x/2) do you guys know what it's going to print on screen? 

Someone?>>[Students] 2. 1.>>1, yeah. When you do 3/2 it's going to get 1.5, but since we're using an integer it's going to ignore the decimal part, and you're going to have 1. If you don't want that to happen what you can do, for example, is declare a float y = x. Then x that used to be 3 is now going to be 3.000 in y. And then you can print the y/2.  Actually, I should have a 2. over there. It's going to do 3.00/2.00, and you're going to get 1.5. And we have this .2f just to ask for 2 decimal units in the decimal part. If you have .3f it's going to have actually 1.500. If it's 2 it's going to be 1.50. We also have this case here. If you do float x = 3.14 and then you printf x you're going to get 3.14. And if you do x = the int of x, which means treat x as an int and you print x now you're going to have 3.00. Does that make sense? Because you're first treating x as an integer, so you're ignoring the decimal part, and then you're printing x. And finally, you can also do this, int x = 65, and then you declare a char c = x, and then if you print the c you're actually going to get  A, so basically what you're doing here  is translating the integer into the character, just like the ASCII Table does. We also talked about math operators. Most of them are pretty straightforward, so +, -, *, /,  and also we talked about mod, which is the remainder of a division of 2 numbers. If you have 10 % 3, for example, it means divide 10 by 3, and what is the remainder? It's going to be 1, so it's actually very useful for a lot of the programs. For Vigenère and Caesar I'm pretty sure that all of you guys used mod. About math operators, be very careful when combining * and /. 

For example, if you do (3/2) * 2 what are you going to get? [Students] 2. Yeah, 2, because 3/2 is going to be 1.5, but since you're doing operations between 2 integers you're actually just going to consider 1,  and then 1 * 2 is going to be 2, so be very, very careful when doing arithmetic with integers because  you might get that 2 = 3, in that case. And also be very careful about precedence. You should usually use parentheses to be sure that you know what you're doing. Some useful shortcuts, of course, one is i++ or i += 1 or using +=. That is the same thing as doing i = i + 1. You can also do i-- or i -= 1, which is the same thing as i = i -1, something you guys use a lot in for loops, at least. Also, for *, if you use *= and if you do, for example,  i *= 2 is the same thing as saying i = i * 2, and the same thing for division. If you do i /= 2 it's the same thing as i = i/2. 

Now about functions. You guys learned that functions are a very good strategy to save code while you're programming, so if you want to perform the same task in code again and again, probably you want to use a function just so you don't have to copy and paste the code over and over again. Actually, main is a function, and when I show you the format of a function you're going to see that that is pretty obvious. We also use functions from some libraries, for example, printf, GetIn, which is from the CS50 library, and other functions like toupper. All of those functions are actually implemented in other libraries, and when you put those tether files in the beginning of your program you're saying can you please give me the code for those functions so I don't have to implement them by myself? And you can also write your own functions, so when you start programming you realize that libraries don't have all the functions that you need. For the last pset, for example, we wrote draw, scramble, and lookup, and it's very, very important to be able to write functions  because they are useful, and we use them all the time in programming, and it saves a lot of code. The format of a function is this one. We have return type in the beginning. What is the return type? It's just when your function is going to return. If you have a function, for example, factorial,  that is going to calculate a factorial of an integer, probably it's going to return an integer also. Then the return type is going to be int. Printf actually has a return type void because you're not returning anything. You're just printing things to the screen and quitting the function afterwards. Then you have the name of the function that you can choose. You should be a little reasonable, like don't choose a name like xyz or like x2f. Try to make up a name that makes sense. 

For example, if it's factorial, say factorial. If it's a function that is going to draw something, name it draw. And then we have the parameters, which are also called arguments, which are like the resources that your function needs from your code to perform its task. If you want to calculate the factorial of a number probably you need to have a number to calculate a factorial. One of the arguments that you're going to have is the number itself. And then it's going to do something and return the value at the end unless it's a void function. Let's see an example.  If I want to write a function that sums all the numbers in an array of integers, first of all, the return type is going to be int because I have an array of integers. And then I'm going to have the function name like sumArray, and then it's going to take the array itself, to int nums, and then the length of the array so I know how many numbers I have to sum. Then I have to initialize a variable called sum, for example, to 0, and every time I see an element in the array I should add it to sum, so I did a for loop. Just like Lexi said, you do int i = 0, i < length and i++. And for every element in the array I did sum += nums[i],  and then I returned the sum, so it's very simple, and it saves a lot of code if you're using this function a lot of times. Then we took a look at conditions. We have if, else, and else if. Let's see what is the difference between those. Take a look at these 2 codes. What is the difference between them? The first one has—basically the codes want you to tell if a number is +, -, or 0. The first one says if it's > 0 then it's positive. If it's = to 0 then it's 0, and if it's < 0 then it's negative. 

And the other one is doing if, else if, else. The difference between the two is that this one is actually going to check if > 0, < 0 or = 0 three times, so if you have the number 2, for example, it's going to come here and say if (x > 0), and it's going to say yes, so I print positive. But even though I know that it's > 0 and it's not going to be 0 or < 0 I'm still going to do is it 0, is it < 0,  so I'm actually going inside of ifs that I didn't have to because I already know that it's not going to satisfy any of these conditions. I can use the if, else if, else statement. It basically says if x = 0 I print the positive. If it's not, I'm going to also test this. If it's 2 not I'm going to do this. Basically if I had x = 2 you would say  if (x > 0), yes, so print this. Now that I know that it's > 0 and that it satisfied the first if I'm not even going to run this code. The code runs faster, actually, 3 times faster if you use this. We also learned about and and or. I'm not going to go through this because Lexi already talked about them. It's just the && and | | operator. 

The only thing I'll say is be careful when you have 3 conditions. Use parentheses because it's very confusing when you have a condition and another one or another one. Use parentheses just to be sure that your conditions make sense because in that case, for example, you can imagine that it could be the first condition and one or the other or the 2 conditions combined in an and or the third one, so just be careful. And finally, we talked about switches. A switch is very useful when you have a variable. Let's say that you have a variable like n that can be 0, 1, or 2, and for each of those cases you're going to perform a task. You can say switch the variable, and it indicates that the value then is like value1 I'm going to do this, and then I break, which means I'm not going to look at any of the other cases because we already satisfied that case and then value2 and so on, and I also can have a default switch. That means if it doesn't satisfy any of the cases that I had that I'm going to do something else, but that's optional. That's all for me. Now let's have Tommy. All right, this is going to be Week 3-ish. These are some of the topics we'll be covering, crypto, scope, arrays, et cetera. Just a quick word on crypto. We're not going to hammer this home. 

We did this in pset 2, but for the quiz make sure you know the difference between the Caesar cipher and the Vigenère cipher, how both of those ciphers work and what it's like to encrypt and decrypt text using those 2 ciphers. Remember, the Caesar cipher simply rotates each character by the same amount, making sure you mod by the number of letters in the alphabet. And the Vigenère cipher, on the other hand, rotates each character by a different amount, so rather than saying every character rotated by 3 Vigenère will rotate each character by a different amount depending on some keyword  where each letter in the keyword represents some different amount to rotate the clear text by. Let's first talk about variable scope. There are 2 different types of variables. We have local variables, and these are going to be defined outside of main or outside any function or block, and these will be accessible anywhere in your program. If you have a function and in that function is a while loop the big global variable is accessible everywhere. A local variable, on the other hand, is scoped to the place where it is defined.  

If you have a function here, for example, we have this function g,  and inside of g there is a variable here called y, and that means that this is a local variable. Even though this variable is called y and this variable is called y these 2 functions have no idea what each other's local variables are. On the other hand, up here we say int x = 5, and this is outside the scope of any function. It's outside the scope of main, so this is a global variable. That means that inside of these 2 functions when I say x-- or x++ I'm accessing the same x whereby this y and this y are different variables. That's the difference between a global variable and a local variable. As far as design is concerned, sometimes it's probably a better idea to keep variables local whenever you possibly can since having a bunch of global variables can get really confusing. If you have a bunch of functions all modifying the same thing you might forget what if this function accidentally modifies this global, and this other function doesn't know about it,  and it does get pretty confusing as  you get more code. Keeping variables local whenever you possibly can is just good design. Arrays, remember, are simply lists of elements of the same type. Inside of C I can't have a list like 1, 2.0, hello. We just can't do that. 

When we declare an array in C all of the elements have to be of the same type. Here I have an array of 3 integers. Here I have the length of the array, but if I'm just declaring it in this syntax where I specify what all of the elements are I don't technically need this 3. The compiler is smart enough to figure out how big the array should be. Now when I want to get or set the value of an array this is the syntax to do that. This will actually modify the second element of the array because, remember, numbering starts at 0, not at 1. If I want to read that value I can say something like int x = array[1]. Or if I want to set that value, like I'm doing here, I can say array[1] = 4. That time accessing elements by their index or their position or where they are in the array, and that listing starts at 0. We can also have arrays of arrays, and this is called a multi-dimensional array. When we have a multi-dimensional array that means we can have something like rows and columns, and this is just one way of visualizing this or thinking about it. When I have a multi-dimensional array that means I'm going to start needing more than 1 index because if I have a grid just saying what row you're in doesn't give us a number. That's really just going to give us a list of numbers. Let's say I have this array here. I have an array called grid, and I'm saying it's 2 rows and 3 columns, and so this is one way of visualizing it. When I say I want to get the element at [1] [2] that means that because these are rows first and then columns I'm going to jump to row 1 since I said 1. 

Then I'm going to come over here to column 2, and I'm going to get the value 6. Make sense? Multi-dimensional arrays, remember, are technically just an array of arrays. We can have arrays of arrays of arrays. We can keep going, but really one way to think about how this is being laid out and what's going on is to visualize it  in a grid like this. When we pass arrays to functions, they're going to behave  a little bit differently than when we pass regular variables to functions like passing an int or a float. When we pass in an int or char or any of these other data types we just took a look at if the function modifies the value of that variable that change is not going to propagate up to the calling function. With an array, on the other hand, that will happen. If I pass in an array to some function and that function changes some of the elements, when I come back up to the function that called it my array is now going to be different, and the vocabulary for that is arrays are passed by reference, as we'll see later. This is related to how pointers work, where these basic data types,  on the other hand, are passed by value. 

We can think of that as making a copy of some variable and then passing in the copy.  It doesn't matter what we do with that variable. The calling function will not be aware that it was changed. Arrays are just a little bit different in that regard. For example, as we just saw, main is simply a function that can take in 2 arguments. The first argument to the main function is argc, or the number of arguments, and the second argument is called argv,  and those are the actual values of those arguments.  Let's say I have a program called this.c,  and I say make this, and I'm going to run this at the command line. Now to pass in some arguments to my program called this, I could say something like ./this is cs 50. This is what we imagine David to do every day at the terminal. But now the main function inside of that program has these values, so argc is 4. It might be a little confusing because really we're only passing in is cs 50. That's only 3. But remember that the first element of argv or the first argument is the name of the function itself. So that means that we have 4 things here,  and the first element is going to be ./this.  And this will be represented as a string.  Then the remaining elements are what we typed in after the name of the program.  So just as an aside, as we probably saw in pset 2,  remember that the string 50 is ≠ the integer 50.  So we can't say something like, 'int x = argv 3.'  

That's just not going to make sense, because this is a string, and this is an integer.  So if you want to convert between the 2, remember, we're going to  have this magic function called atoi.  That takes a string and returns the integer represented inside of that string.  So that's an easy mistake to make on the quiz, just thinking that this will automatically be the correct type.  But just know that these will always be strings  even if the string only contains an integer or a character or a float.  So now let's talk about running time.  When we have all these algorithms that do all these crazy things,  it becomes really useful to ask the question, "How long do they take?" We represent that with something called asymptotic notation.  So this means that--well, let's say we give our algorithm  some really, really, really big input.  We want to ask the question, "How long is it going to take? How many steps will it take our algorithm to run  as a function of the size of the input?" So the first way we can describe run time is with big O.  And this is our worst-case running time.  So if we want to sort an array, and we give our algorithm an array that's in descending order when it should be in ascending order,  that's going to be the worst case.  This is our upper bound in the maximum length of time our algorithm will take.  On the other hand, this Ω is going to describe best-case running time.  So if we give an already sorted array to a sorting algorithm,  how long will it take to sort it?  And this, then, describes a lower bound on running time.  So here are just some words that describe some common running times.  These are in ascending order.  The fastest running time we have is called constant.  

That means no matter how many elements we give our algorithm,  no matter how big our array is, sorting it  or doing whatever we're doing to the array will always take the same amount of time.  So we can represent that just with a 1, which is a constant.  We also looked at logarithmic run time.  So something like binary search is logarithmic,  where we cut the problem in half every time and then things just get higher from there.  And if you're ever writing an O of any factorial algorithm,  you probably shouldn't consider this as your day job.  When we compare running times it's important to keep in mind these things.  So if I have an algorithm that's O(n), and someone else  has an algorithm of O(2n) these are actually asymptotically equivalent.  So if we imagine n to be a big number like eleventy billion: so when we're comparing eleventy billion to something like eleventy billion + 3,  suddenly that +3 doesn't really make a big difference anymore.  That's why we're going to start considering these things to be equivalent.  So things like these constants here, there's 2 x this, or adding a 3,  these are just constants, and these are going to drop up.  So that's why all 3 of these run times are the same as saying they're O(n).  Similarly, if we have 2 other run times, let's say O(n³ + 2n²), we can add  + n, + 7, and then we have another run time that's just O(n³). again, these are the same thing because these--these are not the same.  These are the same things, sorry. So these are the same because  this n³ is going to dominate this 2n².  

What is not the same thing is if we have run times like O(n³) and O(n²) because this n³ is much larger than this n².  So if we have exponents, suddenly this starts to matter,  but when we're just dealing with factors as we are up here,  then it's not going to matter because they are just going to drop out.  Let's take a look at some of the algorithms we've seen so far and talk about their run time.  The first way of looking for a number in a list, that we saw, was linear search.  And the implementation of linear search is super straightforward.  We just have a list, and we're going to look at every single element in the list  until we find the number we're looking for.  So that means that in the worst case, this O(n).  And the worst case here could be if the element is  the last element, then using linear search we have to look at every single element  until we get to the last one in order to know that it was actually in the list.  We can't just give up halfway and say, "It's probably not there."  With linear search we have to look at the whole thing.  The best-case running time, on the other hand, is constant because in the best case the element we're looking for is just the first one in the list.  So it's going to take us exactly 1 step, no matter how big the list is if we're looking for the first element every time.  

So when you search, remember, it does not require that our list be sorted.  Because we're simply going to look over every single element, and it doesn't really matter  what order those elements are in.  A more intelligent search algorithm is something like binary search.  Remember, the implementation of binary search is when you're going to  keep looking at the middle of the list.  And because we're looking at the middle, we require that the list is sorted or else we don't know where the middle is, and we have to look over the whole list to find it, and then at that point we're just wasting time.  So if we have a sorted list and we find the middle, we're going to compare the middle to the element we're looking for.  If it's too high, then we can forget the right half because we know that if our element is already too high and everything to the right of this element is even higher, then we don't need to look there anymore.  Where on the other hand, if our element is too low,  we know everything to the left of that element is also too low,  so it doesn't really make sense to look there, either.  This way, with every step and every time we look at the midpoint of the list,  we're going to cut our problem in half because suddenly we know  a whole bunch of numbers that can't be the one we're looking for.  

In pseudocode this would look something like this, and because we're cutting the list in half every single time, our worst-case run time jumps from linear to logarithmic.  So suddenly we have log-in steps in order to find an element in a list.  The best-case running time, though, is still constant  because now, let's just say that the element we're looking for is always the exact middle of the original list.  So we can grow our list as big as we want, but if the element we're looking for is at the middle,  then it's only going to take us 1 step.  So that's why we're O(log n) and Ω(1) or constant.  Let's actually run binary search on this list.  So let's say that we're looking for the element 164.  The first thing we are going to do is find the midpoint of this list.  It just so happens that the midpoint is going to fall in between these 2 numbers,  so let's just arbitrarily say, every time the midpoint falls between 2 numbers,  let's just round up.  We just need to make sure we do this every step of the way.  So we're going to round up, and we're going to say that 161 is the middle of our list.  So 161 < 164, and every element to the left of 161  is also < 164, so we know that it's not going to help us at all  to start looking over here because the element we're looking for can't be there.  So what we can do is we can just forget about that whole left half of the list,  and now only consider from the right of the 161 onward.  

So again, this is the midpoint; let's just round up.  Now 175 is too big.  So we know it's not going to help us looking here or here,  so we can just throw that away, and eventually we'll hit the 164.  Any questions on binary search?  Let's move on from searching through an already-sorted list  to actually taking a list of numbers in any order and making that list in ascending order.  The first algorithm we looked at was called bubble sort.  And this would be simpler of the algorithms we saw.  Bubble sort says that when any 2 elements inside the list are out of place,  meaning there is a higher number to the left of a lower number,  then we're going to swap them, because that means that the list will be  "more sorted" than it was before.  And we're just going to continue this process again and again and again until eventually the elements kind of bubble to their correct location and we have a sorted list.  

The run time of this is going to be O(n²). Why? Well, because in the worst case, we're going to take every element, and  we're going to end up comparing it to every other element in the list.  But in the best case, we have an already sorted list, bubble sort's  just going to go through once, say "Nope. I didn't make any swaps, so I'm done." So we have a best-case running time of Ω(n).  Let's run bubble sort on a list.  Or first, let's just look at some pseudocode really quickly.  We want to say we want to keep track of, in every iteration of the loop,  keep track of whether or not we changed any elements.  So the reason for that is, we're going to stop when we have not swapped any elements.  So at the start of our loop we haven't swapped anything, so we'll say that's false.  Now, we're going to go through the list and compare element i to element i + 1 and if it is the case that there is a bigger number to the left of a smaller number,  then we're just going to swap them.  

And then we're going to remember that we swapped an element.  That means that we need to go through the list at least 1 more time because the condition in which we stopped is when the whole list is already sorted,  meaning we have not made any swaps.  So that's why our condition down here is 'while some elements have been swapped.' So now let's just look at this running on a list.  I have the list 5,0,1,6,4.  Bubble sort is going to start all the way at the left, and it's going to compare  the i elements, so 0 to i + 1, which is element 1.  It's going to say, well 5 > 0, but right now 5 is to the left,  so I need to swap the 5 and the 0.  When I swap them, suddenly I get this different list.  Now 5 > 1, so we're going to swap them.  5 is not > 6, so we don't need to do anything here.  But 6 > 4, so we need to swap.  Again, we need to run through the whole list to eventually discover  that these are out of order; we swap them,  and at this point we need to run through the list 1 more time  to make sure that everything's in its order, and at this point bubble sort has finished.  A different algorithm for taking some elements and sorting them is selection sort.  The idea behind selection sort is that we're going to build up a sorted portion of the list 1 element at a time.  

And the way we're going to do that is by building up the left segment of the list.  And basically, every--on each step, we're going to take the smallest element we have left that hasn't been sorted yet, and we're going to move it into that sorted segment.  That means we need to continuously find the minimum unsorted element and then take that minimum element and swap it with whatever  left-most element that is not sorted.  The run time of this is going to be O(n²) because in the worst case we need to compare every single element to every other element.  Because we're saying that if we start at the left half of the list, we need  to go through the entire right segment to find the smallest element.  And then, again, we need to go over the entire right segment and keep going over that over and over and over again.  That's going to be n². We're going to need a for loop inside of another for loop  which suggests n².  In the best case thought, let's say we give it an already sorted list; we actually don't do any better than n².  Because selection sort has no way of knowing that  the minimum element is just the one I happen to be looking at.  It still needs to make sure that this is actually the minimum.  

And the only way to make sure that it's the minimum, using this algorithm,  is to look at every single element again.  So really, if you give it--if you give selection sort an already sorted list,  it's not going to do any better than giving it a list that isn't sorted yet.  By the way, if it happens to be the case that something is O(something) and the omega of something, we can just say more succinctly that it's θ of something.  So if you see that come up anywhere, that's what that just means.  

If something is theta of n², it is both big O(n²) and Ω(n²).  So best case and worst case, it doesn't make a difference,  the algorithm is going to do the same thing every time.  So this is what pseudocode for selection sort could look like.  We're basically going to say that I want to iterate over the list from left to right, and at each iteration of the loop, I'm going to move the minimum element into this sorted portion of the list.  And once I move something there, I never need to look at that element again.  Because as soon as I swap an element in to the left segment of the list, it's sorted because we're doing everything in ascending order by using minimums.  So we said, okay, we're at position i, and we need to look at all of the elements  to the right of i in order to find the minimum.  So that means we want to look from i + 1 to the end of the list.  And now, if the element that we're currently looking at is less than our minimum so far, which, remember, we're starting the minimum off to just be whatever element we're currently at; I'll assume that's the minimum.  If I find an element that's smaller than that, then I'm going to say, okay,  well, I have found a new minimum.  I'm going to remember where that minimum was.  

So now, once I've gone through that right unsorted segment,  I can say I'm going to swap the minimum element with the element that is in position i.  That's going to build up my list, my sorted portion of the list from left to right,  and we don't ever need to look at an element again once it's in that portion.  Once we've swapped it.  So let's run selection sort on this list.  The blue element here is going to be the i, and the red element is going to be the minimum element.  So i starts all the way at the left of the list, so at 5.  Now we need to find the minimum unsorted element.  So we say 0 < 5, so 0 is my new minimum.  

But I can't stop there, because even though we can recognize that 0 is the smallest,  we need to run through every other element of the list to make sure.  So 1 is bigger, 6 is bigger, 4 is bigger.  That means that after looking at all of these elements, I've determined 0 is the smallest.  So I'm going to swap the 5 and the 0.  Once I swap that, I'm going to get a new list, and I know that I never need to look at that 0 again because once I've swapped it, I've sorted it and we're done.  Now it just so happens that the blue element is again the 5,  and we need to look at the 1, the 6 and the 4 to determine that 1  is the smallest minimum element, so we'll swap the 1 and the 5.  Again, we need to look at--compare the 5 to the 6 and the 4,  and we're going to swap the 4 and the 5, and finally, compare  those 2 numbers and swap them until we get our sorted list.  Any questions on selection sort?  Okay. Let's move to the last topic here, and that is recursion.  

Recursion, remember, is this really meta thing where a function  repeatedly calls itself.  So at some point, while our fuction is repeatedly calling itself,  there needs to be some point at which we stop calling ourselves.  Because if we don't do that, then we're just going to continue to do this forever,  and our program is just not going to terminate.  We call this condition the base case.  And the base case says, rather than calling a function again,  I'm just going to return some value.  So once we've returned a value, we've stopped calling ourselves,  and the rest of the calls we've made so far can also return.  The opposite of the base case is the recursive case.  And this is when we want to make another call to the function that we're currently in.  And we probably, although not always, want to use different arguments.  

So if we have a function called f, and f just called take 1 argument,  and we just keep calling f(1), f(1), f(1), and it just so happens that  the argument 1 falls into recursive case, we're still never going to stop.  Even if we have a base case, we need to make sure that eventually we're going to hit that base case.  We don't just keep staying in this recursive case.  Generally, when we call ourselves, we're probably going to have a different argument each time.  Here is a really simple recursive function.  So this will compute the factorial of a number.  Up top here we have our base case.  In the case that n ≤ 1, we're not going to call factorial again.  We're going to stop; we're just going to return some value.  If this is not true, then we're going to hit our recursive case.  Notice here that we're not just calling factorial(n), because that wouldn't be very helpful.  We're going to call factorial of something else.  

And so you can see, eventually if we pass a factorial (5) or something, we're going to call factorial (4) and so on, and eventually we're going to hit this base case.  So this looks good. Let's see what happens when we actually run this.  This is the stack, and let's say that main is going to call this function with an argument (4).  So once factorial sees and = 4, factorial will call itself.  Now, suddenly, we have factorial(3).  So these functions are going to keep growing until eventually we hit our base case.  At this point, the return value of this is the return(n x the return value of this),  the return value of this is n x the return value of this.  Eventually we need to hit some number.  At the top here, we say return 1.  That means that once we return that number, we can pop this off the stack.  So this factorial(1) is done.  When 1 returns, this factorial(1) returns, this return to 1.  The return value of this, remember, was n x the return value of this.  So suddenly, this guy knows that I want to return 2.  

So remember, return value of this is just n x the return value up here.  So now we can say 3 x 2, and finally, here we can say this is just going to be 4 x 3 x 2.  And once this returns, we get down to a single integer inside of main.  Any questions on recursion?  All right. So there's more time for questions at the end, but now Joseph will cover the remaining topics.  

[Joseph Ong] All right. So now that we've talked about recursions,  let's talk a little bit about what merge sort is.  Merge sort is basically another way of sorting a list of numbers.  And how it works is, with merge sort you have a list, and what we do is we say, let's split this into 2 halves.  We'll first run merge sort again on the left half,  then we'll run merge sort on the right half,  and that gives us now 2 halves that are sorted, and now we're going to combine those halves together.  It's a bit hard to see without an example, so we'll go through the motions and see what happens.  So you start with this list, we split it into 2 halves.  We run merge sort on the left half first.  So that's the left half, and now we run them through this list again which gets passed into merge sort, and then we look, again,  at the left side of this list and we run merge sort on it.  Now, we get down to a list of 2 numbers,  and now the left half is only 1 element long, and we can't  split a list that's only 1 element into half, so we just say, once we have 50, which is just 1 element, it's already sorted.  

Once we're done with that, we can see that we can  move on to the right half of this list,  and 3 is also sorted, and so now that both halves of this list are sorted we can join these numbers back together.  So we look at 50 and 3; 3 is smaller than 50, so it goes in first and then 50 comes in.  Now, that's done; we go back up to that list and sort it's right half.  42 is it's own number, so it's already sorted.  So now we compare these 2 and 3 is smaller than 42, so that gets put in first,  now 42 gets put in, and 50 gets put in.  Now, that's sorted, we go all the way back to the top, 1337 and 15.  Well, we now look at the left half of this list; 1337 is by itself so it's sorted and same with 15.  So now we combine these 2 numbers to sort that original list, 15 < 1337,  so it goes in first, then 1337 goes in.  And now we sorted both halves of the original list up top.  And all we have to do is combine these.  We look at the first 2 numbers of this list, 3 < 15, so it goes into the sort array first.  15 < 42, so it goes in. Now, 42 < 1337, that goes in.  50 < 1337, so it goes in. And notice that we just took 2 numbers off of this list.  So we're not just alternating between the 2 lists.  We're just looking at the beginning, and we're taking the element that's smaller and then putting it into our array.  Now we've merged all the halves and we're done.  

Any questions about merge sort? Yes?  [Student] If it's splitting into different groups, why don't they just split it once and you have 3 and 2 in a group? [Rest of question unintelligible] The reason--so the question is, why can't we just merge them at that first step after we have them? The reason we can do this, start at the left-most elements of both sides, and then take the smaller one and put it in, is that we know that these  individual lists are in sorted orders.  So if I'm looking at the left-most elements of both halves,  I know they're going to be the smallest elements of those lists.  So I can put them into the smallest element spots of this large list.  On the other hand, if I look at those 2 lists in the second level over there,  50, 3, 42, 1337 and 15, those aren't sorted.  So if I look at 50 and 1337, I'm going to put 50 into my list first.  But that doesn't really make sense, because 3 is the smallest element out of all of those.  So the only reason we can do this combining step is because our lists are already sorted.  Which is why we have to get down all the way to the bottom because when we have just a single number, you know that a single number  in and of itself is already a sorted list.  

Any questions? No? Complexity? Well, you can see that at each step there's end numbers,  and we can divide a list in half log n times,  which is where we get this n x log n complexity.  And you'll see the best case for merge sort is n log n, and it just so happens  that the worst case, or the Ω over there, is also n log n.  Something to keep in mind.  Moving on, let's go on to some super basic file I/O.  If you looked at Scramble, you'll notice we had some sort of system  where you could write to a log file if you read through the code.  Let's see how you might do that.  Well, we have fprintf, which you can think of as just printf,  but just printing to a file instead, and hence the f at the beginning.  This sort of code up here, what it does is, as you might have seen in Scramble,  it goes through your 2-dimensional array printing out row by row what the numbers are.  In this case, printf prints out to your terminal or what we call the standard output of section.  

And now, in this case, all we have to do is replace printf with fprintf,  tell it what file you want to print to, and in this case it just prints it out to that file  instead of printing it out to your terminal.  Well, then that begs the question: Where do we get this sort of file from, right?  We passed log in to this fprintf fuction but we had no idea where it came from.  Well, early in the code, what we had was this chunk of code over here,  which basically says that open the file calls log.txt.  What we do after that is we have to make sure that the file is actually opened successfully.  So it might fail for multiple reasons; you don't have enough space on your computer, for example.  So it's always important before you do any operations with the file  that we check whether that file was opened successfully.  So what that a, that's an argument to fopen, well, we can open a file in many ways.  What we can do is, we can pass it w, which means override the file if it exits already,  We can pass an a, which they append to the end of the file instead of overriding it,  or we can specify r, which means, let's open the file as read-only.  So if the program tries to make any changes to the file,  yell at them and don't let them do it.  Finally, once we're done with the file, done doing operations on it,  we need to make sure we close the file.  And so at the end of your program, you are going to pass them again  this file that you opened, and just close it.  So this is something important that you have to make sure you do.  So remember you can open a file, then you can write to the file,  do operations in the file, but then you have to close the file at the end.  

Any questions on basic file I/O? Yes? [Student question, unintelligible]  Right here. The question is, where does this log.txt file appear?  Well, if you just give it log.txt, it creates it in the same directory as the executable.  So if you're-- >>[Student question, unintelligible] Yes. In the same folder, or in the same directory, as you call it.  Now memory, stack, and heap.  So how is memory laid out in the computer?  Well, you can imagine memory as sort of this block here. And in memory we have what's called the heap stuck over there, and the stack that's down there.  And the heap grows downward and the stack grows upward.  So as Tommy mentioned--oh, well, and we have these other 4 segments which I'll get to in a second-- As Tommy said earlier, you know how his functions call themselves and call each other?  They build up this sort of stack frame. Well, if main calls foo, foo gets put on the stack.  Foo calls bar, bar get's put on the stack, and that gets put on the stack after.  And as they return, they each get taken off the stack.  What do each of these locations and memory hold?  Well, the top, which is the text segment, contains the program itself.  So the machine code, that's there, once you compile your program.  Next, any initialized global variables.  

So you have global variables in your program, and you say like, a = 5,  that gets put in that segment, and right under that,  you have any uninitialized global data, which is just int a,  but you don't say it's equal to anything.  Realize these are global variables, so they're outside of main.  So this means any global variables that are declared but are not initialized.  So what's in the heap? Memory allocated using malloc, which we'll get to in a little bit. And finally, with the stack you have any local variables and any functions you might call in any of their parameters.  The last thing, you don't really have to know what the environment variables do,  but whenever you run program, there is something associated, like this is the username of the person who ran the program.  And that's going to be sort of at the bottom.  In terms of memory addresses, which are hexadecimal values,  the values at the top start at 0, and they go all the way down to the bottom.  In this case, if you're on the 32-bit system,  the address at the bottom is going to be 0x, followed by af, because that's 32 bits,  which is 8 bytes, and in this case 8 bytes corresponds to 8 hexadecimal digits.  So down here you're going to have, like, 0xffffff, and up there you're going to have 0. So what are pointers? Some of you may not have covered this in section before.  but we did go over it in lecture, so a pointer is just a data type  which stores, instead of some sort of value like 50, it stores the address of some location in memory.  Like that memory [unintelligible].  So in this case, what we have is, we have a pointer to an integer or an int *,  and it contains this hexadecimal address of 0xDEADBEEF.  

So what we have is, now, this pointer points at some location in memory,  and that's just a, the value 50 is at this memory location.  On some 32-bit systems, on all 32-bit systems, pointers take up 32 bits or 4 bytes.  But, for example, on a 64-bit system, pointers are 64 bits.  So that's something you'll want to keep in mind.  So on an end-bit system, a pointer is end bits long.  Pointers are sort of hard to digest without extra things,  so let's go through an example of dynamic memory allocation.  What dynamic memory allocation does for you, or what we call malloc,  it lets you allocate some sort of data outside of the set.  So this data is sort of more permanent for the duration of the program.  Because as you know, if you declare x inside of a function, and that function returns,  you no longer have access to the data that was stored in x. What pointers let us do is they let us store memory or store values  in a different segment of memory, namely the heap.  Now once we return out of function, as long as we have a pointer  to that location in memory, then what we can do is we can just look at the values there.  Let's look at an example: This is our memory layout again.  And we have this function, main.  What it does is--okay, so simple, right?--int x = 5, that's just a variable on the stack in main.  

On the other hand, now we declare a pointer which calls the function giveMeThreeInts. And so now we go into this function and we create a new stack frame for it.  However, in this stack frame, we declare int * temp, which in mallocs 3 integers for us. So size of int will give us how many bytes this int is,  and malloc gives us that many bytes of space on the heap.  So in this case, we have created enough space for 3 integers,  and the heap is way up there, which is why I've drawn it higher up.  Once we're done, we come back up here, you only need 3 ints returned,  and it returns the address, in this case over where that memory is.  And we set pointer = switch, and up there we have just another pointer.  But what that function returns is stacked here and disappears.  So temp disappears, but we still maintain the address of where  those 3 integers are inside of mains.  So in this set, the pointers are scoped locally for the stacked frame,  but the memory to which they refer is in the heap.  

Does that make sense?  [Student] Could you repeat that?                          >>[Joseph] Yes.  So if I go back just a little bit, you see that temp allocated  some memory on the heap up there.  So when this function, giveMeThreeInts returns, this stack here is going to disappear.  And with it any of the variables, in this case, this pointer that was allocated in stacked frame.  That is going to disappear, but since we returned temp  and we set pointer = temp, pointer's now going to point the same memory of location as temp was.  So now, even though we lose temp, that local pointer,  we still retain the memory address of what it was pointing to inside of that variable pointer.  Questions? That can be kind of a confusing topic if you haven't gone over it in section.  We can, your TF will definitely go over it and of course we can answer questions  at the end of the review session for this.  But this is sort of a complex topic, and I have more examples that are going to show up that will help clarify what pointers actually are.  

In this case, pointers are equivalent to arrays, so I can just use this pointer as the same thing as an int array.  So I'm indexing into 0, and changing the first integer to 1,  changing the second integer to 2, and the 3rd integer to 3.  So more on pointers. Well, recall Binky.  In this case we've allocated a pointer, or we declared a pointer,  but initially, when I just declared a pointer, it's not pointing to anywhere in memory.  It's just garbage values inside of it.  So I have no idea where this pointer is pointing to.  It has an address which is just filled with 0's and 1's where it was initially declared.  I can't do anything with this until I call malloc on it and then it gives me a little space on the heap where I can put values inside.  Then again, I don't know what's inside of this memory. So the first thing I have to do is check whether the system had enough memory  to give me back 1 integer in the first place, which is why I'm doing this check.  If pointer is null, that means that it didn't have enough space or some other error occurred,  so I should exit out of my program.  But if it did succeed, now I can use that pointer and what * pointer does is it follows where the address is to where that value is, and it sets it equal to 1.  So over here, we're checking if that memory existed.  

Once you know it exists, you can put into it what value you want to put into it; in this case 1.  Once we're done with it, you need to free that pointer because we need to get back to the system that memory that you asked for in the first place.  Because the computer doesn't know when we're done with it.  In this case we're explicitly telling it, okay, we're done with that memory.  If some other process needs it, some other program needs it, feel free to go ahead and take it.  What we can also do is we can just get the address of local variables on the set.  So int x is inside the stacked frame of main.  And when we use this ampersand, this and operator, what it does is  it takes x, and x is just some data in memory, but it has an address.  It's located somewhere. So by calling & x, what this does is it gives us the address of x.  By doing this, we're making pointer point to where x is in memory.  Now we just do something like *x, we're going to get 5 back.  The star is called dereferencing it.  You follow the address and you get the value of it stored there.  

Any questions? Yes?  [Student] If you don't do the 3-pointed thing, does it still compile?  Yes. If you don't do the 3-pointer thing, it's still going to compile, but I'll show you what happens in a second, and without doing that,  that's what we call a memory leak. You're not giving the system  back its memory, so after a while the program is going to accumulate  memory that it's not using, and nothing else can use it.  If you've ever seen Firefox with 1.5 million kilobytes on your computer,  in the task manager, that's what's going on.  You have a memory leak in the program that they're not handling.  So how does pointer arithmetic work?  Well, pointer arithmetic is sort of like indexing into an array.  In this case, I have a pointer, and what I do is I make pointer point to the first element  of this array of 3 integers that I've allocated.  So now what I do, star pointer just changes the first element in the list.  Star pointer +1 points over here.  So pointer is over here, pointer +1 is over here, pointer +2 is over here.  

So just adding 1 is the same thing as moving along this array.  What we do is, when we do pointer +1 you get the address over here,  and in order to get the value in here, you put a star in from the entire expression to dereference it. So, in this case, I'm setting the first location in this array to 1, second location to 2, and third location to 3. Then what I'm doing over here is I'm printing our pointer +1, which just gives me 2. Now I'm incrementing pointer, so pointer equals pointer +1, which moves it forward. And so now if I print out pointer +1, pointer +1 is now 3, which in this case prints out 3. And in order to free something, the pointer that I give it must be pointing at the beginning of the array which I got back from malloc. So, in this case, if I were to call 3 right here, this wouldn't be right, because it's in the middle of the array. I have to subtract to get to the original location the initial first spot before I can free it. So, here's a more involved example. In this case, we're allocating 7 characters in a character array. 

And in this case what we're doing is we're looping over the first 6 of them, and we're setting them to Z. So, for int i = 0, i > 6, i ++,  So, pointer +i will just give us, in this case,  pointer, pointer +1, pointer +2, pointer +3, and so on and so forth in the loop. What it's going to do is it gets that address, dereferences it to get the value, and changes that value to a Z. Then at the end remember this is a string, right? All strings have to end with the null terminating character. So, what I do is in pointer 6 I put the null terminator character in. And now what I'm basically doing over here is implementing printf for a string, right? 

So, when does printf now when it's reached the end of a string? When it hits the null terminating character. So, in this case, my original pointer points to the beginning of this array. I print the first character out. I move it over one. I print that character out. I move it over. And I keep doing this until I reach the end. And now the end *pointer will dereference this and get the null terminating character back. And so my while loop runs only when that value is not the null terminating character. So, now I exit out of this loop. And so if I subtract 6 from this pointer, I go back all the way to the beginning. Remember, I'm doing this because I have to go to the beginning in order to free it. 

So, I know that was a lot. Are there any questions? Please, yes? [Student question unintelligible] Can you say that louder? Sorry. [Student] On the last slide right before you freed the pointer, where were you actually changing the value of the pointer? [Joseph] So, right here. >>[Student] Oh, okay. [Joseph] So, I have a pointer minus minus, right, which moves the thing back one, and then I free it, because this pointer has to be pointed to the beginning of the array. [Student] But that wouldn't be needed had you stopped after that line. [Joseph] So, if I had stopped after this, this would be considered a memory leak, because I didn't run the free. [Student] I [unintelligible] after the first three lines where you had pointer +1 [unintelligible]. [Joseph] Uh-huh. So, what's the question there? Sorry. No, no. Go, go, please. [Student] So, you're not changing the value of pointers. You wouldn't have had to do pointer minus minus. [Joseph] Yes, exactly. So, when I do pointer +1 and pointer +2,  I'm not doing pointer equals pointer +1. So, the pointer just stays pointing at the beginning of the array. It's only when I do plus plus that it sets the value back inside the pointer, that it actually moves this along. All right. More questions? 

Again, if this is sort of overwhelming, this will be covered in session. Ask your teaching fellow about it, and we can answer questions at the end. And usually we don't like to do this minus thing. This has to require me keeping track of how much I've offset in the array. So, in general, this is just to explain how pointer arithmetic works. But what we usually like to do is we like to create a copy of the pointer, and then we'll use that copy when we're moving around in the string. So, in these case you use the copy to print the entire string, but we don't have to do like pointer minus 6 or keep track of how much we moved in this, just because we know that our original point is still pointed to the beginning of the list and all that we altered was this copy. So, in general, alter copies of your original pointer. Don't try to sort of like--don't alter original copies. Trying to alter only copies of your original. So, you notice when we pass the string into printf you don't have to put a star in front of it like we did with all the other dereferences, right? So, if you print out the entire string %s expects is an address, and in this case a pointer or in this case like an array of characters. 

Characters, char*s, and arrays are the same thing. Pointer is to characters, and character arrays are the same thing. And so, all we have to do is pass in pointer. We don't have to pass in like *pointer or anything like that. So, arrays and pointers are the same thing. When you're doing something like x [ y ] over here for an array, what it's doing under the hood is it's saying, okay, it's a character array, so it's a pointer. And so x are the same thing, and so what it does is it adds y to x,  which is the same thing as moving forward in memory that much. And now x + y gives us some sort of address, and we dereference the address or follow the arrow to where that location in memory is and we get the value out of that location in memory. So, so these two are exactly the same thing. It's just a syntactic sugar. They do the same thing. They're just different syntactics for each other. 

So, what can go wrong with pointers? Like, a lot. Okay. So, bad things. Some bad things you can do are not checking if your malloc call returns null, right? In this case, I'm asking the system to give me--what is that number? Like 2 billion times 4, because the size of an integer is 4 bytes. I'm asking it for like 8 billion bytes. Of course my computer is not going to be able to give me that much memory back. And we didn't check if this is null, so when we try to dereference it over there-- follow the arrow to where it's going to--we don't have that memory. This is what we call dereferencing a null pointer. And this essentially causes you to segfault.  This is one of the ways you can segfault. Other bad things you can do--oh well.  That was dereferencing a null pointer. Okay. Other bad things--well, to fix that you just put a check in there that checks whether the pointer is null and exit out of the program if it happens that malloc returns a null pointer. That's the xkcd comic. People understand it now. Sort of. 

So, memory. And I went over this. We're calling malloc in a loop, but every time we call malloc we're losing track of where this pointer is pointing to, because we're clobbering it. So, the initial call to malloc gives me memory over here. My pointer pointers to this. Now, I don't free it, so now I call malloc again. Now it points over here. Now my memory is pointing over here. Pointing over here. Pointing over here. But I've lost track of the addresses of all the memory over here that I allocated. And so now I don't have any reference to them anymore. So, I can't free them outside of this loop. And so in order to fix something like this, if you forget to free memory and you get this memory leak, You have to free the memory inside of this loop once you're done with it. Well, this is what happens. I know lots of you hate this. But now--yay! You get like 44,000 kilobytes. So, you free it at the end of the loop, and that's going to just free the memory every time. Essentially, your program doesn't have a memory leak anymore. 

And now something else you can do is free some memory that you've asked for twice. In this case, you malloc something, you change its value. You free it once because you said you were done with it. But then we freed it again. This is something that's pretty bad. It's not going to initially segfault, but after a while what this does is double freeing this corrupts your heap structure, and you'll learn a little bit more about this if you choose to take a class like CS61. But essentially after a while your computer is going to get confused about what memory locations are where and where it's stored-- where data is stored in memory. And so freeing a pointer twice is a bad thing that you don't want to do. 

Other things that can go wrong is not using sizeof. So, in this case you malloc 8 bytes, and that's the same thing as two integers, right? So, that's perfectly safe, but is it? Well, as Lucas talked about on different architectures, integers are of different lengths. So, on the appliance that you're using, integers are about 4 bytes, but on some other system they might be 8 bytes or they might be 16 bytes. So, if I just use this number over here, this program might work on the appliance,  but it's not going to allocate enough memory on some other system. In this case, this is what the sizeof operator is used for. When we call sizeof(int), what this does is  it gives us the size of an integer on the system that the program is running. So, in this case, sizeof(int) will return 4 on something like the appliance, and now this will 4 * 2, which is 8, which is just the amount of space necessary for two integers. On a different system, if an int is like 16 bytes or 8 bytes, it's just going to return enough bytes to store that amount. 

And finally, structs. So, if you wanted to store a sudoku board in memory, how might we do this? You might think of like a variable for the first thing, a variable for the second thing, a variable for the third thing, a variable for the fourth thing--bad, right? So, one improvement you can make on top of this is to make a 9 x 9 array. That's fine, but what if you wanted to associate other things with the sudoku board like what the difficulty of the board is, or, for example, what your score is, or how much time it's taken you to solve this board? Well, what you can do is you can create a struct. What I'm basically saying is I'm defining this structure over here, and I'm defining a sudoku board which consists of a board that is 9 x 9. 

And what it has it has pointers to the name of the level. It also has x and y, which are the coordinates of where I am right now. It also has time spent [unintelligible], and it has the total number of moves I've inputted so far. And so in this case, I can group a whole bunch of data into just one structure instead of having it like flying around in like different variables  that I can't really keep track of. And this lets us have just nice syntax for sort of referencing different things inside of this struct. I can just do board.board, and I get the sudoku board back. Board.level, I get how tough it is. Board.x and board.y give me the coordinates of where I might be in the board. And so I'm accessing what we call fields in the struct. This defines sudokuBoard, which is a  type that I have. And now we're here. I have a variable called "board" of type sudokuBoard. And so now I can access all the fields that make up this structure over here. 

Any questions about structs? Yes? [Student] For int x, y, you declared both on one line? >>[Joseph] Uh-huh. [Student] So, could you just do that with all of them? Like in x, y comma times that total? [Joseph] Yes, you could definitely do that, but the reason I put x and y on the same line-- and the question is why can we just do this on the same line? Why don't we just put all of these on the same line is x and y are related to each other, and this is just stylistically more correct, in a sense, because it's grouping two things on the same line that like sort of relate to the same thing. And I just split these apart. It's just a style thing. It functionally makes no difference whatsoever. Any other questions on structs? You can define a Pokédex with a struct. A Pokémon has a number and it has a letter, an owner, a type. And then if you have an array of Pokémon , you can make up a Pokédex, right? Okay, cool. So, questions on structs. Those are related to structs. 

Finally, GDB. What does GDB let you do? It lets you debug your program. And if you haven't used GDB, I would recommended watching the short and just going over what GDB is, how you work with it, how you might use it,  and test it on a program. And so what GDB lets you do is it lets pause the [unintelligible] up your program and a practical line. For example, I want to pause execution at like line 3 of my program, and while I'm at line 3 I can print out all the values that are there. And so what we call like pausing in a line  is we call this putting a breakpoint at that line and then we can print out the variables at the state of the program at that time. 

We can then from there step through the program line-by-line. And then we can look at the state of the stack at the time. And so in order to use GDB, what we do is we call clang on the C file, but we have to pass it the -ggdb flag. And once we're done with that we just run gdb on the resulting output file. And so you get some like mass of text like this,  but really all you have to do is type in commands at the beginning. Break main puts a breakpoint at main. List 400 lists the lines of code around line 400. And so in this case you can just look around and say, oh, I want to set a breakpoint at line 397, which is this line, and then your program runs into that step and it's going to break. It's going to pause there, and you can print out, for example, value of low or high. And so there are a bunch of commands you need to know, and this slideshow will go up on the website, so if you just want to reference these or like put them on your cheat sheets, feel free. 

Cool. That was Quiz Review 0, and we'll stick around if you have any questions. All right.  

 [applause] 

[CS50.TV]