ROB BOWDEN: Hi, I'm Rob Bowden, and let's talk about quiz0. So, first question. This is the question where you needed to code the number 127 in the binary bulbs. If you wanted, you could do the regular conversion from bi-- or, from decimal to binary. But that's probably going to take a lot of time. I mean, you could figure out that, OK, 1 is in there, 2 is in there, 4 is in there, 8 is in there. Easier way, 127 is 128 minus one. That leftmost light bulb is the 128-bit. So 127 is really just all of the other light bulbs, since that's the leftmost light bulb minus 1. That's it for that question. 

Question one. So with 3 bits you can represent 8 distinct values. Why, then, is 7 the largest non-negative decimal integer you can represent? Well, if we can only represent 8 distinct values, then what we're going to be representing is 0 through 7. 0 takes up one of the values. 

Question two. With n bits, how many distinct values can you represent? So, with n bits, you have 2 possible values for each bit. So we have 2 possible values for the first bit, 2 possible values for the second, 2 possible for the third. And so that's 2 times 2 times 2, and ultimately the answer is 2 to the n. 

Question three. What's 0x50 in binary? So remember that hexadecimal has a very straightforward conversion to binary. So here, we just need to look at the 5 and the 0 independently. So what's 5 in binary? 0101, that's the 1 bit and the 4 bit. What's 0 in binary? Not tricky. 0000. So just put them together, and that's the full number in binary. 01010000. And if you wanted you could take off that leftmost zero. It's irrelevant. 

So then alternatively, what is 0x50 in decimal? If you wanted, you could-- if you're more comfortable with the binary, you could take that binary answer and convert that into decimal. Or we could just remember that hexadecimal. So that 0 is in the 0-th place, and the 5 is in the 16 to the first place. So here, we have 5 times 16 to the first, plus 0 times 16 to the zero, is 80. And if you looked at the title to the question, it was CS 80, which was kind of a hint to the answer to this problem. 

Question five. We have this Scratch script, which is repeating 4 times peanut butter jelly. So how do we now code that in C? Well, we have here-- the part in bold is the only part you had to implement. So we have a 4 loop that's looping 4 times, printf-ing peanut butter jelly, with new line as the problem asks for. 

Question six, another Scratch problem. We see that we are in a forever loop. We're saying the variable i and then incrementing i by 1. Now we want to do that in C. There are multiple ways we could have done this. Here we happened to code the forever loop as a while (true). So we declare the variable i, just like we had variable i in Scratch. Declare the variable i, and forever while (true), we say the variable i. So printf %i-- or you could've used %d. We say that variable, and then increment it, i++. 

Question seven. Now we want to do something very similar to Mario dot c from problem set one. We want to print these hashtags, we want to print a five by three rectangle of these hashes. So how are we going to do that? Well, we give you a whole bunch of code, and you just have to fill in the print grid function. 

So what does PrintGrid look like? Well you're past the width and the height. So we have an outer 4 loop, that's looping over all of the rows of this grid that we want to print out. Then we have the inter-nested 4 loop, that's printing over each column. So for each row, we print for each column, a single hash. Then at the end of the row we print a single new line to go to the next row. And that's it for the whole grid. 

Question eight. A function like PrintGrid is said to have a side effect, but not a return value. Explain the distinction. So this relies on you remembering what a side effect is. Well, a return value-- we know PrintGrid doesn't have return value, since right here it says void. So anything that returns void doesn't really return anything. So what is the side effect? Well, a side effect is anything that sort of persists after the function ends that wasn't just returned, and it wasn't just from the inputs. 

So, for example, we might change a global variable. That would be a side effect. In this particular case, a very important side effect is printing to the screen. So that is a side effect that PrintGrid has. We print these things to the screen. And you can think of that as a side effect, since that's something that persists after this function ends. That's something outside the scope of this function that ultimately is being changed, the contents of the screen. 

Question nine. Consider the program below, to which line numbers have been added for the sake of discussion. So in this program we are just calling GetString, storing it in this variable s, and then printing that variable s. OK. So explain why line one is present. #include cs50 dot h. Why do we need to #include cs50 dot h? Well we're calling the GetString function, and GetString is defined in the cs50 library. So if we didn't have #include cs50 dot h, we would get that implicit declaration of the GetString function error from the compiler. So we need to include the library-- we need to include the header file, or else the compiler won't recognize that GetString exists. 

Explain why line two is present. So standard io dot h. It's exactly the same as the previous problem, except instead of dealing with GetString, we're talking about printf. So if we didn't say we need to include standard io dot h, then we wouldn't be able to use the printf function, because the compiler wouldn't know about it. 

Why-- what is the significance of void in line four? So here we have int main (void). That's just saying that we aren't getting any command line arguments to main. Remember that we could say int main int argc string argv brackets. So here we just say void to say we are ignoring command line arguments. 

Explain, with respect to memory, exactly what GetString in line six returns. GetString is returning a block of memory, an array of characters. It's really returning a pointer to the first character. Remember that a string is a char star. So s is a pointer to the first character in whatever the string is that the user entered at the keyboard. And that memory happens to be malloced, so that memory is in the heap. 

Question 13. Consider the program below. So all this program is doing is printf-ing 1 divided by 10. So when compiled and executed, this program outputs 0.0, even though 1 divided by 10 is 0.1. So why is it 0.0? Well, this is because of integer division. So 1 is an integer, 10 is an integer. So 1 divided by 10, everything is treated as integers, and in C, when we do integer division, we truncate any decimal point. So 1 divided by 10 is 0, and then we're trying to print that as a float, so zero printed as a float is 0.0. And that's why we get 0.0. 

Consider the program below. Now we're printing 0.1. So no integer division, we're just printing 0.1, but we're printing it to 28 decimal places. And we get this 0.1000, a whole bunch of zeros, 5 5 5, blah blah blah. So the question here is why does it print that, instead of exactly 0.1? 

So the reason here is now floating point imprecision. Remember that a float is only 32 bits. So we can only represent a finite number of floating point values with those 32 bits. Well there's ultimately infinitely many floating point values, and there's infinitely many floating point values in between 0 and 1, and we're obviously able to represent even more values than that. So we have to make sacrifices to be able to represent most values. 

So a value like 0.1, apparently we can't represent that exactly. So instead of representing 0.1 we do the best we can represent this 0.100000 5 5 5. And that's pretty close, but for a lot of applications you have to worry about floating point imprecision, because we just can't represent all floating points exactly. 

Question 15. Consider the code below. We're just printing 1 plus 1. So there is no trick here. 1 plus 1 evaluates to 2, and then we're printing that. This just prints 2. 

Question 16. Now we're printing the character 1 plus the character 1. So why does this not print the same thing? Well the character 1 plus the character 1, the character 1 has ASCII value 49. So this is really saying 49 plus 49, and ultimately this is going to print 98. So this does not print 2. 

Question 17. Complete the implementation of odd below in such a way that the function returns true if n is odd and false if n is even. This is a great purpose for the mod operator. So we take our argument n, if n mod 2 equals 1, well that means that n divided by 2 had a remainder. If n divided by 2 had a remainder, that means that n is odd, so we return true. Else we return false. You also could have done n mod 2 equals zero, return false, else return true. 

Consider the recursive function below. So if n is less than or equal to 1, return 1, else return n times f of n minus 1. So what is this function? Well, this is just the factorial function. This is nicely represented as n factorial. 

So question 19 now, we want to take this recursive function. We want to make it iterative. So how do we do that? Well for the staff solution, and again there's multiple ways you could have done that, we start with this int product equals 1. And throughout this for loop, we're going to be multiplying product to ultimately end up with the full factorial. So for int i equals 2, i is less than or equal to n, i++. 

You might be wondering why i equals 2. Well, remember that here we have to make sure our base case is correct. So if n is less than or equal to 1, we're just returning 1. So over here, we start at i equals 2. Well if i were 1, then the-- or if n were 1, then the for loop wouldn't execute at all. And so we would just return product, which is 1. Similarly, if n were anything less than 1-- if it were 0, negative 1, whatever-- we'd still be returning 1, which is exactly what the recursive version is doing. 

Now, if n is greater than 1, then we're going to do at least one iteration of this loop. So let's say n is 5, then we're going to do product times equals 2. So now product is 2. Now we're going to do product times equals 3. Now it's 6. Product times equals 4, now it's 24. Product times equals 5, now it's 120. So then ultimately, we're returning 120, which is correctly 5 factorial. 

Question 20. This is the one where you have to fill in this table with any given algorithm, anything that we've seen, that fits these algorithmic run times these asymptotic run times. So what is an algorithm that is omega of 1, but big O of n? So there could be infinitely many answers here. The one that we've seen probably most frequently is just linear search. 

So in the best case scenario, the item we're looking for is at the beginning of the list and so in omega of 1 steps, the first thing we check, we just immediately return that we found the item. In the worst case scenario, the item is at the end, or the item isn't in the list at all. So we have to search the entire list, all n elements, and that's why it's o of n. 

So now it's something that's both omega of n log n, and big O of n log n. Well the most relevant thing we've seen here is merge sort. So merge sort, remember, is ultimately theta of n log n, where theta is defined if both omega and big O are the same. Both n log n. 

What's something that's omega of n, and O of n squared? Well, again there's multiple possible answers. Here we happen to say bubble sort. Insertion sort would also work here. Remember that bubble sort has that optimization where, if you are able to get through the entire list without needing to do any swaps, then, well, we can immediately return that the list was sorted to begin with. So in the best case scenario, it's just omega of n. If it's not just a nicely sorted list to begin with, then we have O of n squared swaps. And finally, we have selection sort for n squared, both omega and big O. 

Question 21. What's integer overflow? Well again, similar to earlier, we only have finitely many bits to represent an integer, so maybe 32 bits. Let's say we have a signed integer. Then ultimately the highest positive number we can represent is 2 to the 31 minus 1. So what happens if we try to then increment that integer? Well, we're going to go from 2 to the 31 minus 1, all the way down to negative 2 to the 31. So this integer overflow is when you keep incrementing, and ultimately you can't get any higher and it just wraps all the way back around to a negative value. 

What about a buffer overflow? So a buffer overflow-- remember what a buffer is. It's just a chunk of memory. Something like an array is a buffer. So a buffer overflow is when you try to access memory beyond the end of that array. So if you have an array of size 5 and you try to access array bracket 5 or bracket 6 or bracket 7, or anything beyond the end, or even anything below-- array bracket negative 1-- all of those are buffer overflows. You're touching memory in bad ways. 

Question 23. So in this one you need to implement strlen. And we tell you that you can assume s will not be null, so you don't have to do any check for null. And there are multiple ways you could have done this. Here we just take the straightforward. We start with a counter, n. n is counting how many characters there are. So we start at 0, and then we iterate over the entire list. 

Is s bracket 0 equal to the null terminator character? Remember we're looking for the null terminator character to determine how long our string is. That is going to terminate any relevant string. So is s bracket 0 equal to the null terminator? If it's not, then we're going to look at s bracket 1, s bracket 2. We keep going until we find the null terminator. Once we've found it, then n contains the total length of the string, and we can just return that. 

Question 24. So this is the one where you have to make the trade off. So one thing is good in one way, but in what way is it bad? So here, merge sort tends to be faster than bubble sort. Having said that-- well, there are multiple answers here. But the main one is that bubble sort is omega of n for a sorted list. 

Remember that table we just saw earlier. So bubble sorts omega of n, the best case scenario is it's able to just go over the list once, determine hey this thing is already sorted, and return. Merge sort, no matter what you do, is omega of n log n. So for sorted list, bubble sort's going to be faster. 

Now what about linked lists? So a linked list can grow and shrink to fit as many elements as needed. Having said that-- so usually the direct comparison is going to be a linked list with an array. So even though arrays can easily grow and shrink to fit as many elements as needed, a linked list compared to an array-- an array has random access. We can index into any particular element of the array. 

So for a linked list, we can't just go to the fifth element, we have to traverse from the beginning until we get to the fifth element. And that's going to prevent us from doing something like binary search. Speaking of binary search, binary search tends to be faster than linear search. Having said that-- so, one possible thing is that you can't do binary search on linked lists, you can only do it on arrays. But probably more importantly, you can't do binary search on an array that is not sorted. Upfront you might need to sort the array, and only then can you do binary search. So if your thing isn't sorted to begin with, then linear search might be faster. 

Question 27. So consider the program below, which will be in the next slide. And this is the one where we're going to want to explicitly state the values for various variables. So let's look at that. 

So line one. We have int x equals 1. That's the only thing that's happened. So at line one, we see in our table, that y, a, b, and tmp are all blacked out. So what is x? Well we just set it equal to 1. And then line two, well, we see that y is set to 2, and the table is already filled in for us. So x is 1 and y is 2. 

Now, line three, we're now inside the swap function. What did we pass to swap? We passed ampersand x for a, and ampersand y for b. Where the problem earlier stated that the address of x is 0x10, and the address of y is 0x14. So a and b are equal to 0x10 and 0x14, respectively. 

Now at line three, what are x and y? Well, nothing has changed about x and y at this point. Even though they're inside a main stack frame, they still have the same values they did before. We haven't modified any memory. So x is 1, y is 2. All right. So now we said int tmp equal to star a. So at line four, everything is the same except for tmp. We haven't changed any values of anything except for tmp. We are setting tmp equal to star a. What is star a? Well, a points to x, So star a is going to equal x, which is 1. So everything is copied down, and tmp is set to 1. 

Now the next line. Star a equals star b. So by line five-- well again, everything is the same except whatever star a is. What is star a? Well, we just said star a is x. So we're changing x to equal star b. What is star b? y. b points to y. So star b is y. So we're setting x equal to y, and everything else is the same. So we see in the next row that x is now 2, and the rest are just copied down. 

Now in the next line, star b equals tmp. Well, we just said star b is y, so we're setting y equal to tmp. Everything else is the same, so everything gets copied down. We're setting y equal to tmp, which is one, and everything else is the same. 

Now finally, line seven. We're back in the main function. We're after swap is finished. We have lost a, b, and tmp, but ultimately we aren't changing any values of anything at this point, we just copy x and y down. And we see that x and y are now 2 and 1 instead of 1 and 2. The swap has successfully executed. 

Question 28. Suppose that you encounter the error messages below during office hours next year as a CA or TF. Advise how to fix each of these errors. So undefined reference to GetString. Why might you see this? Well, if a student is using GetString in their code, they have properly hash included cs50 dot h to include the cs50 library. 

Well, what do they need to fix this error? They need to do a dash lcs50 at the command line when they're compiling. So if they don't pass clang dash lcs50, they're not going to have the actual code that implements GetString. 

Question 29. Implicitly declaring library function strlen. Well this now, they haven't done the proper hash include. In this particular case, the header file they need to include is string dot h, and including string dot h, now the student-- now the compiler has access to the declarations of strlen, and it knows that your code is using strlen correctly. 

Question 30. More percent conversions than data arguments. So what is this? Well remember that these percent signs-- how they're relevant to printf. So in printf we might percent-- we might print something like percent i backslash n. Or we might print like percent i, space, percent i, space, percent i. So for each of those percent signs, we need to pass a variable at the end of printf. 

So if we say printf paren percent i backslash n close paren, well, we say that we're going to print an integer, but then we don't pass printf an integer to actually print. So here more percent conversions than data arguments? That's saying that we have a whole bunch of percents, and we don't have enough variables to actually fill in those percents. 

And then definitely, for question 31, definitely lost 40 bytes in one blocks. So this is a Valgrind error. This is saying that somewhere in your code, you have an allocation that is 40 bytes large so you malloced 40 bytes, and you never freed it. Most likely you just need to find some memory leak, and find where you need to free this block of memory. 

And question 32, invalid write of size 4. Again this is a Valgrind error. This doesn't have to do with memory leaks now. This is, most likely-- I mean, it's some sort of invalid memory rights. And most likely this is some sort of buffer overflow. Where you have an array, maybe an integer array, and let's say it's of size 5, and you try to touch array bracket 5. So if you try to write to that value, that's not a piece of memory that you actually have access to, and so you're going to get this error, saying invalid write of size 4. Valgrind is going to recognize you're trying to touch memory inappropriately. 

And that's it for quiz0. I'm Rob Bowden, and this is CS50.