1 00:00:00,000 --> 00:00:02,742 2 00:00:02,742 --> 00:00:05,680 >> SPEAKER 1: Hi everyone. 3 00:00:05,680 --> 00:00:07,530 We are going to get started. 4 00:00:07,530 --> 00:00:09,330 I think people are still going to be filtering in. 5 00:00:09,330 --> 00:00:12,840 But in the interest of time, so we can get you guys out of here on time, 6 00:00:12,840 --> 00:00:14,110 we're going to start. 7 00:00:14,110 --> 00:00:18,780 So welcome to the CS50 Quiz 0 review. 8 00:00:18,780 --> 00:00:23,020 For those of you who haven't realized yet, you have a question on Wednesday. 9 00:00:23,020 --> 00:00:25,700 Woo-hoo. 10 00:00:25,700 --> 00:00:29,780 >> If you haven't started studying yet or haven't realized that this exists yet, 11 00:00:29,780 --> 00:00:34,070 past quizzes and all information about your quiz are on cs50.net/quizzes. 12 00:00:34,070 --> 00:00:38,090 There's some pretty good stuff on there, past quizzes from the last 10 13 00:00:38,090 --> 00:00:43,760 years as well as information about this quiz and topics 14 00:00:43,760 --> 00:00:46,250 that will be covered. 15 00:00:46,250 --> 00:00:48,980 So let's get started. 16 00:00:48,980 --> 00:00:54,240 >> So you guys might remember, the first day of class David had those lamps on. 17 00:00:54,240 --> 00:00:59,650 So essentially, everything that goes on under the hood of a computer is 18 00:00:59,650 --> 00:01:00,860 done in binary. 19 00:01:00,860 --> 00:01:04,080 Binary means what it sounds like, 0's and 1's. 20 00:01:04,080 --> 00:01:09,290 It has two values that can be represented. 21 00:01:09,290 --> 00:01:14,675 >> So just like in the first day of section when David turned on a light 22 00:01:14,675 --> 00:01:21,990 bulb to represent on, or 1, our computer understands binary as 0's and 23 00:01:21,990 --> 00:01:24,110 1's, on or off. 24 00:01:24,110 --> 00:01:25,360 Basics of Binary. 25 00:01:25,360 --> 00:01:29,440 26 00:01:29,440 --> 00:01:32,470 Every place is represented in base two. 27 00:01:32,470 --> 00:01:36,260 So you add 2 to the 0 to the 1 to the 2 all the way up. 28 00:01:36,260 --> 00:01:41,970 >> To calculate what your binary is to decimal, you just follow this equation 29 00:01:41,970 --> 00:01:42,840 type thing. 30 00:01:42,840 --> 00:01:49,510 If you have a 1 in any of those places, you multiply it by whatever 31 00:01:49,510 --> 00:01:53,820 base it's in, add it up, and you get the decimal. 32 00:01:53,820 --> 00:01:57,930 So this is how you count to 5 in binary. 33 00:01:57,930 --> 00:02:01,400 Just like what we were doing on the last slide, this is how you would 34 00:02:01,400 --> 00:02:02,650 represent 1 through 5. 35 00:02:02,650 --> 00:02:05,320 36 00:02:05,320 --> 00:02:09,660 >> Similarly, just like you can add and subtract in decimal or base 10, or 37 00:02:09,660 --> 00:02:13,040 really any base, on can add and subtract in binary. 38 00:02:13,040 --> 00:02:18,400 Exactly what you would expect when you add the two up, if it equals greater 39 00:02:18,400 --> 00:02:24,220 than 1, you carry a 1, make it a 0, and do the addition that way, just 40 00:02:24,220 --> 00:02:29,910 like you would expect with regular decimal or any other base. 41 00:02:29,910 --> 00:02:30,970 Cool. 42 00:02:30,970 --> 00:02:35,140 >> So like I said before, everything that goes on under the hood of our computer 43 00:02:35,140 --> 00:02:37,560 is done in 0's and 1's, or binary. 44 00:02:37,560 --> 00:02:43,470 So how do we express, for example, letters, or numbers, or characters? 45 00:02:43,470 --> 00:02:45,560 And the answer to that is ASCII. 46 00:02:45,560 --> 00:02:49,380 >> ASCII is a mapping between characters that we would normally see in the 47 00:02:49,380 --> 00:02:53,360 English language like A's, B's, C's, underscore, dashes, and 48 00:02:53,360 --> 00:02:54,910 anything like that. 49 00:02:54,910 --> 00:02:57,260 And it maps that to an ASCII value. 50 00:02:57,260 --> 00:03:03,080 An ASCII value is just a number that can be understood by your computer. 51 00:03:03,080 --> 00:03:07,430 And just like you can do addition and subtraction with numbers, you can do 52 00:03:07,430 --> 00:03:10,890 them with ASCII values. 53 00:03:10,890 --> 00:03:14,050 >> So in this example, what will this print out? 54 00:03:14,050 --> 00:03:26,790 55 00:03:26,790 --> 00:03:35,480 Yeah, so just A space B space C space D. Where did my mouse go? 56 00:03:35,480 --> 00:03:39,200 57 00:03:39,200 --> 00:03:43,380 Notice you can define an int at 65. 58 00:03:43,380 --> 00:03:47,080 And when you print that out using percent C, it'll interpret that as a 59 00:03:47,080 --> 00:03:49,330 character and will print out A. 60 00:03:49,330 --> 00:03:52,800 >> Similarly, you can declare it as a char. 61 00:03:52,800 --> 00:03:56,860 And when you print it out using percent C, it'll interpret that as 62 00:03:56,860 --> 00:04:05,240 percent D. And just like you can add a number, you can add characters are 63 00:04:05,240 --> 00:04:06,878 ASCII values, in this case. 64 00:04:06,878 --> 00:04:11,370 65 00:04:11,370 --> 00:04:16,130 >> So a little pointer for everybody. 66 00:04:16,130 --> 00:04:19,610 5, as a string, does not actually equal 5. 67 00:04:19,610 --> 00:04:26,610 So how might we convert the string 5 to the integer 5? 68 00:04:26,610 --> 00:04:28,930 Any ideas? 69 00:04:28,930 --> 00:04:31,630 Yeah. 70 00:04:31,630 --> 00:04:36,720 >> So if we have 5 as a string, we can subtract 0. 71 00:04:36,720 --> 00:04:37,820 And that'll give us 5. 72 00:04:37,820 --> 00:04:41,670 And similarly, if we have 5 as an integer, add that to the string 0. 73 00:04:41,670 --> 00:04:43,112 And that gives us the string 5. 74 00:04:43,112 --> 00:04:46,350 75 00:04:46,350 --> 00:04:48,350 Cool. 76 00:04:48,350 --> 00:04:52,940 >> Now, recall back to lecture one where we talked about algorithms. 77 00:04:52,940 --> 00:04:57,260 So how do we actually want a computer to do interesting things? 78 00:04:57,260 --> 00:05:00,460 You know, just adding and subtracting numbers and printing things out is not 79 00:05:00,460 --> 00:05:01,730 that exciting. 80 00:05:01,730 --> 00:05:04,620 Usually, we want our computer to perform some kind of algorithm. 81 00:05:04,620 --> 00:05:07,820 Something a little more complex than just simple arithmetic. 82 00:05:07,820 --> 00:05:11,930 >> An algorithm is just a step by step set of instructions for how to perform 83 00:05:11,930 --> 00:05:14,640 a certain task-- 84 00:05:14,640 --> 00:05:15,660 just like a recipe. 85 00:05:15,660 --> 00:05:19,990 You might remember the first day of class where David had us count a room 86 00:05:19,990 --> 00:05:22,550 of people and how many people were in the room. 87 00:05:22,550 --> 00:05:24,480 You might be used to counting one by one. 88 00:05:24,480 --> 00:05:25,860 1, 2, 3, 4. 89 00:05:25,860 --> 00:05:28,010 In that case, a linear time algorithm. 90 00:05:28,010 --> 00:05:31,710 >> But David introduced an algorithm for you to count the people in the room 91 00:05:31,710 --> 00:05:37,340 where everyone stands up, you say your number to another person, add that 92 00:05:37,340 --> 00:05:39,200 number up, and one person sits down. 93 00:05:39,200 --> 00:05:40,410 And you repeat that. 94 00:05:40,410 --> 00:05:42,910 That's one type of algorithm. 95 00:05:42,910 --> 00:05:47,520 We can analyze how efficient an algorithm is based on it's run time. 96 00:05:47,520 --> 00:05:49,680 But we'll talk a little bit more about that later. 97 00:05:49,680 --> 00:05:52,740 98 00:05:52,740 --> 00:05:57,090 >> So all algorithms can also be written in pseudocode. 99 00:05:57,090 --> 00:06:01,120 Pseudocode is just an English like syntax used to represent 100 00:06:01,120 --> 00:06:02,420 a programming language. 101 00:06:02,420 --> 00:06:06,070 For example, if we wanted to ask a user to guess my favorite number, we 102 00:06:06,070 --> 00:06:08,390 might have pseudocode as such. 103 00:06:08,390 --> 00:06:09,850 >> Get a users guess. 104 00:06:09,850 --> 00:06:13,570 If the guess is correct, tell them they're correct, else tell them 105 00:06:13,570 --> 00:06:15,560 they're not correct. 106 00:06:15,560 --> 00:06:22,530 And pseudocode is a way of easily representing an idea or an algorithm. 107 00:06:22,530 --> 00:06:26,910 So now we might want to actually write this in the language that the computer 108 00:06:26,910 --> 00:06:27,980 might understanding. 109 00:06:27,980 --> 00:06:35,660 So we could write our pseudocode and interpret that into source code. 110 00:06:35,660 --> 00:06:41,320 >> So far, source code must adhere to a certain syntax of 111 00:06:41,320 --> 00:06:42,490 a programming language. 112 00:06:42,490 --> 00:06:45,430 And so far, in CS50, we've been using mostly c. 113 00:06:45,430 --> 00:06:48,320 So this might be source code for c. 114 00:06:48,320 --> 00:06:51,440 Later on in the course, you night come into contact with other programming 115 00:06:51,440 --> 00:06:52,480 languages like PHP. 116 00:06:52,480 --> 00:06:57,540 Or if you even take other classes, you might do Java, Python, or even OCML. 117 00:06:57,540 --> 00:07:01,570 But in our c program language, this is how we might write the source code for 118 00:07:01,570 --> 00:07:04,760 the pseudocode algorithm that I just described earlier. 119 00:07:04,760 --> 00:07:08,630 120 00:07:08,630 --> 00:07:11,430 >> So how does your computer actually understand that? 121 00:07:11,430 --> 00:07:14,490 Like I said before, it only really understands zeros and ones. 122 00:07:14,490 --> 00:07:17,880 So how does it get from the source code to something that can be 123 00:07:17,880 --> 00:07:18,960 understood? 124 00:07:18,960 --> 00:07:22,920 Well, we have something called a compiler. 125 00:07:22,920 --> 00:07:28,450 >> If you recall back in most of your psets, you had some kind of program 126 00:07:28,450 --> 00:07:30,370 written in a dot c file. 127 00:07:30,370 --> 00:07:32,550 And then you would type make. 128 00:07:32,550 --> 00:07:35,970 So what is make doing? 129 00:07:35,970 --> 00:07:39,970 >> You can type make to compile your program because someone-- 130 00:07:39,970 --> 00:07:42,730 whoever wrote your p set; probably David-- 131 00:07:42,730 --> 00:07:44,190 created a make file. 132 00:07:44,190 --> 00:07:51,320 And that tells make to know to run your compiler, called clang, that will 133 00:07:51,320 --> 00:07:55,560 then compile your source code to object code, which is zeros and ones 134 00:07:55,560 --> 00:07:57,720 that your computer understands. 135 00:07:57,720 --> 00:08:01,610 But a little later on, we will go more in depth about compilers. 136 00:08:01,610 --> 00:08:05,640 137 00:08:05,640 --> 00:08:10,800 >> So recall pset 0, where-- yes, you have a question? 138 00:08:10,800 --> 00:08:11,620 >> AUDIENCE: [INAUDIBLE]? 139 00:08:11,620 --> 00:08:12,490 >> SPEAKER 1: Yes. 140 00:08:12,490 --> 00:08:14,960 I think they actually should be online. 141 00:08:14,960 --> 00:08:15,120 Yeah. 142 00:08:15,120 --> 00:08:16,572 >> AUDIENCE: Is it like [INAUDIBLE]? 143 00:08:16,572 --> 00:08:19,476 144 00:08:19,476 --> 00:08:20,830 >> SPEAKER 1: It is not. 145 00:08:20,830 --> 00:08:25,810 The are on cs50.net/quizzes. 146 00:08:25,810 --> 00:08:32,900 >> AUDIENCE: Slash quizzes, slash 2013, slash 0, and just click through 147 00:08:32,900 --> 00:08:35,956 quizzes 2013 and quiz 0, review section slides. 148 00:08:35,956 --> 00:08:40,380 >> SPEAKER 1: Yeah, so if you guys want to pull it up and look at it on your 149 00:08:40,380 --> 00:08:42,740 own computer, that's fine too. 150 00:08:42,740 --> 00:08:43,130 Say that again. 151 00:08:43,130 --> 00:08:44,546 >> AUDIENCE: [INAUDIBLE]. 152 00:08:44,546 --> 00:08:48,780 >> SPEAKER 1: Yeah, [INAUDIBLE] is the dummy variable. 153 00:08:48,780 --> 00:08:49,644 Oh, yes? 154 00:08:49,644 --> 00:08:51,372 >> AUDIENCE: [INAUDIBLE]? 155 00:08:51,372 --> 00:08:54,300 >> SPEAKER 1: No, strikes are not on the exam. 156 00:08:54,300 --> 00:08:55,950 Sorry, her question was, was strikes on the exam. 157 00:08:55,950 --> 00:08:59,530 And it is not. 158 00:08:59,530 --> 00:09:05,780 So pset 0, you guys should have all implemented something using scratch. 159 00:09:05,780 --> 00:09:13,100 And we learned some basic programming building blocks using scratch. 160 00:09:13,100 --> 00:09:15,590 >> So let's take a look at some of these building blocks 161 00:09:15,590 --> 00:09:18,170 that make up a program. 162 00:09:18,170 --> 00:09:20,570 First is Boolean expression. 163 00:09:20,570 --> 00:09:24,540 Boolean expressions are ones and 0's or anything that has 164 00:09:24,540 --> 00:09:25,700 two possible values. 165 00:09:25,700 --> 00:09:30,320 In this case, true or false, on or off, and yes or no. 166 00:09:30,320 --> 00:09:35,390 An example of a simple, very simple, program that uses a Boolean 167 00:09:35,390 --> 00:09:39,140 expression up here. 168 00:09:39,140 --> 00:09:43,220 >> So in order for Boolean expressions to be useful, we have Boolean operators. 169 00:09:43,220 --> 00:09:48,920 These are operators that can be used to compare certain values. 170 00:09:48,920 --> 00:09:52,820 So we have and or not equal to, less than or equal to, greater than or 171 00:09:52,820 --> 00:09:55,130 equal to, and less than or greater than. 172 00:09:55,130 --> 00:09:59,060 But these operators aren't very useful unless we can combine them into 173 00:09:59,060 --> 00:10:00,320 conditions. 174 00:10:00,320 --> 00:10:04,370 >> So you guys might remember from scratch and from your p sets that we 175 00:10:04,370 --> 00:10:05,400 had conditions. 176 00:10:05,400 --> 00:10:09,710 They are, essentially, like forks in the logic of your program that 177 00:10:09,710 --> 00:10:12,670 executes depending on whether a condition is met. 178 00:10:12,670 --> 00:10:18,150 So one of the conditions that we had used many times in this course is the 179 00:10:18,150 --> 00:10:21,470 if, else, if, and else conditions. 180 00:10:21,470 --> 00:10:24,060 >> Here's an example of how you might use that. 181 00:10:24,060 --> 00:10:28,430 Does anyone know the difference between just using if statements all 182 00:10:28,430 --> 00:10:32,530 the way down verses if, else, if, and else combined? 183 00:10:32,530 --> 00:10:33,013 Yes? 184 00:10:33,013 --> 00:10:34,263 >> AUDIENCE: [INAUDIBLE]. 185 00:10:34,263 --> 00:10:40,741 186 00:10:40,741 --> 00:10:42,160 >> SPEAKER 1: Exactly. 187 00:10:42,160 --> 00:10:50,210 So if I had if all the way down this way, even if this condition returns 188 00:10:50,210 --> 00:10:52,800 true, it will still continue testing the next two. 189 00:10:52,800 --> 00:11:00,120 Whereas, with an else-if, an else statement, if the one returns true, 190 00:11:00,120 --> 00:11:02,640 the others are not tested. 191 00:11:02,640 --> 00:11:05,955 Any questions about that? 192 00:11:05,955 --> 00:11:06,890 Cool. 193 00:11:06,890 --> 00:11:12,240 >> So you use an if-else of an else statement if you know that it can only 194 00:11:12,240 --> 00:11:14,470 be one of these cases. 195 00:11:14,470 --> 00:11:21,550 So we know if x is less than 0, it's definitely not going to be 196 00:11:21,550 --> 00:11:22,890 greater than 0. 197 00:11:22,890 --> 00:11:26,940 198 00:11:26,940 --> 00:11:31,480 >> Next, another building block that we learned are loops. 199 00:11:31,480 --> 00:11:33,310 We have three types of loops. 200 00:11:33,310 --> 00:11:35,830 For loops, while loops, and do while loops. 201 00:11:35,830 --> 00:11:38,730 And generally, when you sit down to write something, you have to decide 202 00:11:38,730 --> 00:11:40,060 which of the three you want to use. 203 00:11:40,060 --> 00:11:41,900 So how do we decide which one? 204 00:11:41,900 --> 00:11:44,920 205 00:11:44,920 --> 00:11:48,790 >> We generally use a for loop if we know how many times we want to iterate 206 00:11:48,790 --> 00:11:53,650 through something or how many times we want to perform a task. 207 00:11:53,650 --> 00:11:58,830 We use while loops if we need some condition to be true to keep running. 208 00:11:58,830 --> 00:12:03,730 And we use do while very similar to while, but we want our code to run at 209 00:12:03,730 --> 00:12:04,880 least one time. 210 00:12:04,880 --> 00:12:09,410 >> So do while, whatever is in the do will always run at least one time. 211 00:12:09,410 --> 00:12:13,120 Whereas, with the while, it may not run at all if the 212 00:12:13,120 --> 00:12:15,490 condition is not satisfied. 213 00:12:15,490 --> 00:12:16,740 Any questions with that? 214 00:12:16,740 --> 00:12:20,480 215 00:12:20,480 --> 00:12:22,860 >> So structure of a for loop. 216 00:12:22,860 --> 00:12:23,620 You guys have all seen this. 217 00:12:23,620 --> 00:12:25,320 You initialize it. 218 00:12:25,320 --> 00:12:26,600 You have some kind of condition. 219 00:12:26,600 --> 00:12:32,340 So, for example, we might initialize as for i equals 0. 220 00:12:32,340 --> 00:12:34,040 i is less than 10. 221 00:12:34,040 --> 00:12:35,442 And i++. 222 00:12:35,442 --> 00:12:39,010 Very simple one that we've done. 223 00:12:39,010 --> 00:12:42,210 >> For a while loop, similarly, you have to have some kind of initialization, 224 00:12:42,210 --> 00:12:44,980 some kind of condition, and some kind of update. 225 00:12:44,980 --> 00:12:51,990 So we can implement our for loop also as a while loop using this. 226 00:12:51,990 --> 00:12:56,000 And similarly with a do while loop, we might have some initialization, 227 00:12:56,000 --> 00:12:58,640 execute something, update it, and then check the condition. 228 00:12:58,640 --> 00:13:03,500 229 00:13:03,500 --> 00:13:05,140 >> So now functions. 230 00:13:05,140 --> 00:13:06,460 We put everything together. 231 00:13:06,460 --> 00:13:10,140 We might want to write some kind of function. 232 00:13:10,140 --> 00:13:12,790 Common function that you might have seen already is main. 233 00:13:12,790 --> 00:13:13,770 Main is a function. 234 00:13:13,770 --> 00:13:16,160 It has a return type, int. 235 00:13:16,160 --> 00:13:18,470 It has a function name, main. 236 00:13:18,470 --> 00:13:20,810 And it has arguments, argc and argv. 237 00:13:20,810 --> 00:13:24,040 So main is just a function. 238 00:13:24,040 --> 00:13:27,230 >> Other functions you might have used, printf-- printf is a function-- 239 00:13:27,230 --> 00:13:29,330 GetInt, toupper. 240 00:13:29,330 --> 00:13:32,010 But these happen to have been implemented for us by 241 00:13:32,010 --> 00:13:33,270 some kind of library. 242 00:13:33,270 --> 00:13:37,400 If you guys remember including this CS50.h library or the 243 00:13:37,400 --> 00:13:38,510 standard I/O library. 244 00:13:38,510 --> 00:13:39,200 Yes, question? 245 00:13:39,200 --> 00:13:41,610 >> AUDIENCE: Is main just inherent in c? 246 00:13:41,610 --> 00:13:44,740 Does it just kind of [INAUDIBLE]? 247 00:13:44,740 --> 00:13:47,370 >> SPEAKER 1: The question is if main is inherent in c. 248 00:13:47,370 --> 00:13:51,460 And yes, all functions have a main function. 249 00:13:51,460 --> 00:13:55,290 It's kind of necessary for the computer to know where to start 250 00:13:55,290 --> 00:13:55,993 running the code. 251 00:13:55,993 --> 00:13:58,108 >> AUDIENCE: So you wouldn't [INAUDIBLE]? 252 00:13:58,108 --> 00:13:59,480 >> SPEAKER 1: No. 253 00:13:59,480 --> 00:14:00,760 Any other questions? 254 00:14:00,760 --> 00:14:03,430 255 00:14:03,430 --> 00:14:04,770 Cool. 256 00:14:04,770 --> 00:14:08,050 So just like you can use a function that's written for you, you can also 257 00:14:08,050 --> 00:14:10,380 write your own function. 258 00:14:10,380 --> 00:14:17,050 This is a function that someone might have written to calculate the volume 259 00:14:17,050 --> 00:14:18,395 of a q, for example. 260 00:14:18,395 --> 00:14:21,300 261 00:14:21,300 --> 00:14:29,500 There's a return type here, in this case int, our function name q and our 262 00:14:29,500 --> 00:14:31,360 list of parameters. 263 00:14:31,360 --> 00:14:34,550 >> And note that you have to write the data type of the parameter you want to 264 00:14:34,550 --> 00:14:38,660 use or else the function doesn't know what kind of 265 00:14:38,660 --> 00:14:41,650 parameter should I be accepting. 266 00:14:41,650 --> 00:14:48,110 So, in this case, we want an integer as our input. 267 00:14:48,110 --> 00:14:50,390 So why might we want to use functions? 268 00:14:50,390 --> 00:14:52,800 >> First of all, great for organization. 269 00:14:52,800 --> 00:14:56,350 They help break up your code into more organized chunks and make 270 00:14:56,350 --> 00:14:57,960 it easier to read. 271 00:14:57,960 --> 00:14:59,760 Simplification. 272 00:14:59,760 --> 00:15:01,740 This is good for design. 273 00:15:01,740 --> 00:15:04,570 When you're reading a piece of code and the main function is really, 274 00:15:04,570 --> 00:15:07,750 really long, it might be harder to reason about what's going on. 275 00:15:07,750 --> 00:15:11,710 So if you break it down into functions, it might be easier to read. 276 00:15:11,710 --> 00:15:12,750 And reuse-ability. 277 00:15:12,750 --> 00:15:16,940 If you have a chunk of code that's being called or run multiple times, 278 00:15:16,940 --> 00:15:20,690 instead of rewriting that code 10 times in your main function, you might 279 00:15:20,690 --> 00:15:21,440 want to reuse it. 280 00:15:21,440 --> 00:15:25,740 And then every time you need to use that piece of code, call the function. 281 00:15:25,740 --> 00:15:30,550 282 00:15:30,550 --> 00:15:35,380 >> So now if we remember back to scratch, we also talked about a few concepts, 283 00:15:35,380 --> 00:15:37,680 one of which is threading. 284 00:15:37,680 --> 00:15:41,120 Thread is the concept of multiple sequences of code 285 00:15:41,120 --> 00:15:43,040 executing at the same time. 286 00:15:43,040 --> 00:15:47,490 So think back to day one where David had you guys count off the number of 287 00:15:47,490 --> 00:15:48,440 people in the room. 288 00:15:48,440 --> 00:15:50,550 >> Essentially, what was going on is all of you guys were 289 00:15:50,550 --> 00:15:52,370 running separate threads. 290 00:15:52,370 --> 00:15:55,540 And those threads were coming together to get some kind of answer. 291 00:15:55,540 --> 00:15:58,890 Similarly, in Scratch, when you have multiple sprites, you might 292 00:15:58,890 --> 00:16:01,070 have a cat and a dog. 293 00:16:01,070 --> 00:16:08,770 And they would be simultaneously running their own scripts. 294 00:16:08,770 --> 00:16:10,020 That is an example of threading. 295 00:16:10,020 --> 00:16:12,860 296 00:16:12,860 --> 00:16:18,000 >> And the other concept that was introduced in scratch was events. 297 00:16:18,000 --> 00:16:22,550 And events are when multiple parts of your code communicate with each other. 298 00:16:22,550 --> 00:16:26,840 In Scratch, this was when you used the broadcast control and the When I 299 00:16:26,840 --> 00:16:29,500 Receive blocks. 300 00:16:29,500 --> 00:16:35,170 >> And also, in Problem Set 4, we saw a little bit of events as well. 301 00:16:35,170 --> 00:16:38,250 You guys might have used the Gevent library. 302 00:16:38,250 --> 00:16:42,450 And there was a function waitForClick in which you were waiting 303 00:16:42,450 --> 00:16:44,300 for the user to click. 304 00:16:44,300 --> 00:16:47,870 And your click, in this case, would be the event and wait for click is your 305 00:16:47,870 --> 00:16:49,120 event handler. 306 00:16:49,120 --> 00:16:53,690 307 00:16:53,690 --> 00:16:58,630 >> And also, throughout running your psets and working on your psets, you 308 00:16:58,630 --> 00:17:01,920 might have come into contact with some of these commands. 309 00:17:01,920 --> 00:17:05,579 This is what you typed into your terminal window or whatever window 310 00:17:05,579 --> 00:17:12,119 that shows up on your g edit to, essentially, navigate your computer. 311 00:17:12,119 --> 00:17:19,440 >> So for example, LS lists the contents of a directory. 312 00:17:19,440 --> 00:17:22,510 Make directory creates a new folder. 313 00:17:22,510 --> 00:17:24,819 CD, change directory. 314 00:17:24,819 --> 00:17:28,400 RM, remove, deletes a file or some directory. 315 00:17:28,400 --> 00:17:31,050 And then remove directory removes a directory. 316 00:17:31,050 --> 00:17:32,300 >> AUDIENCE: [INAUDIBLE]? 317 00:17:32,300 --> 00:17:36,978 318 00:17:36,978 --> 00:17:38,370 >> SPEAKER 1: Yeah, sure. 319 00:17:38,370 --> 00:17:42,530 320 00:17:42,530 --> 00:17:46,040 Sorry, the question was if you would suggest putting this 321 00:17:46,040 --> 00:17:48,840 on the cheat sheet. 322 00:17:48,840 --> 00:17:49,440 It could help. 323 00:17:49,440 --> 00:17:51,490 If you have room, you can put it on. 324 00:17:51,490 --> 00:17:56,170 It's also just generally good enough to remember because when you use it 325 00:17:56,170 --> 00:17:59,060 you might want to just have it memorized. 326 00:17:59,060 --> 00:18:02,750 That'll make your life a lot easier. 327 00:18:02,750 --> 00:18:04,000 Did I answer your question? 328 00:18:04,000 --> 00:18:10,528 329 00:18:10,528 --> 00:18:14,290 >> So now, we talked a little bit briefly about libraries. 330 00:18:14,290 --> 00:18:18,570 But the two main ones that we've been using so far in the course are 331 00:18:18,570 --> 00:18:20,860 standard I/O and cs50. 332 00:18:20,860 --> 00:18:25,410 What kind of things are included in the standard I/O library? 333 00:18:25,410 --> 00:18:28,410 >> Yeah, so far we've used printf. 334 00:18:28,410 --> 00:18:31,150 In cs50, we've used GetInt and GetString. 335 00:18:31,150 --> 00:18:37,200 And the data type string also happens to be declared in this cs50 library. 336 00:18:37,200 --> 00:18:40,250 We'll talk a little more in depth about how libraries work and how they 337 00:18:40,250 --> 00:18:41,870 interact with the rest of your code. 338 00:18:41,870 --> 00:18:46,220 But those are the two main ones that we have come in contact with so far in 339 00:18:46,220 --> 00:18:48,430 the course. 340 00:18:48,430 --> 00:18:50,050 >> Types. 341 00:18:50,050 --> 00:18:58,120 These are good to remember how much each type is represented by or how 342 00:18:58,120 --> 00:19:02,840 many bytes each of type requires-- 343 00:19:02,840 --> 00:19:04,990 int, 4 bytes; char, 1 byte. 344 00:19:04,990 --> 00:19:06,550 Float is 4 bytes. 345 00:19:06,550 --> 00:19:07,782 What is a double? 346 00:19:07,782 --> 00:19:09,032 >> AUDIENCE: [INAUDIBLE]. 347 00:19:09,032 --> 00:19:11,398 348 00:19:11,398 --> 00:19:16,240 >> SPEAKER 1: Yeah, so a float but double the size. 349 00:19:16,240 --> 00:19:17,150 What about a long? 350 00:19:17,150 --> 00:19:18,400 >> AUDIENCE: [INAUDIBLE]. 351 00:19:18,400 --> 00:19:21,614 352 00:19:21,614 --> 00:19:24,680 >> SPEAKER 1: OK. 353 00:19:24,680 --> 00:19:25,410 What is a long? 354 00:19:25,410 --> 00:19:26,660 >> AUDIENCE: [INAUDIBLE]. 355 00:19:26,660 --> 00:19:29,400 356 00:19:29,400 --> 00:19:31,450 >> SPEAKER 1: Yeah, double an int. 357 00:19:31,450 --> 00:19:34,240 358 00:19:34,240 --> 00:19:34,705 Yes. 359 00:19:34,705 --> 00:19:36,100 >> AUDIENCE: [INAUDIBLE]. 360 00:19:36,100 --> 00:19:38,030 >> SPEAKER 1: Long [INAUDIBLE]. 361 00:19:38,030 --> 00:19:41,860 And then a long long is double that. 362 00:19:41,860 --> 00:19:42,814 >> AUDIENCE: No, no. 363 00:19:42,814 --> 00:19:47,107 A long is just an int. 364 00:19:47,107 --> 00:19:50,910 It depends on the architecture before the [INAUDIBLE] 365 00:19:50,910 --> 00:19:52,922 and int have the same size. 366 00:19:52,922 --> 00:19:54,172 [INAUDIBLE]. 367 00:19:54,172 --> 00:19:58,841 368 00:19:58,841 --> 00:20:00,920 >> SPEAKER 1: So a long and an int are the same. 369 00:20:00,920 --> 00:20:02,943 And then a long long is double the int. 370 00:20:02,943 --> 00:20:03,910 Cool. 371 00:20:03,910 --> 00:20:05,550 And then, what is the last type? 372 00:20:05,550 --> 00:20:06,510 >> AUDIENCE: Pointer. 373 00:20:06,510 --> 00:20:10,350 >> SPEAKER 1: Yeah, so we learned a little bit about pointers. 374 00:20:10,350 --> 00:20:14,015 And regardless of what a pointer is pointing to-- it could be a char star 375 00:20:14,015 --> 00:20:15,880 or an int star-- 376 00:20:15,880 --> 00:20:20,530 it's always 4 bytes for a pointer. 377 00:20:20,530 --> 00:20:21,633 Questions about that? 378 00:20:21,633 --> 00:20:22,116 Yes? 379 00:20:22,116 --> 00:20:24,531 >> AUDIENCE: [INAUDIBLE]? 380 00:20:24,531 --> 00:20:29,530 >> SPEAKER 1: So a long and an int are the same in this cs50 appliance. 381 00:20:29,530 --> 00:20:32,302 >> AUDIENCE: The appliance are completely interchangeable. 382 00:20:32,302 --> 00:20:33,510 >> SPEAKER 1: Yeah. 383 00:20:33,510 --> 00:20:36,610 So then a long long is double an int. 384 00:20:36,610 --> 00:20:39,250 >> AUDIENCE: This is the 32 bit? 385 00:20:39,250 --> 00:20:40,620 >> SPEAKER 1: 32 bit, yeah. 386 00:20:40,620 --> 00:20:43,572 >> AUDIENCE: So [INAUDIBLE]? 387 00:20:43,572 --> 00:20:46,790 >> SPEAKER 1: Yes, if it doesn't explicitly say, you 388 00:20:46,790 --> 00:20:47,870 should assume a 32 bit. 389 00:20:47,870 --> 00:20:50,040 >> AUDIENCE: It would say something like assuming an 390 00:20:50,040 --> 00:20:51,498 architecture like the appliance. 391 00:20:51,498 --> 00:20:58,800 392 00:20:58,800 --> 00:21:01,710 For 64 bit, the only things that change are longs and pointers. 393 00:21:01,710 --> 00:21:05,614 They both [INAUDIBLE]. 394 00:21:05,614 --> 00:21:06,590 >> SPEAKER 1: Yes? 395 00:21:06,590 --> 00:21:07,566 >> AUDIENCE: Question. 396 00:21:07,566 --> 00:21:10,982 So on one of the practice quizzes, it asks about an unsigned int. 397 00:21:10,982 --> 00:21:15,374 So how would that be determined from an int [INAUDIBLE]? 398 00:21:15,374 --> 00:21:18,140 >> SPEAKER 1: An unsigned in is also 4 bytes. 399 00:21:18,140 --> 00:21:21,172 But what is different about a signed int and an unsigned int? 400 00:21:21,172 --> 00:21:22,422 >> AUDIENCE: [INAUDIBLE]. 401 00:21:22,422 --> 00:21:24,868 402 00:21:24,868 --> 00:21:25,630 >> SPEAKER 1: Right. 403 00:21:25,630 --> 00:21:27,570 One can represent negative values. 404 00:21:27,570 --> 00:21:28,580 But how does it do that? 405 00:21:28,580 --> 00:21:30,536 >> AUDIENCE: [INAUDIBLE]. 406 00:21:30,536 --> 00:21:36,370 >> SPEAKER 1: Yeah, it saves 1 bit to represent the sign. 407 00:21:36,370 --> 00:21:40,910 408 00:21:40,910 --> 00:21:45,040 The signed has one bit that represents the sign. 409 00:21:45,040 --> 00:21:48,886 And unsigned just is all positives. 410 00:21:48,886 --> 00:21:50,365 >> AUDIENCE: OK. 411 00:21:50,365 --> 00:21:54,230 So you say that a double is twice the size of a float? 412 00:21:54,230 --> 00:21:58,202 >> SPEAKER 1: Double is twice the size of a float, yes. 413 00:21:58,202 --> 00:22:01,639 >> AUDIENCE: How does a pointer to a long long [INAUDIBLE]? 414 00:22:01,639 --> 00:22:06,058 415 00:22:06,058 --> 00:22:10,870 >> SPEAKER 1: So the question is how does the pointer to a long long-- 416 00:22:10,870 --> 00:22:13,800 how is that only four bytes when a long long its 8 bytes. 417 00:22:13,800 --> 00:22:17,310 So remember what is a pointer, essentially, at the very base value. 418 00:22:17,310 --> 00:22:19,046 >> AUDIENCE: [INAUDIBLE]. 419 00:22:19,046 --> 00:22:22,670 >> SPEAKER 1: Yeah, so a pointer is just a memory location. 420 00:22:22,670 --> 00:22:28,040 So it doesn't matter how much space that pointer is pointing to. 421 00:22:28,040 --> 00:22:32,060 It only needs 4 bytes to keep track of that memory location. 422 00:22:32,060 --> 00:22:34,760 423 00:22:34,760 --> 00:22:36,010 Any other questions? 424 00:22:36,010 --> 00:22:39,800 425 00:22:39,800 --> 00:22:41,050 Cool. 426 00:22:41,050 --> 00:22:42,920 427 00:22:42,920 --> 00:22:47,460 >> So the last thing I have is standard output. 428 00:22:47,460 --> 00:22:51,020 You should use them frequently enough that you can remember. 429 00:22:51,020 --> 00:22:54,800 But this is when we use printf, for example. 430 00:22:54,800 --> 00:22:59,260 And we have these placeholders that were called format codes. 431 00:22:59,260 --> 00:23:03,910 >> So percent c char, percent i for int, and we can also use percent d. 432 00:23:03,910 --> 00:23:05,130 It's the same thing. 433 00:23:05,130 --> 00:23:08,200 But, generally, in CS50 we try to use percent i. 434 00:23:08,200 --> 00:23:09,860 Percent f for float. 435 00:23:09,860 --> 00:23:15,620 Percent ld for long long and percent s for string. 436 00:23:15,620 --> 00:23:18,550 >> Similarly, we've been using a few of these escape sequences. 437 00:23:18,550 --> 00:23:22,431 For example, backslash n for new line. 438 00:23:22,431 --> 00:23:26,910 This is just for when you're formatting your code for print f. 439 00:23:26,910 --> 00:23:27,260 Yes? 440 00:23:27,260 --> 00:23:28,906 >> AUDIENCE: What is percent d for? 441 00:23:28,906 --> 00:23:31,850 >> SPEAKER 1: So the question is what is percent d for? 442 00:23:31,850 --> 00:23:33,270 Percent d is for ints. 443 00:23:33,270 --> 00:23:37,392 Percent d and percent i are the same. 444 00:23:37,392 --> 00:23:41,130 >> AUDIENCE: What's the difference between backslash n and backslash r? 445 00:23:41,130 --> 00:23:45,300 >> SPEAKER 1: So the question is what's the difference between backlash n and 446 00:23:45,300 --> 00:23:48,615 backlash r? 447 00:23:48,615 --> 00:23:50,906 I think backslash r is-- 448 00:23:50,906 --> 00:23:54,340 >> AUDIENCE: So backslash r just implies returns to the beginning of the line 449 00:23:54,340 --> 00:23:56,670 without actually going to a new line. 450 00:23:56,670 --> 00:24:01,000 So if you print a backslash r and you go back to the beginning of the line 451 00:24:01,000 --> 00:24:04,005 then you print more stuff, you overwrite the stuff that's already on 452 00:24:04,005 --> 00:24:04,390 [INAUDIBLE]. 453 00:24:04,390 --> 00:24:06,725 Whereas, n actually goes to a new line and goes to [INAUDIBLE]. 454 00:24:06,725 --> 00:24:10,525 455 00:24:10,525 --> 00:24:13,915 >> SPEAKER 1: Well, any other questions? 456 00:24:13,915 --> 00:24:15,430 All right. 457 00:24:15,430 --> 00:24:18,617 I'm going to hand it off to Dan who will continue. 458 00:24:18,617 --> 00:24:25,078 >> [APPLAUSE] 459 00:24:25,078 --> 00:25:08,814 460 00:25:08,814 --> 00:25:09,720 >> DAN: All righty. 461 00:25:09,720 --> 00:25:18,590 So I'll be talking about another wide range of ideas from the class that are 462 00:25:18,590 --> 00:25:23,220 roughly representative of week two and the start of week three starting off 463 00:25:23,220 --> 00:25:28,690 with casting, which is just a way of treating a value of a certain type as 464 00:25:28,690 --> 00:25:30,830 a value of a different type. 465 00:25:30,830 --> 00:25:34,110 So we can do this with chars to ints, floats to ints, and 466 00:25:34,110 --> 00:25:35,360 long longs to double. 467 00:25:35,360 --> 00:25:38,170 468 00:25:38,170 --> 00:25:44,500 >> All of these things can be used as ways of treating some numeric value 469 00:25:44,500 --> 00:25:48,370 minus char as some other numeric value. 470 00:25:48,370 --> 00:25:54,480 So there are some issues with this, of course, which comes when you cast 471 00:25:54,480 --> 00:25:57,860 things like float to ints. 472 00:25:57,860 --> 00:26:00,500 So this is a little weird. 473 00:26:00,500 --> 00:26:03,170 We have a float that is 1.31. 474 00:26:03,170 --> 00:26:05,220 We multiply it by 10,000. 475 00:26:05,220 --> 00:26:08,380 And then we print it as an int. 476 00:26:08,380 --> 00:26:09,630 What does this output? 477 00:26:09,630 --> 00:26:11,600 478 00:26:11,600 --> 00:26:14,020 10,000 times 1.31. 479 00:26:14,020 --> 00:26:18,761 So 13,000, is that the guess? 480 00:26:18,761 --> 00:26:20,685 >> AUDIENCE: I think it's 10,000. 481 00:26:20,685 --> 00:26:24,234 >> DAN: So I'm multiplying it by 10,000 before I'm casting it. 482 00:26:24,234 --> 00:26:25,202 >> AUDIENCE: Oh. 483 00:26:25,202 --> 00:26:27,622 Wouldn't there be one 9 and some 0 numbers? 484 00:26:27,622 --> 00:26:29,270 >> DAN: You might have some weird digits. 485 00:26:29,270 --> 00:26:32,410 486 00:26:32,410 --> 00:26:37,670 So right, it's 1.3 times 10,000. 487 00:26:37,670 --> 00:26:40,040 So that's 13,000. 488 00:26:40,040 --> 00:26:41,313 And this extra weird-- 489 00:26:41,313 --> 00:26:42,160 >> AUDIENCE: 13,100. 490 00:26:42,160 --> 00:26:42,650 >> DAN: 13,100. 491 00:26:42,650 --> 00:26:44,910 Thank you, Rob. 492 00:26:44,910 --> 00:26:46,610 And this extra weirdness-- 493 00:26:46,610 --> 00:26:48,060 this 9,9-- 494 00:26:48,060 --> 00:26:53,860 is simply because this casting ended up rounding down where 495 00:26:53,860 --> 00:26:55,394 it shouldn't have. 496 00:26:55,394 --> 00:26:55,871 Yeah. 497 00:26:55,871 --> 00:26:58,256 >> AUDIENCE: The casting happens after anything else? 498 00:26:58,256 --> 00:27:03,865 >> DAN: So because I have this in print, it does this multiplication before it 499 00:27:03,865 --> 00:27:05,230 does this casting. 500 00:27:05,230 --> 00:27:06,140 >> AUDIENCE: [INAUDIBLE]. 501 00:27:06,140 --> 00:27:11,350 >> DAN: I think it would cast first, yeah, which would be 10,000. 502 00:27:11,350 --> 00:27:12,610 Anything else? 503 00:27:12,610 --> 00:27:13,330 Cool. 504 00:27:13,330 --> 00:27:16,344 So this is 13,099. 505 00:27:16,344 --> 00:27:17,840 Why does this happen? 506 00:27:17,840 --> 00:27:18,900 Imprecision. 507 00:27:18,900 --> 00:27:21,020 >> Floats aren't perfect. 508 00:27:21,020 --> 00:27:27,550 They can only represent numbers to a certain number of significant figures. 509 00:27:27,550 --> 00:27:35,120 So if we print out 8 sig figs on this float, we get a kind of 510 00:27:35,120 --> 00:27:36,800 ugly looking number. 511 00:27:36,800 --> 00:27:45,580 And that's because 1.31 can't accurately be represented by simple 512 00:27:45,580 --> 00:27:49,000 powers of two in the machine. 513 00:27:49,000 --> 00:27:53,530 So it ends up taking the closest guess, which ends up 514 00:27:53,530 --> 00:27:55,710 being a little low. 515 00:27:55,710 --> 00:27:57,730 Make sense? 516 00:27:57,730 --> 00:27:59,110 OK. 517 00:27:59,110 --> 00:28:05,840 >> Now, switched are a different way of doing conditional statements where all 518 00:28:05,840 --> 00:28:09,900 we care about is a single variable. 519 00:28:09,900 --> 00:28:16,570 So in this particular example, we're getting an integer from the user. 520 00:28:16,570 --> 00:28:21,070 And then we're looking at what that integer is. 521 00:28:21,070 --> 00:28:23,500 Presumably, it's number between one and four. 522 00:28:23,500 --> 00:28:24,800 That's what we're asking for. 523 00:28:24,800 --> 00:28:28,450 >> So you do a switch of the variable name. 524 00:28:28,450 --> 00:28:34,290 Then you set up cases of possible values it could be. 525 00:28:34,290 --> 00:28:37,730 So case one, say it's low. 526 00:28:37,730 --> 00:28:41,080 And then you break to get out of the switch condition so 527 00:28:41,080 --> 00:28:43,270 you don't keep going. 528 00:28:43,270 --> 00:28:44,830 >> In the next case-- 529 00:28:44,830 --> 00:28:46,940 so case two and case three-- 530 00:28:46,940 --> 00:28:51,920 if it's case two it just drops down to the first line of code it sees as with 531 00:28:51,920 --> 00:28:55,400 case three until it sees a break. 532 00:28:55,400 --> 00:29:00,430 So the reason you get case one to only print low is because I 533 00:29:00,430 --> 00:29:01,890 have this break here. 534 00:29:01,890 --> 00:29:05,360 If I, say, ignored this break-- if I threw this breakaway-- 535 00:29:05,360 --> 00:29:09,740 it would print low, and then it would print middle, and then it would break. 536 00:29:09,740 --> 00:29:12,200 >> So breaks are an important part of switch conditions and 537 00:29:12,200 --> 00:29:14,340 they should be there. 538 00:29:14,340 --> 00:29:20,070 Any cases that are not stated explicitly are handled by the default 539 00:29:20,070 --> 00:29:26,645 case in the switch and should be cast. 540 00:29:26,645 --> 00:29:31,363 >> AUDIENCE: So 1, 2, 3, and 4 would be n? 541 00:29:31,363 --> 00:29:33,310 >> DAN: Values that n can be. 542 00:29:33,310 --> 00:29:34,654 Yes. 543 00:29:34,654 --> 00:29:35,146 Yeah? 544 00:29:35,146 --> 00:29:37,606 >> AUDIENCE: So when you have that [INAUDIBLE]? 545 00:29:37,606 --> 00:29:44,002 546 00:29:44,002 --> 00:29:46,830 >> DAN: You would print low, and then it would print middle, and 547 00:29:46,830 --> 00:29:47,400 then it would break. 548 00:29:47,400 --> 00:29:50,244 >> AUDIENCE: Why would it print middle if [INAUDIBLE]? 549 00:29:50,244 --> 00:29:54,036 550 00:29:54,036 --> 00:30:00,550 >> DAN: So everything under a case before a break falls under. 551 00:30:00,550 --> 00:30:09,390 So case one print is underneath case one as is this following print. 552 00:30:09,390 --> 00:30:09,890 Yeah? 553 00:30:09,890 --> 00:30:11,140 >> AUDIENCE: [INAUDIBLE]? 554 00:30:11,140 --> 00:30:15,890 555 00:30:15,890 --> 00:30:22,170 >> DAN: So this number is just a particular value that this variable 556 00:30:22,170 --> 00:30:23,420 can take, right? 557 00:30:23,420 --> 00:30:26,740 558 00:30:26,740 --> 00:30:28,490 Does that make sense? 559 00:30:28,490 --> 00:30:28,990 Yeah. 560 00:30:28,990 --> 00:30:31,490 >> AUDIENCE: [INAUDIBLE]? 561 00:30:31,490 --> 00:30:34,130 >> DAN: Yes, case two would print middle and then break. 562 00:30:34,130 --> 00:30:35,380 >> AUDIENCE: [INAUDIBLE]? 563 00:30:35,380 --> 00:30:37,954 564 00:30:37,954 --> 00:30:40,050 >> DAN: I think any? 565 00:30:40,050 --> 00:30:43,855 What other data types can you switch over? 566 00:30:43,855 --> 00:30:46,320 >> AUDIENCE: You can switch over any data types. 567 00:30:46,320 --> 00:30:50,905 But it only means anything over chars and ints and stuff like that, because 568 00:30:50,905 --> 00:30:55,600 if you're switching over a pointer that doesn't really make sense, 569 00:30:55,600 --> 00:30:59,555 switching over loads, if it even let's you do that, because of floating point 570 00:30:59,555 --> 00:31:02,840 in precision, you wouldn't really want to do that anyway. 571 00:31:02,840 --> 00:31:07,320 So pretty much, just ints and chars and stuff like that. 572 00:31:07,320 --> 00:31:12,360 >> DAN: Yeah, it's when you have explicit values that you know, I think, can be 573 00:31:12,360 --> 00:31:14,250 that a switch is actually useful. 574 00:31:14,250 --> 00:31:17,094 575 00:31:17,094 --> 00:31:18,990 Good? 576 00:31:18,990 --> 00:31:21,370 OK. 577 00:31:21,370 --> 00:31:26,180 >> Scope is the range that a declared variable extends. 578 00:31:26,180 --> 00:31:32,190 So in this little chunk of code I have, it would be full of errors. 579 00:31:32,190 --> 00:31:41,450 And the reason is I declared this int i within the scope of this for loop. 580 00:31:41,450 --> 00:31:46,390 And then I'm trying to reference that i outside of that for loop scope. 581 00:31:46,390 --> 00:31:50,330 >> So basically, you can think about scope as anything that you declare 582 00:31:50,330 --> 00:31:59,750 with inside a set of curly braces only exists within those curly braces. 583 00:31:59,750 --> 00:32:04,990 And if you try and use that variable outside of those curly braces, you'll 584 00:32:04,990 --> 00:32:08,356 get an error from the compiler. 585 00:32:08,356 --> 00:32:08,812 Yeah? 586 00:32:08,812 --> 00:32:09,724 >> AUDIENCE: So this one doesn't work? 587 00:32:09,724 --> 00:32:11,790 >> DAN: This doesn't work, yes. 588 00:32:11,790 --> 00:32:17,190 589 00:32:17,190 --> 00:32:18,660 Strings. 590 00:32:18,660 --> 00:32:19,780 String a char*. 591 00:32:19,780 --> 00:32:22,250 They're exactly the same. 592 00:32:22,250 --> 00:32:25,540 They are just pointers to characters. 593 00:32:25,540 --> 00:32:33,000 And any strings that you have should end with backslash zero, which is just 594 00:32:33,000 --> 00:32:34,410 a c convention. 595 00:32:34,410 --> 00:32:36,680 >> It is called the NULL terminator. 596 00:32:36,680 --> 00:32:39,050 And NULL-- 597 00:32:39,050 --> 00:32:41,670 capital N, capital U, capital L, capital L-- 598 00:32:41,670 --> 00:32:44,290 is not the same as the NULL terminator. 599 00:32:44,290 --> 00:32:46,640 This is a pointer. 600 00:32:46,640 --> 00:32:48,280 This is a character. 601 00:32:48,280 --> 00:32:49,530 They are very distinct. 602 00:32:49,530 --> 00:32:50,200 Remember it. 603 00:32:50,200 --> 00:32:52,320 It will be on the quiz, probably. 604 00:32:52,320 --> 00:32:54,040 I haven't seen the quiz. 605 00:32:54,040 --> 00:32:57,880 606 00:32:57,880 --> 00:32:58,840 Yeah? 607 00:32:58,840 --> 00:33:01,232 >> AUDIENCE: So NULL is, say, the pointer? 608 00:33:01,232 --> 00:33:01,995 >> DAN: Yes. 609 00:33:01,995 --> 00:33:05,170 >> AUDIENCE: What does [INAUDIBLE]? 610 00:33:05,170 --> 00:33:10,050 >> DAN: If, say, malloc is called when you don't have enough memory to get 611 00:33:10,050 --> 00:33:14,400 whatever size you're asking for, malloc will return NULL. 612 00:33:14,400 --> 00:33:19,550 It's, basically, whenever a function is supposed to return a pointer, you 613 00:33:19,550 --> 00:33:22,600 need to check against NULL because NULL is a pretty good-- 614 00:33:22,600 --> 00:33:25,260 it's, sort of, the garbage value. 615 00:33:25,260 --> 00:33:27,050 It's a zero as far as pointers go. 616 00:33:27,050 --> 00:33:29,630 617 00:33:29,630 --> 00:33:32,250 >> Whenever you call a function, that returns a pointer. 618 00:33:32,250 --> 00:33:35,960 You're going to want to check to be sure that that pointer isn't NULL 619 00:33:35,960 --> 00:33:37,760 because NULL is very common. 620 00:33:37,760 --> 00:33:40,160 It's sort of a garbage return. 621 00:33:40,160 --> 00:33:44,902 So if something didn't go right, just return NULL instead. 622 00:33:44,902 --> 00:33:45,898 >> AUDIENCE: [INAUDIBLE]? 623 00:33:45,898 --> 00:33:48,922 >> DAN: Yes, and that's this. 624 00:33:48,922 --> 00:33:51,750 >> AUDIENCE: [INAUDIBLE]? 625 00:33:51,750 --> 00:33:52,800 >> DAN: Spell it as this. 626 00:33:52,800 --> 00:33:54,150 It's the NULL terminator. 627 00:33:54,150 --> 00:33:56,560 It's lowercase N-U-L-L if you're spelling it. 628 00:33:56,560 --> 00:33:59,860 >> AUDIENCE: And I just went back and tested it. 629 00:33:59,860 --> 00:34:03,010 And if you try to put a floating point value into a switch, it'll yell at you 630 00:34:03,010 --> 00:34:05,916 saying, statement requires expression of integer type. 631 00:34:05,916 --> 00:34:07,166 >> DAN: There you go. 632 00:34:07,166 --> 00:34:09,639 633 00:34:09,639 --> 00:34:12,246 But yeah, what was the question again? 634 00:34:12,246 --> 00:34:13,496 >> AUDIENCE: [INAUDIBLE]? 635 00:34:13,496 --> 00:34:16,150 636 00:34:16,150 --> 00:34:23,679 >> DAN: So capital N, capital U, capital L, capital L is an actual c thing. 637 00:34:23,679 --> 00:34:29,719 It is the NULL pointer and will only be treated as such. 638 00:34:29,719 --> 00:34:33,530 You won't ever try and spell the NULL character and see any 639 00:34:33,530 --> 00:34:35,630 other way than this. 640 00:34:35,630 --> 00:34:36,610 Yeah? 641 00:34:36,610 --> 00:34:42,490 >> AUDIENCE: So returning to char max or something in the notes, would it 642 00:34:42,490 --> 00:34:43,960 embody the same function as [INAUDIBLE]? 643 00:34:43,960 --> 00:34:50,655 644 00:34:50,655 --> 00:34:54,949 >> AUDIENCE: So are you referring to returning char max from getchar, or 645 00:34:54,949 --> 00:34:55,444 whatever it is? 646 00:34:55,444 --> 00:34:55,940 >> AUDIENCE: Yeah. 647 00:34:55,940 --> 00:34:58,620 >> AUDIENCE: Yeah, so the general term for all those things 648 00:34:58,620 --> 00:34:59,920 are sentinel values. 649 00:34:59,920 --> 00:35:03,640 So like returning int max from GetInt and char max from getchar, it's 650 00:35:03,640 --> 00:35:06,010 supposed to be like, all right, if these things are returning to us, 651 00:35:06,010 --> 00:35:07,210 something went wrong. 652 00:35:07,210 --> 00:35:09,950 >> For pointers, we just happen to have this sentinel value that everyone 653 00:35:09,950 --> 00:35:10,750 agrees upon. 654 00:35:10,750 --> 00:35:13,210 And this is the thing you return when things go wrong. 655 00:35:13,210 --> 00:35:15,910 So char max is what we're using to represent something 656 00:35:15,910 --> 00:35:18,100 like NULL or getchar. 657 00:35:18,100 --> 00:35:23,420 >> AUDIENCE: So if you're testing getchar, could you just put NULL? 658 00:35:23,420 --> 00:35:23,910 Would that make a difference? 659 00:35:23,910 --> 00:35:25,400 >> DAN: You couldn't just check NULL. 660 00:35:25,400 --> 00:35:30,130 You'd have to check char max because the return value from the function is 661 00:35:30,130 --> 00:35:35,416 a character not a pointer. 662 00:35:35,416 --> 00:35:35,888 Yeah? 663 00:35:35,888 --> 00:35:38,248 >> AUDIENCE: This question asks for the string length. 664 00:35:38,248 --> 00:35:40,136 Does that include the NULL character? 665 00:35:40,136 --> 00:35:41,000 >> DAN: No. 666 00:35:41,000 --> 00:35:45,930 And that's actually how string length knows to stop because it goes through 667 00:35:45,930 --> 00:35:49,070 your array of characters until it sees a NULL character. 668 00:35:49,070 --> 00:35:51,030 And then it's like, all right, I'm done. 669 00:35:51,030 --> 00:35:52,130 >> AUDIENCE: [INAUDIBLE] five? 670 00:35:52,130 --> 00:35:53,990 >> DAN: Hello would be five. 671 00:35:53,990 --> 00:35:55,240 Yep. 672 00:35:55,240 --> 00:35:59,580 673 00:35:59,580 --> 00:36:02,880 So arrays are continuous blocks of memory. 674 00:36:02,880 --> 00:36:08,480 They have instant access by saying the name of the array and then, in curly 675 00:36:08,480 --> 00:36:16,720 braces, whatever index you want to go to, they're indexed from zero through 676 00:36:16,720 --> 00:36:20,100 the length of the array minus 1. 677 00:36:20,100 --> 00:36:23,070 >> And they're declared by the type of the thing that you're storing in the 678 00:36:23,070 --> 00:36:29,750 array, the name of the array, and then whatever the size is of that array. 679 00:36:29,750 --> 00:36:36,660 So this is a char array of length six that has these values. 680 00:36:36,660 --> 00:36:42,050 681 00:36:42,050 --> 00:36:42,700 Yeah? 682 00:36:42,700 --> 00:36:43,950 >> AUDIENCE: [INAUDIBLE]? 683 00:36:43,950 --> 00:36:47,980 684 00:36:47,980 --> 00:36:48,460 >> DAN: Yeah. 685 00:36:48,460 --> 00:36:51,340 >> AUDIENCE: [INAUDIBLE]? 686 00:36:51,340 --> 00:36:56,700 >> DAN: If you have what is going into the array already made. 687 00:36:56,700 --> 00:37:02,260 So you could specify this instead as, say, char, whatever the name of your 688 00:37:02,260 --> 00:37:12,200 array is, empty brackets equals curly brace H comma E comma L comma L comma 689 00:37:12,200 --> 00:37:16,290 O comma NULL character and curly brace. 690 00:37:16,290 --> 00:37:18,180 That would also work as a declaration. 691 00:37:18,180 --> 00:37:20,886 >> AUDIENCE: [INAUDIBLE]? 692 00:37:20,886 --> 00:37:23,110 >> DAN: Then you need to have the size already made. 693 00:37:23,110 --> 00:37:23,896 >> AUDIENCE: [INAUDIBLE]? 694 00:37:23,896 --> 00:37:25,146 >> DAN: Yes. 695 00:37:25,146 --> 00:37:30,114 696 00:37:30,114 --> 00:37:32,420 All righty. 697 00:37:32,420 --> 00:37:36,430 Command line arguments are a way of getting input from the user as 698 00:37:36,430 --> 00:37:39,380 arguments to main. 699 00:37:39,380 --> 00:37:40,600 Main takes two arguments. 700 00:37:40,600 --> 00:37:47,680 The number of arguments that is being passed along the command line and a 701 00:37:47,680 --> 00:37:55,340 string vector or a string array of all of the arguments. 702 00:37:55,340 --> 00:38:07,840 >> So if I, say, called a function such as a dot out 1 space, 2 space, three, 703 00:38:07,840 --> 00:38:10,110 argc would be 4. 704 00:38:10,110 --> 00:38:17,370 And the argv 0 would be a dot out. 705 00:38:17,370 --> 00:38:19,130 Argv1 would be 1. 706 00:38:19,130 --> 00:38:23,030 argv2 would be 2. argv3 would be 3, in that particular case. 707 00:38:23,030 --> 00:38:23,310 Yeah? 708 00:38:23,310 --> 00:38:25,400 >> AUDIENCE: [INAUDIBLE]? 709 00:38:25,400 --> 00:38:34,010 >> DAN: The last element in the array because the array is length argc plus 710 00:38:34,010 --> 00:38:41,050 one of argb, the last element is the NULL pointer. 711 00:38:41,050 --> 00:38:42,580 It is argc plus 1. 712 00:38:42,580 --> 00:38:46,210 713 00:38:46,210 --> 00:38:52,150 So in the case that I just said, it would be argv 0 is a dot out. 714 00:38:52,150 --> 00:38:56,330 argv 1 is 1. argv2 is 2. argv 3 is 3. 715 00:38:56,330 --> 00:39:03,490 argv 4, which is one larger than argc would be NULL. 716 00:39:03,490 --> 00:39:04,870 >> And that's the NULL pointer. 717 00:39:04,870 --> 00:39:06,590 Yes. 718 00:39:06,590 --> 00:39:11,250 And that's because string is a char star is a pointer. 719 00:39:11,250 --> 00:39:14,102 So it has to be the same type. 720 00:39:14,102 --> 00:39:14,595 Yeah? 721 00:39:14,595 --> 00:39:16,074 >> AUDIENCE: Two questions. 722 00:39:16,074 --> 00:39:21,004 So one, what's the difference between this and GetString other than one type 723 00:39:21,004 --> 00:39:22,483 in the user engine? 724 00:39:22,483 --> 00:39:25,934 And two, is it stored within your recent memory? 725 00:39:25,934 --> 00:39:28,399 So like, GetString would be [INAUDIBLE]? 726 00:39:28,399 --> 00:39:31,357 727 00:39:31,357 --> 00:39:33,650 >> DAN: Where is it stored? 728 00:39:33,650 --> 00:39:34,905 I don't know where it's stored. 729 00:39:34,905 --> 00:39:40,000 >> AUDIENCE: So, actually, you know how any function you call it's arguments 730 00:39:40,000 --> 00:39:42,170 are stored in the stack? 731 00:39:42,170 --> 00:39:46,610 So argc and argv are arguments to main and they are on the stack, or really 732 00:39:46,610 --> 00:39:49,131 just above what you think as the start of the stack. 733 00:39:49,131 --> 00:39:53,490 What was the other part of the question? 734 00:39:53,490 --> 00:39:56,821 >> AUDIENCE: So what's the [INAUDIBLE]? 735 00:39:56,821 --> 00:40:00,990 >> DAN: Yeah, it's just a different way of getting input from the user. 736 00:40:00,990 --> 00:40:06,030 This one's slightly more efficient and it's handier for scripts because you 737 00:40:06,030 --> 00:40:10,070 can just pass arguments to your main function rather than having to wait 738 00:40:10,070 --> 00:40:13,400 for users if you don't have any users. 739 00:40:13,400 --> 00:40:16,280 >> AUDIENCE: And yeah, get strings would be [INAUDIBLE]. 740 00:40:16,280 --> 00:40:17,922 It would store the stuff you need. 741 00:40:17,922 --> 00:40:18,834 >> DAN: Yeah? 742 00:40:18,834 --> 00:40:21,114 >> AUDIENCE: [INAUDIBLE]? 743 00:40:21,114 --> 00:40:27,545 >> DAN: Yes, argv 0 always includes the dot slash of the function call. 744 00:40:27,545 --> 00:40:28,042 Yeah? 745 00:40:28,042 --> 00:40:29,292 >> AUDIENCE: [INAUDIBLE]? 746 00:40:29,292 --> 00:40:33,509 747 00:40:33,509 --> 00:40:37,310 >> DAN: Yes, each of the arguments are ended in NULL character because they 748 00:40:37,310 --> 00:40:38,310 are strings. 749 00:40:38,310 --> 00:40:40,892 >> AUDIENCE: [INAUDIBLE]? 750 00:40:40,892 --> 00:40:44,116 >> DAN: Yes, argv argc is a NULL pointer. 751 00:40:44,116 --> 00:40:45,112 >> AUDIENCE: [INAUDIBLE]? 752 00:40:45,112 --> 00:40:47,104 >> DAN: Oh yeah. 753 00:40:47,104 --> 00:40:48,100 Yeah, sorry. 754 00:40:48,100 --> 00:40:49,594 >> AUDIENCE: So [INAUDIBLE]? 755 00:40:49,594 --> 00:41:08,518 756 00:41:08,518 --> 00:41:16,340 >> DAN: So the question is if you had the command line dot slash a dot out 1, 2, 757 00:41:16,340 --> 00:41:20,410 would the number of command line arguments be two or would it be three? 758 00:41:20,410 --> 00:41:24,420 759 00:41:24,420 --> 00:41:28,240 >> AUDIENCE: I think it doesn't really matter. 760 00:41:28,240 --> 00:41:31,370 I tend to say, oh, you didn't pass any command line arguments when, 761 00:41:31,370 --> 00:41:32,730 obviously, you called the function. 762 00:41:32,730 --> 00:41:37,950 So I tend to vocally exclude the function from the command line 763 00:41:37,950 --> 00:41:40,350 arguments even though it's included in argv. 764 00:41:40,350 --> 00:41:42,600 >> DAN: But if it was on the test-- 765 00:41:42,600 --> 00:41:46,550 yeah-- and also if you say something like argc equals 3, 766 00:41:46,550 --> 00:41:48,512 you're in safe standing. 767 00:41:48,512 --> 00:41:49,416 Yeah? 768 00:41:49,416 --> 00:41:50,666 >> AUDIENCE: [INAUDIBLE]? 769 00:41:50,666 --> 00:42:00,990 770 00:42:00,990 --> 00:42:09,510 >> DAN: I think if instead of calling this in argc and string argv brackets 771 00:42:09,510 --> 00:42:14,350 but kept the same types and just called them something different like a 772 00:42:14,350 --> 00:42:16,640 and b, would it still work? 773 00:42:16,640 --> 00:42:18,790 And it would still work, you would just-- 774 00:42:18,790 --> 00:42:21,520 instead of using argc-- you'd use a and b. 775 00:42:21,520 --> 00:42:24,436 776 00:42:24,436 --> 00:42:25,408 Yeah? 777 00:42:25,408 --> 00:42:26,658 >> AUDIENCE: [INAUDIBLE]? 778 00:42:26,658 --> 00:42:34,642 779 00:42:34,642 --> 00:42:38,850 >> DAN: So the question is GetString is going to store memory in the heap 780 00:42:38,850 --> 00:42:42,280 because GetString is char*. 781 00:42:42,280 --> 00:42:47,530 It stores memory in the heap because it calls now malloc within the actual 782 00:42:47,530 --> 00:42:49,258 implementation of GetString. 783 00:42:49,258 --> 00:42:53,210 784 00:42:53,210 --> 00:42:55,090 OK, moving on. 785 00:42:55,090 --> 00:42:55,950 >> Security. 786 00:42:55,950 --> 00:43:01,090 So to be truly secure, you rely on no one and you allow no one access to any 787 00:43:01,090 --> 00:43:04,540 of your information, which is why everyone builds their own machines, 788 00:43:04,540 --> 00:43:09,580 their own operating systems, all their programs from scratch, and obviously 789 00:43:09,580 --> 00:43:13,410 don't connect to any other machines via the internet. 790 00:43:13,410 --> 00:43:17,350 So computers are insecure. 791 00:43:17,350 --> 00:43:19,200 They really are. 792 00:43:19,200 --> 00:43:20,940 We have to trust other people. 793 00:43:20,940 --> 00:43:26,500 >> And the idea of security is that you're trying to limit the amount of 794 00:43:26,500 --> 00:43:27,540 trust that you need. 795 00:43:27,540 --> 00:43:32,080 And one of the means you do that is through cryptography. 796 00:43:32,080 --> 00:43:34,950 Cryptography is, essentially, we have secrets. 797 00:43:34,950 --> 00:43:38,880 >> Sometimes we have to pass our secrets along through, say, the internet or 798 00:43:38,880 --> 00:43:39,980 other things. 799 00:43:39,980 --> 00:43:43,180 And we don't want people to know these secrets. 800 00:43:43,180 --> 00:43:50,100 So we encrypt our secrets into a way that we hope no one can figure out. 801 00:43:50,100 --> 00:43:51,600 >> So we used-- 802 00:43:51,600 --> 00:43:54,340 through the course of this class-- 803 00:43:54,340 --> 00:44:00,750 things like Caesar cipher and [INAUDIBLE], which are both very, very 804 00:44:00,750 --> 00:44:03,200 insecure ways of encrypting things. 805 00:44:03,200 --> 00:44:07,930 They're easy to figure out what they are and what your secrets are. 806 00:44:07,930 --> 00:44:12,130 The real world uses much more complicated encryption schemes. 807 00:44:12,130 --> 00:44:13,880 And we won't get into much more than that. 808 00:44:13,880 --> 00:44:18,280 809 00:44:18,280 --> 00:44:19,430 >> Debugging. 810 00:44:19,430 --> 00:44:20,785 GDB is the best. 811 00:44:20,785 --> 00:44:24,014 812 00:44:24,014 --> 00:44:25,810 I'm going to stress this again. 813 00:44:25,810 --> 00:44:30,920 Use GDB all the time every time you have a problem. 814 00:44:30,920 --> 00:44:36,030 Commands that are useful in GDB are break, which you pass either a line 815 00:44:36,030 --> 00:44:41,330 number, a function name, essentially where in your code you want to stop, 816 00:44:41,330 --> 00:44:45,600 and be able to take control. 817 00:44:45,600 --> 00:44:54,140 >> Print takes a variable and prints out whatever that variable is at that 818 00:44:54,140 --> 00:44:55,990 point in your execution. 819 00:44:55,990 --> 00:45:00,130 Next moves your execution along one step. 820 00:45:00,130 --> 00:45:05,050 And step steps inside a function in your execution. 821 00:45:05,050 --> 00:45:10,480 >> Other things are run, which is how you actually run your code. 822 00:45:10,480 --> 00:45:16,630 Continue takes all the steps needed to get to the next break point. 823 00:45:16,630 --> 00:45:18,300 And there are many, many others. 824 00:45:18,300 --> 00:45:19,040 Look them up. 825 00:45:19,040 --> 00:45:19,901 They're great. 826 00:45:19,901 --> 00:45:20,863 Yeah? 827 00:45:20,863 --> 00:45:22,113 >> AUDIENCE: [INAUDIBLE]? 828 00:45:22,113 --> 00:45:26,635 829 00:45:26,635 --> 00:45:28,200 >> DAN: Yes, which is a debugger. 830 00:45:28,200 --> 00:45:34,230 So a debugger is a program that lets you debug your program. 831 00:45:34,230 --> 00:45:39,931 It's not a program that finds bugs for you, though that would be great. 832 00:45:39,931 --> 00:45:43,020 833 00:45:43,020 --> 00:45:46,040 >> And last for me is search. 834 00:45:46,040 --> 00:45:51,470 So the types of search that we talked about in this class are linear search, 835 00:45:51,470 --> 00:45:55,960 which is just that you look through each element of the search space, one 836 00:45:55,960 --> 00:46:00,410 element at a time, until you find what you're looking for or until you reach 837 00:46:00,410 --> 00:46:03,350 the end of your search space at which point you say that you couldn't find 838 00:46:03,350 --> 00:46:06,360 the element that you were looking for. 839 00:46:06,360 --> 00:46:13,450 And this takes at best constant time, which is 0 of 1 and at worst linear 840 00:46:13,450 --> 00:46:16,070 time, which is 0 of n. 841 00:46:16,070 --> 00:46:19,250 >> Binary search, which needs sordid elements. 842 00:46:19,250 --> 00:46:24,230 You go to the middle of your elements, see if the element you're looking for 843 00:46:24,230 --> 00:46:30,120 is larger or smaller than the element that you're at the middle. 844 00:46:30,120 --> 00:46:36,510 It it's larger, you say that the bottom of your search space is your 845 00:46:36,510 --> 00:46:41,550 current location, the middle, and you restart the process. 846 00:46:41,550 --> 00:46:46,150 If it's smaller, you look say that the-- yeah, what's up? 847 00:46:46,150 --> 00:46:47,400 >> AUDIENCE: [INAUDIBLE]? 848 00:46:47,400 --> 00:46:51,000 849 00:46:51,000 --> 00:46:54,260 >> DAN: Yes. 850 00:46:54,260 --> 00:46:58,360 Any sort of sort that's been taught in the class is fair game for the test. 851 00:46:58,360 --> 00:47:01,504 852 00:47:01,504 --> 00:47:04,920 >> [LAUGHTER] 853 00:47:04,920 --> 00:47:10,260 >> DAN: And the fact that you haven't had to do it for a problem set, it's fair 854 00:47:10,260 --> 00:47:12,420 game for the test. 855 00:47:12,420 --> 00:47:15,186 >> AUDIENCE: Can we go over it how to-- 856 00:47:15,186 --> 00:47:17,052 >> DAN: It will be gone over. 857 00:47:17,052 --> 00:47:20,496 >> SPEAKER 2: The actual code for [INAUDIBLE] is on study.cs50.net. 858 00:47:20,496 --> 00:47:25,910 859 00:47:25,910 --> 00:47:32,680 So if you look at the practice problem in the merge sort page of 860 00:47:32,680 --> 00:47:35,880 study.cs50.net, there is the code for implementing merge sort. 861 00:47:35,880 --> 00:47:38,550 So you don't have to implement it yourself tonight. 862 00:47:38,550 --> 00:47:42,090 But make sure you understand it rather than just memorizing it. 863 00:47:42,090 --> 00:47:45,035 >> AUDIENCE: [INAUDIBLE]? 864 00:47:45,035 --> 00:47:49,720 >> SPEAKER 2: The merge sort page on study.cs50.net, there is a practice 865 00:47:49,720 --> 00:47:53,570 problem that, if you click through the problem, at the very end there is a 866 00:47:53,570 --> 00:47:56,280 solution, which is the merge sort implementation. 867 00:47:56,280 --> 00:47:58,510 But make sure you understand it rather than just memorizing it 868 00:47:58,510 --> 00:47:59,760 or copying it down. 869 00:47:59,760 --> 00:48:02,870 870 00:48:02,870 --> 00:48:06,340 >> AUDIENCE: And a perfectly valid problem for the exam would be 871 00:48:06,340 --> 00:48:07,990 something like here's a list. 872 00:48:07,990 --> 00:48:12,100 What does this list look like after one step of selections sort or 873 00:48:12,100 --> 00:48:13,330 insertion sort or whatever. 874 00:48:13,330 --> 00:48:14,940 One full iteration of the list. 875 00:48:14,940 --> 00:48:18,530 So even if you don't end up needing to code for it, you need to understand it 876 00:48:18,530 --> 00:48:20,440 enough to know how it's going to be modifying this array. 877 00:48:20,440 --> 00:48:24,144 878 00:48:24,144 --> 00:48:25,394 >> DAN: That's it for me. 879 00:48:25,394 --> 00:48:30,604 880 00:48:30,604 --> 00:48:32,588 >> [APPLAUSE] 881 00:48:32,588 --> 00:49:06,316 882 00:49:06,316 --> 00:49:07,410 >> LUCAS: Hey everyone. 883 00:49:07,410 --> 00:49:08,390 My name is Lucas. 884 00:49:08,390 --> 00:49:16,840 I'm going to talk about recursion, all the sorts that we have learned, and a 885 00:49:16,840 --> 00:49:18,050 little bit of all pointers. 886 00:49:18,050 --> 00:49:18,740 OK? 887 00:49:18,740 --> 00:49:20,340 So first of all, recursion. 888 00:49:20,340 --> 00:49:22,951 What does it mean to say that a function is recursive? 889 00:49:22,951 --> 00:49:24,675 >> AUDIENCE: Calls itself. 890 00:49:24,675 --> 00:49:26,500 >> LUCAS: OK, calls itself, yeah. 891 00:49:26,500 --> 00:49:27,700 So like this picture, for example. 892 00:49:27,700 --> 00:49:30,280 It's like the picture inside of a picture and so on. 893 00:49:30,280 --> 00:49:35,740 So for example, you can have-- as Dan that was talking about binary search. 894 00:49:35,740 --> 00:49:41,840 One way in which binary search is recursive is the fact that you're 895 00:49:41,840 --> 00:49:43,130 trying to find a number. 896 00:49:43,130 --> 00:49:44,250 So you go to the middle. 897 00:49:44,250 --> 00:49:47,130 And then you check if the numbers there in the left and in the right. 898 00:49:47,130 --> 00:49:49,650 >> And then if you find out the number is going to be on the left, it's the same 899 00:49:49,650 --> 00:49:53,340 thing as doing the search again but just on the left of the list. 900 00:49:53,340 --> 00:49:57,350 So that's how it sounds like it's recursive. 901 00:49:57,350 --> 00:50:01,870 So that's why you guys have recursive solution for merge sort. 902 00:50:01,870 --> 00:50:04,270 >> OK, so here's an example. 903 00:50:04,270 --> 00:50:07,280 So let's say that I want to choose all the numbers from 1 to n. 904 00:50:07,280 --> 00:50:13,790 I can realize that the sum of the n number is n plus n minus 1 up to 1. 905 00:50:13,790 --> 00:50:17,810 But then, if I look at n minus 1 plus n minus 2 plus 1, that's the same 906 00:50:17,810 --> 00:50:20,680 thing as summing numbers up to n minus 1. 907 00:50:20,680 --> 00:50:25,890 So I can say the sum of an equal sum equals n plus the sum of n minus 1. 908 00:50:25,890 --> 00:50:28,010 Does that make sense? 909 00:50:28,010 --> 00:50:32,630 >> And I also would have something else called the base case, which is that 910 00:50:32,630 --> 00:50:37,440 the sum of the numbers up to zero would be zero. 911 00:50:37,440 --> 00:50:42,770 So as soon as I get to the number zero, I stop counting. 912 00:50:42,770 --> 00:50:45,330 Does that make sense? 913 00:50:45,330 --> 00:50:48,120 >> So here's an example of how I can implement that. 914 00:50:48,120 --> 00:50:49,860 So I have this function in some. 915 00:50:49,860 --> 00:50:51,700 That takes an integer n. 916 00:50:51,700 --> 00:50:56,300 So here I first check if n is less or equals to zero. 917 00:50:56,300 --> 00:51:00,310 So if it's less or equal to zero, I return zero, which is our base case. 918 00:51:00,310 --> 00:51:05,690 Otherwise, I can just return n plus the sum of the numbers from 919 00:51:05,690 --> 00:51:07,190 one to n minus one. 920 00:51:07,190 --> 00:51:09,360 Make sense? 921 00:51:09,360 --> 00:51:10,100 OK. 922 00:51:10,100 --> 00:51:11,610 >> So here's what it looks like. 923 00:51:11,610 --> 00:51:15,260 You have sum of 2 equals 2 plus the sum of 1. 924 00:51:15,260 --> 00:51:18,930 And some of 1 is 1 plus the sum of 0, which is 0. 925 00:51:18,930 --> 00:51:20,216 Make sense? 926 00:51:20,216 --> 00:51:25,342 So if we look at the stack of your program, this is what it looks like. 927 00:51:25,342 --> 00:51:26,820 >> First, we have the main function. 928 00:51:26,820 --> 00:51:30,320 And then the main function called sum 2. 929 00:51:30,320 --> 00:51:36,690 And then sum 2 is going to say, oh, sum 2 equals 2 plus the sum of one. 930 00:51:36,690 --> 00:51:39,460 So I add sum of 1 to the stack. 931 00:51:39,460 --> 00:51:43,860 And the sum of 1 is going to call sum of 0, which is also going to be added 932 00:51:43,860 --> 00:51:44,630 to the stack. 933 00:51:44,630 --> 00:51:49,240 And then each of these ones that are on top of another have to return 934 00:51:49,240 --> 00:51:52,020 before the other ones can keep going. 935 00:51:52,020 --> 00:51:56,240 >> So for example, here, sum of 0, first, is going to return 0. 936 00:51:56,240 --> 00:51:58,320 And then choose sum of 1. 937 00:51:58,320 --> 00:52:00,850 Then sum of 1 is going to return 1 to sum of 2. 938 00:52:00,850 --> 00:52:03,900 And finally, sum of 2 is going to return 3 to main. 939 00:52:03,900 --> 00:52:05,320 Does that make sense? 940 00:52:05,320 --> 00:52:09,496 >> It's really important to understand how the stack is working and try to 941 00:52:09,496 --> 00:52:11,980 see if it makes sense. 942 00:52:11,980 --> 00:52:13,260 OK, so sorting. 943 00:52:13,260 --> 00:52:16,170 So why is sorting important, first of all? 944 00:52:16,170 --> 00:52:18,260 Why should we care? 945 00:52:18,260 --> 00:52:20,310 Anyone? 946 00:52:20,310 --> 00:52:20,695 Give me an example? 947 00:52:20,695 --> 00:52:21,040 Yeah? 948 00:52:21,040 --> 00:52:22,968 >> AUDIENCE: [INAUDIBLE]. 949 00:52:22,968 --> 00:52:24,700 >> LUCAS: Yeah, OK. 950 00:52:24,700 --> 00:52:26,090 So you can search more efficiently. 951 00:52:26,090 --> 00:52:28,580 That's a good way. 952 00:52:28,580 --> 00:52:32,462 So, for example, we have a lot of things, actually, in our lives that 953 00:52:32,462 --> 00:52:32,920 are sorted. 954 00:52:32,920 --> 00:52:34,830 For example, dictionaries. 955 00:52:34,830 --> 00:52:39,210 >> It's very important to have all the words in some kind of order that we 956 00:52:39,210 --> 00:52:41,970 can access easily. 957 00:52:41,970 --> 00:52:43,280 So that's what he was saying. 958 00:52:43,280 --> 00:52:45,530 You can search more efficiently. 959 00:52:45,530 --> 00:52:48,740 Think of how hard it would be to have a dictionary in which the words are in 960 00:52:48,740 --> 00:52:49,500 random order. 961 00:52:49,500 --> 00:52:53,120 You'll have to look at, pretty much, every single word until you find the 962 00:52:53,120 --> 00:52:54,720 word that you're looking for. 963 00:52:54,720 --> 00:52:58,710 >> If you're using Facebook also, when you're looking at your friends, you're 964 00:52:58,710 --> 00:53:03,540 going to see that Facebook put your closer friend's on top of the ones 965 00:53:03,540 --> 00:53:05,470 that you don't talk to that much. 966 00:53:05,470 --> 00:53:08,080 If you go all the way to the bottom of your friend list, you're going to see 967 00:53:08,080 --> 00:53:11,250 people that you probably don't even remember that you're friends with. 968 00:53:11,250 --> 00:53:14,590 And that's because Facebook sorts your friends based on how 969 00:53:14,590 --> 00:53:16,472 close you are to them. 970 00:53:16,472 --> 00:53:17,930 >> So organizing data. 971 00:53:17,930 --> 00:53:18,450 Also Pokemon. 972 00:53:18,450 --> 00:53:21,400 So you see that all Pokemons have numbers. 973 00:53:21,400 --> 00:53:27,210 And that's like an easy way of accessing data. 974 00:53:27,210 --> 00:53:29,050 >> AUDIENCE: Accessing Pokemon. 975 00:53:29,050 --> 00:53:29,890 >> LUCAS: Yeah. 976 00:53:29,890 --> 00:53:32,395 >> AUDIENCE: [INAUDIBLE]. 977 00:53:32,395 --> 00:53:33,460 >> LUCAS: Yep. 978 00:53:33,460 --> 00:53:35,140 OK, so selection sort. 979 00:53:35,140 --> 00:53:41,610 Selection sort is going to select the smallest unsorted value of a list each 980 00:53:41,610 --> 00:53:43,300 time in each iteration. 981 00:53:43,300 --> 00:53:46,800 It's kind of like the sort that you do in your head when you're trying to 982 00:53:46,800 --> 00:53:48,430 sort a list on hand. 983 00:53:48,430 --> 00:53:51,990 >> Basically, all you do is you look for the smallest number. 984 00:53:51,990 --> 00:53:54,280 You put it in the sorted list. 985 00:53:54,280 --> 00:53:56,230 And then you look for the next smallest number. 986 00:53:56,230 --> 00:54:00,080 And then you keep doing that and so on. 987 00:54:00,080 --> 00:54:04,600 >> So selection sort is basically you select every time the smallest 988 00:54:04,600 --> 00:54:05,750 unsorted value. 989 00:54:05,750 --> 00:54:10,840 Put at the end of the sorted part of the list. 990 00:54:10,840 --> 00:54:12,370 And keep doing that. 991 00:54:12,370 --> 00:54:15,890 So let's quickly see what this looks like. 992 00:54:15,890 --> 00:54:19,340 So here's the sorted and unsorted list. 993 00:54:19,340 --> 00:54:23,350 >> So for the sorted of list, it's initially empty. 994 00:54:23,350 --> 00:54:26,760 And then I'm going to select the smallest number here, which is 2. 995 00:54:26,760 --> 00:54:30,650 So I get the number 2 and I put in the front of the list. 996 00:54:30,650 --> 00:54:34,910 And then I look for the next smallest element, which is 3. 997 00:54:34,910 --> 00:54:37,050 So I put it at the end of the sorted list. 998 00:54:37,050 --> 00:54:38,140 And then I keep doing that. 999 00:54:38,140 --> 00:54:40,040 I find 4 and put it at the end. 1000 00:54:40,040 --> 00:54:41,360 Find 5 and put it at the end. 1001 00:54:41,360 --> 00:54:44,830 >> And look at how all of those times that I'm saying put it at the end is, 1002 00:54:44,830 --> 00:54:46,850 basically, swapping two values. 1003 00:54:46,850 --> 00:54:48,100 OK? 1004 00:54:48,100 --> 00:54:50,140 1005 00:54:50,140 --> 00:54:52,825 And then the last one, you just have one more element. 1006 00:54:52,825 --> 00:54:55,870 So it's already sorted. 1007 00:54:55,870 --> 00:54:57,800 >> OK, so insertion sort. 1008 00:54:57,800 --> 00:55:03,180 Insertion sort you're going to have also that thing of having a sorted and 1009 00:55:03,180 --> 00:55:04,690 an unsorted list. 1010 00:55:04,690 --> 00:55:14,540 The only thing is that every time that you're adding an element to the sorted 1011 00:55:14,540 --> 00:55:18,170 list, you just pick the element that is in front of the unsorted list. 1012 00:55:18,170 --> 00:55:20,880 And then you're going to find what position it should be in the sorted 1013 00:55:20,880 --> 00:55:22,300 part of the list. 1014 00:55:22,300 --> 00:55:25,840 >> Let's see what this is so this makes more sense. 1015 00:55:25,840 --> 00:55:29,360 So initially, for example, I'm trying to insert the number three in the 1016 00:55:29,360 --> 00:55:30,680 sorted part of the list. 1017 00:55:30,680 --> 00:55:31,800 So the list doesn't have anything. 1018 00:55:31,800 --> 00:55:34,160 So I can just put the number 3. 1019 00:55:34,160 --> 00:55:37,480 >> Now, I want to add the number 5 to the sorted part of the list. 1020 00:55:37,480 --> 00:55:38,900 So I look at the number 5. 1021 00:55:38,900 --> 00:55:40,450 I notice that it's greater than 3. 1022 00:55:40,450 --> 00:55:41,980 So I know that it has to be after 3. 1023 00:55:41,980 --> 00:55:44,100 So I put 3 and 5. 1024 00:55:44,100 --> 00:55:45,940 >> Then I want to insert the number 2. 1025 00:55:45,940 --> 00:55:51,630 I notice that the number 2 is actually last then both 3 and 5. 1026 00:55:51,630 --> 00:55:54,580 So I actually have to put it all the way in the beginning of the list. 1027 00:55:54,580 --> 00:55:59,030 So I have to, kind of, shift all the elements in the sorted list so I can 1028 00:55:59,030 --> 00:56:01,970 make room for the number 2. 1029 00:56:01,970 --> 00:56:03,160 >> Then I see the number 6. 1030 00:56:03,160 --> 00:56:05,450 I see that it should be after 5. 1031 00:56:05,450 --> 00:56:06,240 So I put it there. 1032 00:56:06,240 --> 00:56:07,965 And finally, I look at the number 4. 1033 00:56:07,965 --> 00:56:11,030 And I notice it should be between 3 and 5. 1034 00:56:11,030 --> 00:56:14,870 And then I put it there and shift all the other elements. 1035 00:56:14,870 --> 00:56:16,120 Make sense? 1036 00:56:16,120 --> 00:56:17,880 1037 00:56:17,880 --> 00:56:19,150 >> Bubble Sort. 1038 00:56:19,150 --> 00:56:25,730 So bubble sort is basically what you're going to do-- we call it bubble 1039 00:56:25,730 --> 00:56:30,113 sort because you go through the list-- it's actually better if I just show 1040 00:56:30,113 --> 00:56:32,300 you like this-- 1041 00:56:32,300 --> 00:56:35,030 and you're going to compare adjacent numbers. 1042 00:56:35,030 --> 00:56:38,410 And you're going to swap their positions if they're not 1043 00:56:38,410 --> 00:56:39,190 in the right order. 1044 00:56:39,190 --> 00:56:42,570 >> So basically, what is going to happen is here, for example, 1045 00:56:42,570 --> 00:56:44,160 you have 8 and 6. 1046 00:56:44,160 --> 00:56:47,270 You know that the sorted order will actually be 6 and 5, right? 1047 00:56:47,270 --> 00:56:49,540 So you're going to swap the orders. 1048 00:56:49,540 --> 00:56:51,370 Then I see 8 and 4 here. 1049 00:56:51,370 --> 00:56:52,250 And I do the same thing. 1050 00:56:52,250 --> 00:56:53,400 I swap again. 1051 00:56:53,400 --> 00:56:55,070 And finally, 2 and 8. 1052 00:56:55,070 --> 00:56:56,670 I also swap them. 1053 00:56:56,670 --> 00:57:01,690 >> It's called Bubble Sort because after each of these iterations, actually, 1054 00:57:01,690 --> 00:57:05,910 the largest number in the list gets all the way to the end of the list. 1055 00:57:05,910 --> 00:57:06,940 Does that make sense? 1056 00:57:06,940 --> 00:57:11,880 Because it keeps swapping it and moving it to the right. 1057 00:57:11,880 --> 00:57:14,440 >> OK, so this is the second iteration. 1058 00:57:14,440 --> 00:57:17,200 It would be the same thing. 1059 00:57:17,200 --> 00:57:20,190 I'll do one swap and then the last one. 1060 00:57:20,190 --> 00:57:23,290 I that there are no swaps and the list is sorted. 1061 00:57:23,290 --> 00:57:27,460 So in Bubble Sort, we basically keep going through the list and swapping 1062 00:57:27,460 --> 00:57:32,310 things until I notice that I didn't do any swaps doing that iteration, which 1063 00:57:32,310 --> 00:57:34,270 means that list is already sorted. 1064 00:57:34,270 --> 00:57:35,520 Make sense? 1065 00:57:35,520 --> 00:57:38,400 1066 00:57:38,400 --> 00:57:40,870 >> Let's talk a little bit about running time. 1067 00:57:40,870 --> 00:57:45,165 So do you guys remember Big O, Omega, and Theta? 1068 00:57:45,165 --> 00:57:49,290 1069 00:57:49,290 --> 00:57:50,990 Yeah? 1070 00:57:50,990 --> 00:57:53,070 OK, what is Big O, first of all? 1071 00:57:53,070 --> 00:57:54,315 >> AUDIENCE: [INAUDIBLE]. 1072 00:57:54,315 --> 00:57:59,070 >> LUCAS: Yeah, it's called a worst case runtime, which just means that it's 1073 00:57:59,070 --> 00:58:03,470 how much you expect the program to take to run. 1074 00:58:03,470 --> 00:58:04,910 Like, in terms of-- 1075 00:58:04,910 --> 00:58:06,660 in this case-- n. 1076 00:58:06,660 --> 00:58:09,150 The number of elements in the list in the worst case. 1077 00:58:09,150 --> 00:58:12,520 Like, in the worst possible case. 1078 00:58:12,520 --> 00:58:17,100 >> So for Bubble Sort, for example, we have Big O of n square. 1079 00:58:17,100 --> 00:58:20,580 Why do we have that? 1080 00:58:20,580 --> 00:58:24,716 Why is Bubble Sort Big O n square? 1081 00:58:24,716 --> 00:58:27,614 >> AUDIENCE: [INAUDIBLE]. 1082 00:58:27,614 --> 00:58:35,670 >> LUCAS: Yeah, so the worst case will be that I'll have to do n iterations. 1083 00:58:35,670 --> 00:58:39,260 So each of the iterations is going to bring the largest element to the end 1084 00:58:39,260 --> 00:58:40,290 of the list. 1085 00:58:40,290 --> 00:58:44,230 So the worst case is that I have to do that thing n times. 1086 00:58:44,230 --> 00:58:48,550 And for each of those times, I have to do n swaps because I have to compare 1087 00:58:48,550 --> 00:58:49,870 each two elements. 1088 00:58:49,870 --> 00:58:53,730 So that's why it's n squared because it's n times n. 1089 00:58:53,730 --> 00:59:00,120 >> Then, selection sort is also n square because, for each iteration, I have to 1090 00:59:00,120 --> 00:59:02,650 look at every single element in the list. 1091 00:59:02,650 --> 00:59:04,980 And then find the smallest, which means that I have to 1092 00:59:04,980 --> 00:59:06,130 look through n elements. 1093 00:59:06,130 --> 00:59:11,750 And I have to do that n times because I have to select all the n elements. 1094 00:59:11,750 --> 00:59:18,273 >> An insertion sort is also n square because the worst case scenario will 1095 00:59:18,273 --> 00:59:20,950 be, one, I have to insert n numbers, right? 1096 00:59:20,950 --> 00:59:22,765 So I already know that I'm going to have n iterations. 1097 00:59:22,765 --> 00:59:25,466 1098 00:59:25,466 --> 00:59:29,840 But for each of those numbers, if I had to look at all of the numbers in 1099 00:59:29,840 --> 00:59:34,380 the sorted list and put it all the way in the front, that will be n square 1100 00:59:34,380 --> 00:59:36,230 because it will be n times n again. 1101 00:59:36,230 --> 00:59:38,280 Make sense? 1102 00:59:38,280 --> 00:59:41,512 What about omega? 1103 00:59:41,512 --> 00:59:42,886 >> AUDIENCE: [INAUDIBLE]. 1104 00:59:42,886 --> 00:59:44,620 >> LUCAS: It's the best case scenario. 1105 00:59:44,620 --> 00:59:48,810 So it's like, in a lot of times for sorting, the best case scenario is 1106 00:59:48,810 --> 00:59:50,660 when the list is already sorted. 1107 00:59:50,660 --> 00:59:52,670 So you don't really have to do anything. 1108 00:59:52,670 --> 00:59:56,290 Bubble Sort has the best case scenario of n. 1109 00:59:56,290 --> 00:59:58,820 Do you guys know why? 1110 00:59:58,820 --> 01:00:00,620 >> AUDIENCE: [INAUDIBLE]. 1111 01:00:00,620 --> 01:00:05,640 >> LUCAS: Yeah, if you keep track of whether data ration had any swaps or 1112 01:00:05,640 --> 01:00:10,533 not, if you have something like set to true if there was an iteration, if the 1113 01:00:10,533 --> 01:00:15,140 list is already sorted, basically, what's going to happen is I'm going to 1114 01:00:15,140 --> 01:00:17,890 try to swap each two adjacent elements. 1115 01:00:17,890 --> 01:00:19,920 I'm going to see that there are no swaps. 1116 01:00:19,920 --> 01:00:21,230 And I just return right away. 1117 01:00:21,230 --> 01:00:24,240 >> So it means that I just had to go through the list one time. 1118 01:00:24,240 --> 01:00:28,990 So it's n because I look at n elements. 1119 01:00:28,990 --> 01:00:30,930 Why selection sort n square? 1120 01:00:30,930 --> 01:00:35,150 1121 01:00:35,150 --> 01:00:45,520 >> Yeah, even if the list is sorted, for every iteration of selection sort, I 1122 01:00:45,520 --> 01:00:47,590 have to select the minimum element. 1123 01:00:47,590 --> 01:00:49,980 So that means that I have out to look at all the elements in the unsorted 1124 01:00:49,980 --> 01:00:53,350 list and find the minimum for each iteration. 1125 01:00:53,350 --> 01:00:54,600 Does that make sense? 1126 01:00:54,600 --> 01:00:56,880 1127 01:00:56,880 --> 01:01:04,690 >> And insertion sword is n because in the case that I'm trying to insert the 1128 01:01:04,690 --> 01:01:09,320 numbers and all of the numbers, when I try to insert them, I see that they 1129 01:01:09,320 --> 01:01:10,510 are in the right position. 1130 01:01:10,510 --> 01:01:15,120 I don't have to go check all the other numbers in the unsorted list. 1131 01:01:15,120 --> 01:01:17,170 So that's why it will be n. 1132 01:01:17,170 --> 01:01:19,480 Make sense? 1133 01:01:19,480 --> 01:01:21,035 And what is theta? 1134 01:01:21,035 --> 01:01:23,410 >> AUDIENCE: [INAUDIBLE]. 1135 01:01:23,410 --> 01:01:24,380 >> LUCAS: What, sorry? 1136 01:01:24,380 --> 01:01:24,960 Say it again. 1137 01:01:24,960 --> 01:01:25,666 >> AUDIENCE: [INAUDIBLE]. 1138 01:01:25,666 --> 01:01:26,490 >> LUCAS: Exactly. 1139 01:01:26,490 --> 01:01:31,280 So you can see that only selection stored in Merge sort have thetas. 1140 01:01:31,280 --> 01:01:39,920 And that's because you only have theta if both Big O and Omega are the same. 1141 01:01:39,920 --> 01:01:41,520 OK. 1142 01:01:41,520 --> 01:01:44,210 And finally, merge sort is in log n. 1143 01:01:44,210 --> 01:01:48,910 >> And then, as Dan was saying, Merge sort is kind of like the same way that 1144 01:01:48,910 --> 01:01:50,320 you do binary search. 1145 01:01:50,320 --> 01:01:53,530 So you get the list. 1146 01:01:53,530 --> 01:01:55,170 And you're going to cut in half. 1147 01:01:55,170 --> 01:02:00,580 And then you cut them in smaller halves. 1148 01:02:00,580 --> 01:02:01,730 And then you merge them. 1149 01:02:01,730 --> 01:02:02,960 You guys remember that, right? 1150 01:02:02,960 --> 01:02:04,960 OK, as he was saying. 1151 01:02:04,960 --> 01:02:08,330 >> OK, pointers. 1152 01:02:08,330 --> 01:02:11,078 So what is a pointer? 1153 01:02:11,078 --> 01:02:12,050 >> AUDIENCE: [INAUDIBLE]. 1154 01:02:12,050 --> 01:02:12,820 >> LUCAS: An address. 1155 01:02:12,820 --> 01:02:13,720 OK. 1156 01:02:13,720 --> 01:02:18,530 I know that David shows a bunch of videos of binky and things pointing 1157 01:02:18,530 --> 01:02:19,080 each other. 1158 01:02:19,080 --> 01:02:22,960 But I like to think of pointers as merely an address. 1159 01:02:22,960 --> 01:02:26,110 So it's a variable that is going to store an address. 1160 01:02:26,110 --> 01:02:31,940 >> So it's just this special variable that is four bytes long. 1161 01:02:31,940 --> 01:02:36,550 Remember, that pointer to anything is always four bytes long for our 32-bit 1162 01:02:36,550 --> 01:02:39,370 machine so the case with the appliance. 1163 01:02:39,370 --> 01:02:41,920 1164 01:02:41,920 --> 01:02:47,050 And it just has the location of a variable inside of it. 1165 01:02:47,050 --> 01:02:50,240 >> OK, so there's this memory, basically. 1166 01:02:50,240 --> 01:02:57,420 So each block of memory actually has a label, which is the address of the 1167 01:02:57,420 --> 01:02:58,890 slotty memory. 1168 01:02:58,890 --> 01:03:02,370 So that means that I can have a pointer pointing to 1169 01:03:02,370 --> 01:03:03,380 any of these addresses. 1170 01:03:03,380 --> 01:03:09,930 So the reason why we'll use pointers is if I have to remember the location 1171 01:03:09,930 --> 01:03:12,300 that a specific variable is a memory. 1172 01:03:12,300 --> 01:03:16,560 >> And you guys remember that one of those cases was if I have a function 1173 01:03:16,560 --> 01:03:20,820 if I have actually want you to swap for reals, I actually 1174 01:03:20,820 --> 01:03:22,110 have to send a pointer. 1175 01:03:22,110 --> 01:03:23,460 Not the variable. 1176 01:03:23,460 --> 01:03:25,200 Do you guys remember that? 1177 01:03:25,200 --> 01:03:26,450 The difference between-- 1178 01:03:26,450 --> 01:03:33,350 1179 01:03:33,350 --> 01:03:34,120 what is the name? 1180 01:03:34,120 --> 01:03:36,010 Calling by value and calling by reference, right? 1181 01:03:36,010 --> 01:03:36,840 >> OK, yeah. 1182 01:03:36,840 --> 01:03:38,330 So call by value. 1183 01:03:38,330 --> 01:03:43,570 When you just send a variable to function you're just sending a value. 1184 01:03:43,570 --> 01:03:45,610 So you're actually sending a copy of the variable. 1185 01:03:45,610 --> 01:03:49,720 And your program couldn't care less about if the same variable actually 1186 01:03:49,720 --> 01:03:51,650 makes a copy. 1187 01:03:51,650 --> 01:03:56,330 >> And calling by reference means that I'm actually sending a copy of the 1188 01:03:56,330 --> 01:03:57,550 pointer to that variable. 1189 01:03:57,550 --> 01:04:00,970 So it means that I'm sending the location of that variable. 1190 01:04:00,970 --> 01:04:04,440 So sense I have the location of the variable, when I call the function 1191 01:04:04,440 --> 01:04:09,700 with pointers, I'm able to actually change the data that was in main. 1192 01:04:09,700 --> 01:04:12,050 Make sense? 1193 01:04:12,050 --> 01:04:17,560 >> Although, the pointer is a copy, the pointer still has the real address of 1194 01:04:17,560 --> 01:04:20,090 the variable that I want to change. 1195 01:04:20,090 --> 01:04:21,920 Make sense? 1196 01:04:21,920 --> 01:04:24,290 >> So creating pointers. 1197 01:04:24,290 --> 01:04:28,410 Remember, the pointer always have the type that it's pointing 1198 01:04:28,410 --> 01:04:29,890 to and then a star. 1199 01:04:29,890 --> 01:04:31,030 And then you put the name. 1200 01:04:31,030 --> 01:04:35,765 So remember that whenever you have whatever star, it's like a pointer to 1201 01:04:35,765 --> 01:04:38,990 that whatever variable type that you had. 1202 01:04:38,990 --> 01:04:42,850 >> So here in star, for example, it's a pointer and an integer. 1203 01:04:42,850 --> 01:04:47,680 And then char star is a pointer char star and so forth. 1204 01:04:47,680 --> 01:04:47,960 Yeah? 1205 01:04:47,960 --> 01:04:52,710 >> AUDIENCE: What if we have a pointer to n to star x. 1206 01:04:52,710 --> 01:04:55,255 I know that creates a pointer to x. 1207 01:04:55,255 --> 01:04:59,432 Does it also declare x an integer? 1208 01:04:59,432 --> 01:05:05,170 >> LUCAS: OK, so when you say n star x, you're not creating a pointer to a 1209 01:05:05,170 --> 01:05:06,000 variable x. 1210 01:05:06,000 --> 01:05:08,170 You're creating a pointer named x. 1211 01:05:08,170 --> 01:05:09,396 >> AUDIENCE: [INAUDIBLE]. 1212 01:05:09,396 --> 01:05:14,250 >> LUCAS: So when I say n star x, I'm saying, hey, in memory, I'm going to 1213 01:05:14,250 --> 01:05:16,390 get one of these three boxes. 1214 01:05:16,390 --> 01:05:20,750 And I'm going to say that that is going to be x, which is 1215 01:05:20,750 --> 01:05:22,000 going to be a pointer. 1216 01:05:22,000 --> 01:05:26,860 1217 01:05:26,860 --> 01:05:30,640 And something interesting about pointers is that we say that they have 1218 01:05:30,640 --> 01:05:32,620 4 bytes for a 32-bit machine. 1219 01:05:32,620 --> 01:05:36,320 And the reason for that is because 4 bytes are 32-bits. 1220 01:05:36,320 --> 01:05:40,490 >> And machines that are 64 bits actually have pointers addresses 1221 01:05:40,490 --> 01:05:43,480 that are 64 bits long. 1222 01:05:43,480 --> 01:05:49,820 So it just means that the size of the addresses in the machine is different. 1223 01:05:49,820 --> 01:05:52,270 >> So Referencing and Dereferencing. 1224 01:05:52,270 --> 01:05:54,310 There are two operators that you guys should remember. 1225 01:05:54,310 --> 01:05:55,450 The first is ampersand. 1226 01:05:55,450 --> 01:05:56,810 The second is star. 1227 01:05:56,810 --> 01:06:05,060 Don't get confused by that star and this star because remember that, in 1228 01:06:05,060 --> 01:06:06,950 this case, you have n star. 1229 01:06:06,950 --> 01:06:08,700 >> It's like a whole thing together. 1230 01:06:08,700 --> 01:06:10,720 There's no n space star. 1231 01:06:10,720 --> 01:06:12,070 So it means that it's the type. 1232 01:06:12,070 --> 01:06:14,870 Remember, that when you have the variable star, you're 1233 01:06:14,870 --> 01:06:16,230 talking about the type. 1234 01:06:16,230 --> 01:06:20,540 >> When you have just star and then the name of the variable, it means that 1235 01:06:20,540 --> 01:06:24,100 you're dereferencing the pointer, which means that you're looking at the 1236 01:06:24,100 --> 01:06:28,290 pointer, finding the address it's pointing to, going to that address, 1237 01:06:28,290 --> 01:06:30,850 and looking at whenever you have there. 1238 01:06:30,850 --> 01:06:34,310 So I tell my students that when you have star, you should think that it's 1239 01:06:34,310 --> 01:06:36,850 the abbreviation of content of. 1240 01:06:36,850 --> 01:06:39,770 >> So if you have a pointer and you do star pointer, it's the 1241 01:06:39,770 --> 01:06:41,720 content of the pointer. 1242 01:06:41,720 --> 01:06:44,580 So you go to whatever it's pointing to and look at the constant content. 1243 01:06:44,580 --> 01:06:47,730 And the ampersand is the same thing as address of. 1244 01:06:47,730 --> 01:06:52,560 >> So if I have a variable a-- like, let's say that I did int a equals 3-- 1245 01:06:52,560 --> 01:06:56,900 if I want to find the address of that variable a memory, I can just do 1246 01:06:56,900 --> 01:06:58,240 ampersand a. 1247 01:06:58,240 --> 01:07:00,280 So it's address of a. 1248 01:07:00,280 --> 01:07:01,530 Make sense? 1249 01:07:01,530 --> 01:07:03,790 1250 01:07:03,790 --> 01:07:05,040 >> So here's an example. 1251 01:07:05,040 --> 01:07:08,370 1252 01:07:08,370 --> 01:07:11,530 This is missing int b and int c. 1253 01:07:11,530 --> 01:07:16,520 So int a equals 3 means that I'm going to go to memory. 1254 01:07:16,520 --> 01:07:19,870 And I'm going to find a slot and put the number 3 here. 1255 01:07:19,870 --> 01:07:22,200 >> And then int b equals 4. 1256 01:07:22,200 --> 01:07:23,100 I'm going to do the same thing. 1257 01:07:23,100 --> 01:07:25,840 Go to memory and put a number 4 in one of the boxes. 1258 01:07:25,840 --> 01:07:27,100 And int equals 5. 1259 01:07:27,100 --> 01:07:29,740 Find another box and put a number 5. 1260 01:07:29,740 --> 01:07:36,160 >> So what is this line doing out? n star pa equals ampersand a. 1261 01:07:36,160 --> 01:07:37,800 So first of all, n star pa. 1262 01:07:37,800 --> 01:07:39,050 What is it doing? 1263 01:07:39,050 --> 01:07:40,930 1264 01:07:40,930 --> 01:07:42,298 >> AUDIENCE: [INAUDIBLE]. 1265 01:07:42,298 --> 01:07:47,890 >> LUCAS: Yeah, so n star pa, first, declares a pointer called pa. 1266 01:07:47,890 --> 01:07:53,720 And then it's assigning the value of that pointer to be the address of a. 1267 01:07:53,720 --> 01:07:55,790 So ampersand a. 1268 01:07:55,790 --> 01:07:58,510 Then, if I do star pb, what is a star pb? 1269 01:07:58,510 --> 01:08:02,418 1270 01:08:02,418 --> 01:08:03,150 >> Oh, sorry. 1271 01:08:03,150 --> 01:08:06,330 This is also missing. n star pb. 1272 01:08:06,330 --> 01:08:07,905 I mean star pc. 1273 01:08:07,905 --> 01:08:11,200 I'm so sorry. 1274 01:08:11,200 --> 01:08:11,940 It's the same thing. 1275 01:08:11,940 --> 01:08:16,408 But now I'm good ar creating a pointer to b and then a pointer to c. 1276 01:08:16,408 --> 01:08:16,886 Yeah? 1277 01:08:16,886 --> 01:08:18,136 >> AUDIENCE: [INAUDIBLE]? 1278 01:08:18,136 --> 01:08:25,490 1279 01:08:25,490 --> 01:08:26,670 >> LUCAS: Yes. 1280 01:08:26,670 --> 01:08:32,630 So if you go to memory and you go to the box that is designator for pa, 1281 01:08:32,630 --> 01:08:37,149 you're actually going to see an address of a. 1282 01:08:37,149 --> 01:08:38,399 OK? 1283 01:08:38,399 --> 01:08:42,970 1284 01:08:42,970 --> 01:08:43,300 Yeah? 1285 01:08:43,300 --> 01:08:45,605 >> AUDIENCE: [INAUDIBLE]? 1286 01:08:45,605 --> 01:08:49,260 >> LUCAS: Yeah, pointer is an address. 1287 01:08:49,260 --> 01:08:50,120 Never forget that. 1288 01:08:50,120 --> 01:08:52,800 It's like the most important part about pointers. 1289 01:08:52,800 --> 01:08:56,180 There's storing and address to some variable. 1290 01:08:56,180 --> 01:08:56,890 Anything else? 1291 01:08:56,890 --> 01:08:58,370 Any other questions? 1292 01:08:58,370 --> 01:08:59,189 OK. 1293 01:08:59,189 --> 01:09:00,399 >> So Pointers and Arrays. 1294 01:09:00,399 --> 01:09:08,189 Remember that when I do int array 3, basically, what I'm doing is I'm, kind 1295 01:09:08,189 --> 01:09:12,779 of, declaring in a pointer. 1296 01:09:12,779 --> 01:09:18,960 So array is kind of like a pointer to a specific place in memory in which I 1297 01:09:18,960 --> 01:09:21,999 allocated three slots for integers. 1298 01:09:21,999 --> 01:09:23,430 Does that make sense? 1299 01:09:23,430 --> 01:09:30,250 >> So when I do int array 3, what I'm doing, basically, is creating three 1300 01:09:30,250 --> 01:09:31,479 slots in memory. 1301 01:09:31,479 --> 01:09:33,899 So I just find three slots in memory. 1302 01:09:33,899 --> 01:09:38,810 So if I do, then, a star array, it basically means the content of array, 1303 01:09:38,810 --> 01:09:46,180 which means I erase the pointer, I go to that place that it's pointing to, 1304 01:09:46,180 --> 01:09:47,939 and I put the number one. 1305 01:09:47,939 --> 01:09:53,729 >> And then, if I do star array plus 1, that's the same thing as doing array 1306 01:09:53,729 --> 01:09:59,690 brackets one, which just means I go to the place that it's pointing at. 1307 01:09:59,690 --> 01:10:03,000 And then the plus 1 makes me shift one position. 1308 01:10:03,000 --> 01:10:06,510 So I go to this position, actually, and put the number two. 1309 01:10:06,510 --> 01:10:10,900 >> And then, finally, when I do array plus 2, I go to where 1310 01:10:10,900 --> 01:10:11,825 array's pointing at. 1311 01:10:11,825 --> 01:10:14,690 And then I move to memory blocks. 1312 01:10:14,690 --> 01:10:16,240 And then I put the number three here. 1313 01:10:16,240 --> 01:10:16,600 Yeah? 1314 01:10:16,600 --> 01:10:21,400 >> AUDIENCE: So star array is simply saying the very first point. 1315 01:10:21,400 --> 01:10:25,090 And you can add 1, just because we're only really 1316 01:10:25,090 --> 01:10:27,295 referencing that first address. 1317 01:10:27,295 --> 01:10:28,545 >> LUCAS: Yeah. 1318 01:10:28,545 --> 01:10:32,720 1319 01:10:32,720 --> 01:10:36,020 Why do we, for example, say array 0, array 1, and array 2? 1320 01:10:36,020 --> 01:10:38,970 1321 01:10:38,970 --> 01:10:42,790 I'm saying, why do you do 0, 1, 2, 3 instead of 1, 2, 3? 1322 01:10:42,790 --> 01:10:46,550 One of the reasons is, one, computer programmers prefer to start 1323 01:10:46,550 --> 01:10:47,750 counting from 0. 1324 01:10:47,750 --> 01:10:52,370 Two is because when you do array 0, it's the same thing as doing array 1325 01:10:52,370 --> 01:10:56,330 plus 0, which means I go to that position, and I don't 1326 01:10:56,330 --> 01:10:59,320 skip any memory blocks. 1327 01:10:59,320 --> 01:11:01,750 So I don't move any memory blocks. 1328 01:11:01,750 --> 01:11:02,015 Yeah? 1329 01:11:02,015 --> 01:11:03,265 >> AUDIENCE: [INAUDIBLE]? 1330 01:11:03,265 --> 01:11:05,928 1331 01:11:05,928 --> 01:11:12,670 >> LUCAS: So she's asking what is the difference between doing 1332 01:11:12,670 --> 01:11:14,000 this or doing malloc. 1333 01:11:14,000 --> 01:11:17,550 One of the differences is that int array 3 is creating an 1334 01:11:17,550 --> 01:11:19,260 array on the stack. 1335 01:11:19,260 --> 01:11:23,080 And when I do malloc, it creates on the heap. 1336 01:11:23,080 --> 01:11:25,250 Does that make sense? 1337 01:11:25,250 --> 01:11:28,870 >> So how does malloc actually work? 1338 01:11:28,870 --> 01:11:32,245 So why do we even need to use malloc? 1339 01:11:32,245 --> 01:11:35,730 1340 01:11:35,730 --> 01:11:39,700 Your compiler kind of figures out all the variables that you declared. 1341 01:11:39,700 --> 01:11:44,040 And he creates space for all of them in the stack. 1342 01:11:44,040 --> 01:11:47,180 So all of your variables are going to be somewhere in the stack. 1343 01:11:47,180 --> 01:11:49,460 So here is the environment variables. 1344 01:11:49,460 --> 01:11:53,850 >> So basically, space for those variables in memory is allocated at 1345 01:11:53,850 --> 01:11:55,080 compile time. 1346 01:11:55,080 --> 01:11:58,790 So it means that your computer has to know all of those variables 1347 01:11:58,790 --> 01:11:59,790 beforehand. 1348 01:11:59,790 --> 01:12:02,500 It doesn't need to know what value you're going to put in them. 1349 01:12:02,500 --> 01:12:05,490 But it needs to know how much memory you need. 1350 01:12:05,490 --> 01:12:09,380 >> But now let's say that, for example, you're creating an array or taking a 1351 01:12:09,380 --> 01:12:13,430 string that you're taking from the user. 1352 01:12:13,430 --> 01:12:17,300 You don't know how long the string is going to be, for example. 1353 01:12:17,300 --> 01:12:20,600 So you don't know exactly how many memory blocks you allocate, right? 1354 01:12:20,600 --> 01:12:24,120 >> So it doesn't really make sense for you to say put 100 characters. 1355 01:12:24,120 --> 01:12:26,420 And then what if the user writes 150? 1356 01:12:26,420 --> 01:12:27,670 You're going to be screwed. 1357 01:12:27,670 --> 01:12:30,160 1358 01:12:30,160 --> 01:12:34,620 >> So basically, you cannot be sure of how much memory you need to allocate 1359 01:12:34,620 --> 01:12:35,960 when you compile the program. 1360 01:12:35,960 --> 01:12:38,240 You just know that on run time. 1361 01:12:38,240 --> 01:12:39,950 So that's why you have the heap. 1362 01:12:39,950 --> 01:12:47,610 So the heap is going to have memory that you're allocating during the 1363 01:12:47,610 --> 01:12:50,810 duration of the program running. 1364 01:12:50,810 --> 01:12:55,780 >> So basically, when you do malloc, what you're doing is allocating memory at 1365 01:12:55,780 --> 01:13:00,160 runtime, which means that you're deciding right at that moment that you 1366 01:13:00,160 --> 01:13:02,670 should have that memory. 1367 01:13:02,670 --> 01:13:04,210 So that's when you're allocating it. 1368 01:13:04,210 --> 01:13:06,430 Does that make sense? 1369 01:13:06,430 --> 01:13:11,690 >> So remember, the stack has variables that are created on compile time. 1370 01:13:11,690 --> 01:13:14,560 And then the heap has variables that are created as you go 1371 01:13:14,560 --> 01:13:15,600 with malloc, for example. 1372 01:13:15,600 --> 01:13:16,850 >> AUDIENCE: [INAUDIBLE]? 1373 01:13:16,850 --> 01:13:19,179 1374 01:13:19,179 --> 01:13:24,340 >> LUCAS: So GetString is going to call malloc. 1375 01:13:24,340 --> 01:13:26,710 Let me talk about malloc, and I'll explain GetString. 1376 01:13:26,710 --> 01:13:32,000 So malloc is the same thing as memory allocation. 1377 01:13:32,000 --> 01:13:34,600 So it's going to allocate memory on the heap. 1378 01:13:34,600 --> 01:13:40,010 And it's going to return a pointer to where that memory was allocated at. 1379 01:13:40,010 --> 01:13:43,090 >> So when you do-- 1380 01:13:43,090 --> 01:13:44,910 here for example-- 1381 01:13:44,910 --> 01:13:45,830 n star pointer. 1382 01:13:45,830 --> 01:13:50,520 And then pointer equals malloc size of inch times 10. 1383 01:13:50,520 --> 01:13:52,110 I'm creating a pointer. 1384 01:13:52,110 --> 01:13:59,020 And then I'm assigning that pointer to the value of the pointer that malloc 1385 01:13:59,020 --> 01:13:59,680 is giving me. 1386 01:13:59,680 --> 01:14:04,150 >> So I'm asking malloc can you allocate space for 10 integers. 1387 01:14:04,150 --> 01:14:05,390 That's what it's saying. 1388 01:14:05,390 --> 01:14:09,020 And malloc gives me back a pointer to that place. 1389 01:14:09,020 --> 01:14:11,460 Make sense? 1390 01:14:11,460 --> 01:14:12,270 OK. 1391 01:14:12,270 --> 01:14:17,940 I And GetString is, basically, doing a call to malloc so you can allocate 1392 01:14:17,940 --> 01:14:21,680 memory during runtime. 1393 01:14:21,680 --> 01:14:26,460 >> Always remember to check for null because malloc is going to return null 1394 01:14:26,460 --> 01:14:28,200 if it cannot allocate memory. 1395 01:14:28,200 --> 01:14:31,660 Let's say that you ask for a ridiculous amount of memory. 1396 01:14:31,660 --> 01:14:33,950 Your computer is not going to be able to allocate that much. 1397 01:14:33,950 --> 01:14:36,410 >> So malloc is just going to return null. 1398 01:14:36,410 --> 01:14:42,210 So always remember to check if the pointer that you got from malloc is 1399 01:14:42,210 --> 01:14:45,640 null or not because, if it is, you might be dereferencing a pointer and 1400 01:14:45,640 --> 01:14:48,340 causing side faults. 1401 01:14:48,340 --> 01:14:50,930 And finally, don't forget your free memory. 1402 01:14:50,930 --> 01:14:57,800 1403 01:14:57,800 --> 01:15:00,560 >> Malloc is creating memory in the heap. 1404 01:15:00,560 --> 01:15:03,436 And you have to free the memory before the program ends. 1405 01:15:03,436 --> 01:15:05,370 OK, that's all for me. 1406 01:15:05,370 --> 01:15:07,900 Sorry, Rob. 1407 01:15:07,900 --> 01:15:07,950 Thanks. 1408 01:15:07,950 --> 01:15:09,878 >> [APPLAUSE] 1409 01:15:09,878 --> 01:15:12,679 >> LUCAS: Any last questions before Rob comes? 1410 01:15:12,679 --> 01:15:13,138 No? 1411 01:15:13,138 --> 01:15:13,597 Yeah? 1412 01:15:13,597 --> 01:15:15,892 >> AUDIENCE: I didn't see this one online. 1413 01:15:15,892 --> 01:15:17,269 Have you uploaded it yet? 1414 01:15:17,269 --> 01:15:19,106 >> LUCAS: I think Dave is uploading it soon. 1415 01:15:19,106 --> 01:15:19,880 >> DAVE: It'll be posted. 1416 01:15:19,880 --> 01:15:20,310 >> LUCAS: It'll be online. 1417 01:15:20,310 --> 01:15:21,175 >> AUDIENCE: It's up. 1418 01:15:21,175 --> 01:15:22,090 >> LUCAS: It's up? 1419 01:15:22,090 --> 01:15:23,157 OK. 1420 01:15:23,157 --> 01:15:23,644 Yeah? 1421 01:15:23,644 --> 01:15:27,053 >> AUDIENCE: [INAUDIBLE]? 1422 01:15:27,053 --> 01:15:30,285 >> LUCAS: Yes, you should free all the memory that is put in the heap. 1423 01:15:30,285 --> 01:15:31,535 >> AUDIENCE: [INAUDIBLE]? 1424 01:15:31,535 --> 01:15:34,518 1425 01:15:34,518 --> 01:15:36,160 >> LUCAS: Yes. 1426 01:15:36,160 --> 01:15:39,980 Any time that you have a culture malloc, you should have a culture free 1427 01:15:39,980 --> 01:15:42,640 after you stop using that variable. 1428 01:15:42,640 --> 01:15:44,800 So malloc and free are always together. 1429 01:15:44,800 --> 01:15:45,410 Their best friends. 1430 01:15:45,410 --> 01:15:46,720 Yeah. 1431 01:15:46,720 --> 01:15:47,970 Rob? 1432 01:15:47,970 --> 01:15:55,595 1433 01:15:55,595 --> 01:15:56,850 >> ROB: I'll go quickly. 1434 01:15:56,850 --> 01:16:00,466 And also the video will be put up. 1435 01:16:00,466 --> 01:16:01,716 I have the mic on. 1436 01:16:01,716 --> 01:16:24,060 1437 01:16:24,060 --> 01:16:26,230 >> OK, so week five stuff. 1438 01:16:26,230 --> 01:16:27,970 First thing we have is the stack. 1439 01:16:27,970 --> 01:16:33,390 So remember that there's only one stack frame per active function call. 1440 01:16:33,390 --> 01:16:34,710 We'll see that in a second. 1441 01:16:34,710 --> 01:16:37,850 And also remember what actually goes in each stack frame are going to be 1442 01:16:37,850 --> 01:16:41,880 the local variables of our functions, the arguments that are passed into our 1443 01:16:41,880 --> 01:16:43,880 functions, along with a couple other things you don't really 1444 01:16:43,880 --> 01:16:45,260 need to worry about. 1445 01:16:45,260 --> 01:16:50,950 >> So here's an example program where, notice, main is printfing the return 1446 01:16:50,950 --> 01:16:52,830 value of foo 4. 1447 01:16:52,830 --> 01:16:57,930 foo is just going to return the value of bar 4 comma 6. 1448 01:16:57,930 --> 01:17:02,380 And bar is going to set some local variable n equal to 4 times 6. 1449 01:17:02,380 --> 01:17:03,920 And then return n. 1450 01:17:03,920 --> 01:17:09,130 >> So let's look at the stack throughout the actual iteration of this program. 1451 01:17:09,130 --> 01:17:10,500 So there's the bottom of our stack. 1452 01:17:10,500 --> 01:17:12,620 Remember that the stack grows up. 1453 01:17:12,620 --> 01:17:15,370 So at the bottom of our stack, we have a stack frame for main. 1454 01:17:15,370 --> 01:17:17,000 When the program starts, main is always going to be at the 1455 01:17:17,000 --> 01:17:18,560 bottom of our stack. 1456 01:17:18,560 --> 01:17:20,880 >> And what is inside of our stack frame for main? 1457 01:17:20,880 --> 01:17:23,810 So even though there are no local variables to main, like I said before, 1458 01:17:23,810 --> 01:17:29,670 we have argc and rgv taking up space inside of main stack frame. 1459 01:17:29,670 --> 01:17:33,260 So main is now going to call the function foo. 1460 01:17:33,260 --> 01:17:35,125 And that means foo is going to get its own stack frame. 1461 01:17:35,125 --> 01:17:36,970 >> So now we're inside of the function foo. 1462 01:17:36,970 --> 01:17:38,610 And what needs to go in foo's stack frame? 1463 01:17:38,610 --> 01:17:41,100 Well, foo has an argument n. 1464 01:17:41,100 --> 01:17:45,440 And n is equal to 4 since that's what main is passing as foo's argument. 1465 01:17:45,440 --> 01:17:48,490 >> So now foo is going to call bar. 1466 01:17:48,490 --> 01:17:52,070 What is bar going to have inside of its' stack frame? 1467 01:17:52,070 --> 01:17:55,610 It has x equal to 4 y equal to six. 1468 01:17:55,610 --> 01:17:58,540 That's not all that we're going to have in the stack frame because bar 1469 01:17:58,540 --> 01:18:00,580 also has a local variable n. 1470 01:18:00,580 --> 01:18:03,370 And n we're going to set equal to 24. 1471 01:18:03,370 --> 01:18:05,750 >> So now bar is going to return n. 1472 01:18:05,750 --> 01:18:09,300 So bar is returning 24 to the stack frame foo. 1473 01:18:09,300 --> 01:18:12,560 And because bar is now returning, that means we're popping the stack frame 1474 01:18:12,560 --> 01:18:14,250 for bar off of the stack. 1475 01:18:14,250 --> 01:18:18,430 So all the memory that bar had been using is now off the stack. 1476 01:18:18,430 --> 01:18:21,550 >> Now, foo is also going to return 24 to main. 1477 01:18:21,550 --> 01:18:25,470 So now that foo is returning, the memory that foo was using in its' 1478 01:18:25,470 --> 01:18:27,550 stack frame is also gone. 1479 01:18:27,550 --> 01:18:29,660 And now, main is going to call printf. 1480 01:18:29,660 --> 01:18:31,660 So printf is just another function. 1481 01:18:31,660 --> 01:18:35,320 When we call printf, it's going to be another stack frame for the printf 1482 01:18:35,320 --> 01:18:36,470 function call. 1483 01:18:36,470 --> 01:18:37,990 >> What are we passing printf? 1484 01:18:37,990 --> 01:18:40,090 That's what's going to go on its stack frame. 1485 01:18:40,090 --> 01:18:44,970 At the very least, we're passing that percent i backslash n and 1486 01:18:44,970 --> 01:18:47,180 the argument 24. 1487 01:18:47,180 --> 01:18:50,370 It might have more in it's stack frame if printf happens to be using some 1488 01:18:50,370 --> 01:18:51,200 local variables. 1489 01:18:51,200 --> 01:18:51,920 We don't know. 1490 01:18:51,920 --> 01:18:53,810 >> But all that goes in printf's stack frame. 1491 01:18:53,810 --> 01:18:55,740 It's going to execute the printf. 1492 01:18:55,740 --> 01:18:56,830 Then printf's done. 1493 01:18:56,830 --> 01:18:57,820 It will return. 1494 01:18:57,820 --> 01:18:58,960 Finally, main is done. 1495 01:18:58,960 --> 01:18:59,860 Main will return. 1496 01:18:59,860 --> 01:19:02,020 And then our program is done. 1497 01:19:02,020 --> 01:19:02,480 Yeah? 1498 01:19:02,480 --> 01:19:04,505 >> AUDIENCE: Are you seeing [INAUDIBLE] 1499 01:19:04,505 --> 01:19:05,900 arguments [INAUDIBLE] 1500 01:19:05,900 --> 01:19:06,830 parameters? 1501 01:19:06,830 --> 01:19:09,970 >> ROB: So there is a subtle difference between arguments and parameters. 1502 01:19:09,970 --> 01:19:14,400 And really, in common speak, people tend to just mix them up all the time. 1503 01:19:14,400 --> 01:19:17,550 But parameters are the formal name of the things. 1504 01:19:17,550 --> 01:19:20,180 >> So argc and argv are the parameters to main. 1505 01:19:20,180 --> 01:19:23,440 Arguments are what you actually pass in as those parameters. 1506 01:19:23,440 --> 01:19:28,340 So there when I call foo of 4, 4 is the argument I'm passing in. 1507 01:19:28,340 --> 01:19:31,460 And the parameter n, inside of foo, takes on the value 4 1508 01:19:31,460 --> 01:19:32,880 since 4 was the argument. 1509 01:19:32,880 --> 01:19:35,826 >> AUDIENCE: [INAUDIBLE]? 1510 01:19:35,826 --> 01:19:37,880 >> ROB: n is a local variable to bar. 1511 01:19:37,880 --> 01:19:41,420 1512 01:19:41,420 --> 01:19:44,960 n is still local to foo, but it's a parameter to foo. 1513 01:19:44,960 --> 01:19:48,190 It's not a local variable. 1514 01:19:48,190 --> 01:19:48,546 Yeah? 1515 01:19:48,546 --> 01:19:51,180 >> AUDIENCE: [INAUDIBLE]? 1516 01:19:51,180 --> 01:19:55,400 >> ROB: foo is just calling bar and returning whatever bar returns. 1517 01:19:55,400 --> 01:19:56,786 >> AUDIENCE: [INAUDIBLE]? 1518 01:19:56,786 --> 01:19:59,591 >> ROB: Yeah, just to see multiple stack frames. 1519 01:19:59,591 --> 01:20:00,082 Yeah? 1520 01:20:00,082 --> 01:20:03,519 >> AUDIENCE: Why was foo called before printf? 1521 01:20:03,519 --> 01:20:05,920 >> ROB: Why was foo called before printf? 1522 01:20:05,920 --> 01:20:10,740 So I could have, instead, done something like int x equals foo of 4 1523 01:20:10,740 --> 01:20:12,980 and then printed x. 1524 01:20:12,980 --> 01:20:17,900 But instead, I combined the function call into the printf argument. 1525 01:20:17,900 --> 01:20:23,670 >> But notice that we can't actually execute the call to printf until we 1526 01:20:23,670 --> 01:20:25,610 figure out what foo of 4 is. 1527 01:20:25,610 --> 01:20:27,480 So we're going to evaluate this. 1528 01:20:27,480 --> 01:20:32,504 And only once that's done are going to come back and evaluate this. 1529 01:20:32,504 --> 01:20:32,990 Yeah? 1530 01:20:32,990 --> 01:20:37,364 >> AUDIENCE: Since both bar [INAUDIBLE] 1531 01:20:37,364 --> 01:20:41,738 value, why do we not have [INAUDIBLE]? 1532 01:20:41,738 --> 01:20:44,400 >> ROB: They totally should be int. 1533 01:20:44,400 --> 01:20:46,260 That was not caught over multiple passes. 1534 01:20:46,260 --> 01:20:49,010 So it should be int bar and int foo since both of those 1535 01:20:49,010 --> 01:20:50,460 are returning integers. 1536 01:20:50,460 --> 01:20:54,214 Void is only if they're not going to return actual values. 1537 01:20:54,214 --> 01:20:54,692 Yeah? 1538 01:20:54,692 --> 01:20:58,038 >> AUDIENCE: If you had a line above the return, [INAUDIBLE]? 1539 01:20:58,038 --> 01:21:01,862 1540 01:21:01,862 --> 01:21:03,730 >> ROB: A line above the return? 1541 01:21:03,730 --> 01:21:04,410 >> AUDIENCE: Yeah. 1542 01:21:04,410 --> 01:21:10,780 Like if you did printf and [INAUDIBLE], would it print twice? 1543 01:21:10,780 --> 01:21:12,992 >> ROB: So inside of foo? 1544 01:21:12,992 --> 01:21:15,945 If we had a printf right here? 1545 01:21:15,945 --> 01:21:16,750 >> AUDIENCE: Yeah. 1546 01:21:16,750 --> 01:21:19,510 >> ROB: So if we had a printf right here, it would print once. 1547 01:21:19,510 --> 01:21:23,400 Since we are calling foo once right here, then we'll hit the printf. 1548 01:21:23,400 --> 01:21:24,620 Then we'll call bar. 1549 01:21:24,620 --> 01:21:25,710 And then foo will return. 1550 01:21:25,710 --> 01:21:26,275 And that's it. 1551 01:21:26,275 --> 01:21:30,985 We only ever encounter the printf once. 1552 01:21:30,985 --> 01:21:31,482 Yeah? 1553 01:21:31,482 --> 01:21:32,973 >> AUDIENCE: [INAUDIBLE] 1554 01:21:32,973 --> 01:21:37,950 printf calling foo because we're first calling printf and then we're passing 1555 01:21:37,950 --> 01:21:38,580 the arguments. 1556 01:21:38,580 --> 01:21:40,960 >> ROB: So in theory, isn't printf calling foo? 1557 01:21:40,960 --> 01:21:42,220 So no. 1558 01:21:42,220 --> 01:21:47,360 Just the order that c is going to execute these things is, before we can 1559 01:21:47,360 --> 01:21:49,800 call a function, all of the arguments to the function have to 1560 01:21:49,800 --> 01:21:51,600 be completely evaluated. 1561 01:21:51,600 --> 01:21:53,540 So is this completely evaluated? 1562 01:21:53,540 --> 01:21:54,610 Yes, it's just a string. 1563 01:21:54,610 --> 01:21:55,480 It's just a value. 1564 01:21:55,480 --> 01:21:57,200 >> Then we have to completely evaluate this. 1565 01:21:57,200 --> 01:21:59,720 Once this is done, now all of its arguments are evaluated. 1566 01:21:59,720 --> 01:22:01,982 And now we can make the call to printf. 1567 01:22:01,982 --> 01:22:02,478 Yeah? 1568 01:22:02,478 --> 01:22:03,966 >> AUDIENCE: One question. 1569 01:22:03,966 --> 01:22:06,942 If you have a void function, must you have return semicolon? 1570 01:22:06,942 --> 01:22:09,910 >> ROB: You do not a return semicolon if you have a void function. 1571 01:22:09,910 --> 01:22:13,370 1572 01:22:13,370 --> 01:22:14,780 OK. 1573 01:22:14,780 --> 01:22:15,830 So now some heap stuff. 1574 01:22:15,830 --> 01:22:19,640 So heap is how we're going to deal with dynamic memory management. 1575 01:22:19,640 --> 01:22:23,100 And this directly contrasts with the stack which we would call automatic 1576 01:22:23,100 --> 01:22:24,100 memory management. 1577 01:22:24,100 --> 01:22:27,140 >> So on the stack, you never really have to deal with how the local variables 1578 01:22:27,140 --> 01:22:30,400 are being pushed and popped off all these stack frames and all that stuff. 1579 01:22:30,400 --> 01:22:31,070 You don't have to worry about it. 1580 01:22:31,070 --> 01:22:32,070 It's automatic. 1581 01:22:32,070 --> 01:22:36,990 So the heap is manual. 1582 01:22:36,990 --> 01:22:38,070 And the [INAUDIBLE] 1583 01:22:38,070 --> 01:22:41,260 comes from these functions malloc and free. 1584 01:22:41,260 --> 01:22:43,550 >> So here's another program. 1585 01:22:43,550 --> 01:22:47,145 All we're doing is mallocing an integer. 1586 01:22:47,145 --> 01:22:49,360 We're storing it in star x. 1587 01:22:49,360 --> 01:22:52,520 Of course, we have to check to see if x is null. 1588 01:22:52,520 --> 01:22:56,400 Then we're going to just set what x is pointing to to 50. 1589 01:22:56,400 --> 01:23:00,350 1590 01:23:00,350 --> 01:23:03,260 Print what x is pointing to, print x, and then free x. 1591 01:23:03,260 --> 01:23:08,920 >> So how is this actually going to look if we look at our stack and heap? 1592 01:23:08,920 --> 01:23:10,950 So we'll start again. 1593 01:23:10,950 --> 01:23:12,580 The bottom of our stack as before. 1594 01:23:12,580 --> 01:23:15,930 Remember that thee heap directly opposes the stack? 1595 01:23:15,930 --> 01:23:18,850 So we're going to have the top of our heap up there. 1596 01:23:18,850 --> 01:23:22,590 >> So the bottom of our stack, we have our stack frame for main. 1597 01:23:22,590 --> 01:23:28,000 It has the space for argc, argv, and we now have a local variable x, which 1598 01:23:28,000 --> 01:23:30,030 is an int star. 1599 01:23:30,030 --> 01:23:32,240 So we're going to iterate through this program. 1600 01:23:32,240 --> 01:23:34,420 First thing we have is a call to malloc. 1601 01:23:34,420 --> 01:23:36,250 >> So we're making a call to malloc. 1602 01:23:36,250 --> 01:23:37,100 Malloc is a function. 1603 01:23:37,100 --> 01:23:38,770 It's going to get a stack frame. 1604 01:23:38,770 --> 01:23:40,180 What are we passing to malloc? 1605 01:23:40,180 --> 01:23:41,610 That's going to go inside of the stack frame. 1606 01:23:41,610 --> 01:23:45,130 We're passing size of n, which is 4. 1607 01:23:45,130 --> 01:23:49,700 So that is passed to malloc. 1608 01:23:49,700 --> 01:23:50,910 >> What does malloc do? 1609 01:23:50,910 --> 01:23:53,820 It grabs us some space on the heap. 1610 01:23:53,820 --> 01:23:55,320 So we're going to go to the heap. 1611 01:23:55,320 --> 01:23:57,990 And we're going to grab 4 bytes from the heap. 1612 01:23:57,990 --> 01:24:01,500 So let's just give that an arbitrary address. 1613 01:24:01,500 --> 01:24:06,680 0x123 Just pretend that is an address that is on the heap. 1614 01:24:06,680 --> 01:24:12,300 >> So what is actually inside of that region of memory at address Ox123? 1615 01:24:12,300 --> 01:24:13,080 Garbage. 1616 01:24:13,080 --> 01:24:15,270 So we have not stored anything in it. 1617 01:24:15,270 --> 01:24:18,830 So as far as we know, it could be anything. 1618 01:24:18,830 --> 01:24:20,560 You shouldn't assume it's zero. 1619 01:24:20,560 --> 01:24:23,870 It's most likely not zero. 1620 01:24:23,870 --> 01:24:26,260 >> So now malloc returns. 1621 01:24:26,260 --> 01:24:28,020 And what do we do when malloc returns? 1622 01:24:28,020 --> 01:24:29,800 We set what it returns. 1623 01:24:29,800 --> 01:24:32,290 We set x equal to what it is returning. 1624 01:24:32,290 --> 01:24:33,690 So what is it returning? 1625 01:24:33,690 --> 01:24:38,150 It's returning 0x123 since that is the address of the block of memory that it 1626 01:24:38,150 --> 01:24:40,850 just allocated in the heap. 1627 01:24:40,850 --> 01:24:47,160 >> So return 0x123 x is now going to be set equal to 0x123 which, pictorially, 1628 01:24:47,160 --> 01:24:52,940 we frequently draw as x having an actual arrow pointing to that block. 1629 01:24:52,940 --> 01:24:55,820 But x is just storing that address. 1630 01:24:55,820 --> 01:24:58,670 So now we have to check if x is null. 1631 01:24:58,670 --> 01:24:59,120 It's not null. 1632 01:24:59,120 --> 01:25:02,170 We pretend that that malloc succeeded. 1633 01:25:02,170 --> 01:25:04,950 >> So now star x equals 50. 1634 01:25:04,950 --> 01:25:08,450 So star remembers it means go to that address. 1635 01:25:08,450 --> 01:25:12,700 So 0x123 We're going to go to that address. 1636 01:25:12,700 --> 01:25:14,660 So that brings us up there. 1637 01:25:14,660 --> 01:25:16,310 What are we doing at that address? 1638 01:25:16,310 --> 01:25:19,020 We're storing 50. 1639 01:25:19,020 --> 01:25:22,500 >> So after this line, that is what things are going to look like. 1640 01:25:22,500 --> 01:25:24,640 So now it's no longer garbage up there. 1641 01:25:24,640 --> 01:25:28,910 Now we know that 50 is in that particular address because 1642 01:25:28,910 --> 01:25:32,410 we set it to that. 1643 01:25:32,410 --> 01:25:32,790 OK? 1644 01:25:32,790 --> 01:25:34,370 So now we're going to print f. 1645 01:25:34,370 --> 01:25:38,490 >> So first we're going to print star x. 1646 01:25:38,490 --> 01:25:39,640 So what is star x? 1647 01:25:39,640 --> 01:25:44,300 Again, star x means go to the thing that x is pointing to. 1648 01:25:44,300 --> 01:25:47,140 So x is storing 0x123 Go to that. 1649 01:25:47,140 --> 01:25:48,490 We get 50. 1650 01:25:48,490 --> 01:25:50,540 So print f that. 1651 01:25:50,540 --> 01:25:54,900 And that means it's going to print 50. 1652 01:25:54,900 --> 01:25:56,850 And then that returns. 1653 01:25:56,850 --> 01:25:58,340 >> And then we have the second printf. 1654 01:25:58,340 --> 01:25:59,370 We're now percent p. 1655 01:25:59,370 --> 01:26:01,680 If you haven't seen it, that's just how you print a pointer. 1656 01:26:01,680 --> 01:26:04,960 So we have percent i, percent f, and all of those already. 1657 01:26:04,960 --> 01:26:07,160 So percent p, print a pointer. 1658 01:26:07,160 --> 01:26:08,920 >> So x is a pointer. 1659 01:26:08,920 --> 01:26:13,440 So if we're going to print x itself, we're printing what is actually inside 1660 01:26:13,440 --> 01:26:19,220 x, which is 0x123 So the first print f is going to print 50. 1661 01:26:19,220 --> 01:26:23,620 The second print f is going to print 0x123 Yeah? 1662 01:26:23,620 --> 01:26:27,460 >> AUDIENCE: Do you use percent x to print a pointer? 1663 01:26:27,460 --> 01:26:31,200 >> ROB: So do you use percent x to print a pointer? 1664 01:26:31,200 --> 01:26:38,350 So you can but percent x is just, generally, for like if you have some 1665 01:26:38,350 --> 01:26:40,325 integer and you want to print it as a hexadecimal. 1666 01:26:40,325 --> 01:26:43,250 1667 01:26:43,250 --> 01:26:44,880 That's just how you do that. 1668 01:26:44,880 --> 01:26:47,160 >> Whereas, percent d would print as decimal. 1669 01:26:47,160 --> 01:26:50,310 That's were we get percent d. i is just integer. 1670 01:26:50,310 --> 01:26:52,690 percent p is specifically for pointers. 1671 01:26:52,690 --> 01:26:54,060 >> So x is a pointer. 1672 01:26:54,060 --> 01:26:56,360 We want to use percent p. 1673 01:26:56,360 --> 01:26:57,937 But percent x could work. 1674 01:26:57,937 --> 01:26:58,414 Yeah? 1675 01:26:58,414 --> 01:26:59,664 >> AUDIENCE: [INAUDIBLE]? 1676 01:26:59,664 --> 01:27:04,138 1677 01:27:04,138 --> 01:27:05,388 >> ROB: Yeah. 1678 01:27:05,388 --> 01:27:07,870 1679 01:27:07,870 --> 01:27:13,440 At least for this call-- so I didn't include it in here. 1680 01:27:13,440 --> 01:27:19,850 But these two arguments are necessarily inside of this stack frame 1681 01:27:19,850 --> 01:27:23,040 along with any local variables printf happens to be using. 1682 01:27:23,040 --> 01:27:27,020 And then the next call to printf now inside of printf stack frame is 1683 01:27:27,020 --> 01:27:33,960 percent p backslash n and whatever the value of x is, which is 0x123. 1684 01:27:33,960 --> 01:27:34,425 Yeah? 1685 01:27:34,425 --> 01:27:35,675 >> AUDIENCE: [INAUDIBLE]? 1686 01:27:35,675 --> 01:27:38,145 1687 01:27:38,145 --> 01:27:40,880 >> ROB: It'll print something that looks like this. 1688 01:27:40,880 --> 01:27:41,846 >> AUDIENCE: [INAUDIBLE]. 1689 01:27:41,846 --> 01:27:44,510 >> ROB: So it prints it in address form. 1690 01:27:44,510 --> 01:27:47,003 It looks like an address. 1691 01:27:47,003 --> 01:27:47,494 Yeah? 1692 01:27:47,494 --> 01:27:49,458 >> AUDIENCE: [INAUDIBLE]? 1693 01:27:49,458 --> 01:27:51,075 >> ROB: Why is what? 1694 01:27:51,075 --> 01:27:52,920 >> AUDIENCE: [INAUDIBLE]? 1695 01:27:52,920 --> 01:27:55,240 >> ROB: Why is this pointer 4 bytes? 1696 01:27:55,240 --> 01:27:58,500 So there are a whole bunch of 0's in front of this. 1697 01:27:58,500 --> 01:28:03,740 So it's really 0x0000000123. 1698 01:28:03,740 --> 01:28:06,510 On a 64-bit system, there would be a whole bunch of more zeros. 1699 01:28:06,510 --> 01:28:11,410 1700 01:28:11,410 --> 01:28:11,900 Yeah? 1701 01:28:11,900 --> 01:28:13,150 >> AUDIENCE: [INAUDIBLE]. 1702 01:28:13,150 --> 01:28:17,290 1703 01:28:17,290 --> 01:28:21,130 >> ROB: So the first printf is going to print-- 1704 01:28:21,130 --> 01:28:21,980 >> AUDIENCE: [INAUDIBLE]. 1705 01:28:21,980 --> 01:28:24,420 >> ROB: Yes, it's going to print what x is pointing to. 1706 01:28:24,420 --> 01:28:27,030 1707 01:28:27,030 --> 01:28:29,070 Star says what is this thing pointing to. 1708 01:28:29,070 --> 01:28:30,300 Grab it. 1709 01:28:30,300 --> 01:28:31,455 So what is it pointing to? 1710 01:28:31,455 --> 01:28:31,850 50. 1711 01:28:31,850 --> 01:28:32,410 Grab it. 1712 01:28:32,410 --> 01:28:33,390 That's what we're going to print. 1713 01:28:33,390 --> 01:28:37,020 Whereas, the next one, we're just printing x itself. 1714 01:28:37,020 --> 01:28:38,850 What is inside of f? 1715 01:28:38,850 --> 01:28:43,710 0x123. 1716 01:28:43,710 --> 01:28:44,500 OK. 1717 01:28:44,500 --> 01:28:46,620 >> And then, finally, we have the free. 1718 01:28:46,620 --> 01:28:48,040 What are we passing to free? 1719 01:28:48,040 --> 01:28:49,470 We're passing x. 1720 01:28:49,470 --> 01:28:52,380 That time I actually displayed it in the stack frame. 1721 01:28:52,380 --> 01:28:56,370 >> So we're passing the value 0x123 to free. 1722 01:28:56,370 --> 01:28:59,070 So now free knows, all right, I have to go up to the heap 1723 01:28:59,070 --> 01:29:00,050 and free that memory. 1724 01:29:00,050 --> 01:29:03,920 It's no longer using what is at address 0x123. 1725 01:29:03,920 --> 01:29:07,010 >> So free is going to release that from the heap. 1726 01:29:07,010 --> 01:29:09,490 Now our heap is empty again. 1727 01:29:09,490 --> 01:29:11,120 We have no memory leaks. 1728 01:29:11,120 --> 01:29:12,940 Now free will return. 1729 01:29:12,940 --> 01:29:16,130 Notice that x is still 0x123. 1730 01:29:16,130 --> 01:29:18,240 But that is now not valid memory. 1731 01:29:18,240 --> 01:29:21,220 1732 01:29:21,220 --> 01:29:23,986 We should no longer dereference x. 1733 01:29:23,986 --> 01:29:24,440 Yeah? 1734 01:29:24,440 --> 01:29:27,240 >> AUDIENCE: Is return 0 redundant? 1735 01:29:27,240 --> 01:29:28,290 >> ROB: Is returen 0 redundant? 1736 01:29:28,290 --> 01:29:31,110 Yes. 1737 01:29:31,110 --> 01:29:33,950 We just put that there because we have a return one for air. 1738 01:29:33,950 --> 01:29:36,830 So it's like, yeah, lets include the return 0. 1739 01:29:36,830 --> 01:29:37,310 Yeah? 1740 01:29:37,310 --> 01:29:38,560 >> AUDIENCE: [INAUDIBLE]? 1741 01:29:38,560 --> 01:29:42,110 1742 01:29:42,110 --> 01:29:45,580 >> ROB: So after free x, what happens if we try to dereference the pointer? 1743 01:29:45,580 --> 01:29:47,240 It's possible that nothing goes wrong. 1744 01:29:47,240 --> 01:29:49,330 It's possible that we'll still get 50. 1745 01:29:49,330 --> 01:29:53,590 >> It's possible, also, that that memory is now being used for something else. 1746 01:29:53,590 --> 01:29:57,140 So it's undefined behavior. 1747 01:29:57,140 --> 01:30:00,772 And undefined means anything can happen. 1748 01:30:00,772 --> 01:30:01,250 Yeah? 1749 01:30:01,250 --> 01:30:02,500 >> AUDIENCE: [INAUDIBLE]? 1750 01:30:02,500 --> 01:30:07,942 1751 01:30:07,942 --> 01:30:10,830 >> ROB: No, so if you assign x to something else. 1752 01:30:10,830 --> 01:30:15,870 So if right here we said x equals malloc something else-- 1753 01:30:15,870 --> 01:30:17,100 malloc size event-- 1754 01:30:17,100 --> 01:30:20,180 then that original block of memory is not freed. 1755 01:30:20,180 --> 01:30:21,490 And we have officially lost it. 1756 01:30:21,490 --> 01:30:23,150 That is a memory leak. 1757 01:30:23,150 --> 01:30:25,090 We've lost all references to that block of memory. 1758 01:30:25,090 --> 01:30:26,827 So there's no way we can ever free it. 1759 01:30:26,827 --> 01:30:32,074 1760 01:30:32,074 --> 01:30:36,630 OK, so then return 0 means done. 1761 01:30:36,630 --> 01:30:37,900 >> All right, so stack overflow. 1762 01:30:37,900 --> 01:30:39,320 What's the idea here? 1763 01:30:39,320 --> 01:30:41,210 So remember, heap is going down. 1764 01:30:41,210 --> 01:30:43,480 Stack is going up. 1765 01:30:43,480 --> 01:30:48,000 So this was the example from lecture, I think, where main is just going to 1766 01:30:48,000 --> 01:30:51,380 call this function foo, which is going to call itself recursively over and 1767 01:30:51,380 --> 01:30:52,320 over again. 1768 01:30:52,320 --> 01:30:55,370 >> So stack frames are going to work exactly the same. 1769 01:30:55,370 --> 01:30:58,130 So we're going to start with main as the bottom stack frame. 1770 01:30:58,130 --> 01:31:02,000 Then main is going to call foo, which is going to get a stack frame. 1771 01:31:02,000 --> 01:31:04,260 >> Then foo is going to call foo again, which is going to get 1772 01:31:04,260 --> 01:31:05,500 another stack frame. 1773 01:31:05,500 --> 01:31:08,270 And then again, and again, and again, and again until, eventually, we run 1774 01:31:08,270 --> 01:31:09,190 into the heap. 1775 01:31:09,190 --> 01:31:11,990 So this is how we get a stack overflow. 1776 01:31:11,990 --> 01:31:14,910 And at this point, you seg fault. 1777 01:31:14,910 --> 01:31:17,335 Or you'd really seg fault before this point but yeah. 1778 01:31:17,335 --> 01:31:19,660 >> AUDIENCE: Is core dump the same as seg fault? 1779 01:31:19,660 --> 01:31:26,140 >> ROB: So you'll see segmentation fault core dumped. 1780 01:31:26,140 --> 01:31:28,760 You get a core dump when you seg fault. 1781 01:31:28,760 --> 01:31:32,580 And it's like a dump of all of the contents of your current memory so 1782 01:31:32,580 --> 01:31:36,670 that you can try and identify why you seg faulted. 1783 01:31:36,670 --> 01:31:37,135 Yeah? 1784 01:31:37,135 --> 01:31:38,385 >> AUDIENCE: [INAUDIBLE]? 1785 01:31:38,385 --> 01:31:40,855 1786 01:31:40,855 --> 01:31:45,460 >> ROB: So a segmentation fault means there's a stack overflow. 1787 01:31:45,460 --> 01:31:47,060 So not necessarily. 1788 01:31:47,060 --> 01:31:49,880 A segmentation fault means that you're touching memory in a way 1789 01:31:49,880 --> 01:31:50,880 you shouldn't be. 1790 01:31:50,880 --> 01:31:54,750 So one way of that happening is, when you stack overflow, we start touching 1791 01:31:54,750 --> 01:31:58,736 memory in a way that we shouldn't be. 1792 01:31:58,736 --> 01:31:59,208 Yeah? 1793 01:31:59,208 --> 01:32:00,458 >> AUDIENCE: [INAUDIBLE]? 1794 01:32:00,458 --> 01:32:03,456 1795 01:32:03,456 --> 01:32:05,830 >> ROB: So inside of an infinite loop. 1796 01:32:05,830 --> 01:32:08,770 Like, this is like a recursive infinite loop and so we get another 1797 01:32:08,770 --> 01:32:09,770 stack frame each time. 1798 01:32:09,770 --> 01:32:13,540 But just inside of a regular infinite while one-- 1799 01:32:13,540 --> 01:32:16,390 well, let's not even print f-- 1800 01:32:16,390 --> 01:32:17,040 do something. 1801 01:32:17,040 --> 01:32:18,390 Whatever. 1802 01:32:18,390 --> 01:32:20,610 >> We're not going to be getting another stack frame. 1803 01:32:20,610 --> 01:32:22,530 We're just going to keep looping over this single instruction. 1804 01:32:22,530 --> 01:32:23,920 The stack isn't growing. 1805 01:32:23,920 --> 01:32:27,290 It's the fact that each recursive call is giving us a stack frame. 1806 01:32:27,290 --> 01:32:31,231 That's why we get a stack overflow. 1807 01:32:31,231 --> 01:32:31,728 Yeah? 1808 01:32:31,728 --> 01:32:38,189 >> AUDIENCE: So if you said to get the while loop and then [INAUDIBLE]? 1809 01:32:38,189 --> 01:32:42,000 >> ROB: So if inside of the while loop there was a printf, you still would 1810 01:32:42,000 --> 01:32:42,790 not seg fault. 1811 01:32:42,790 --> 01:32:46,090 I just didn't want to confuse things. 1812 01:32:46,090 --> 01:32:46,610 It would loop. 1813 01:32:46,610 --> 01:32:48,225 You'd get a single stack frame for the printf. 1814 01:32:48,225 --> 01:32:49,580 >> Then printf would return. 1815 01:32:49,580 --> 01:32:50,280 Then you'd loop again. 1816 01:32:50,280 --> 01:32:51,460 You'd get a single stack frame for the printf. 1817 01:32:51,460 --> 01:32:52,850 It would return. 1818 01:32:52,850 --> 01:32:54,060 Single stack frame. 1819 01:32:54,060 --> 01:33:00,215 So you're not getting this infinite piling up stack frames. 1820 01:33:00,215 --> 01:33:03,185 >> AUDIENCE: [INAUDIBLE]? 1821 01:33:03,185 --> 01:33:04,040 >> ROB: Yes. 1822 01:33:04,040 --> 01:33:09,360 So this stack overflow happens because none of these 1823 01:33:09,360 --> 01:33:11,600 calls to foo are returning. 1824 01:33:11,600 --> 01:33:15,250 So if we return, then we would start losing stack frames. 1825 01:33:15,250 --> 01:33:17,870 And then we would not stack overflow. 1826 01:33:17,870 --> 01:33:20,070 And that's why you need a base case for your personal functions. 1827 01:33:20,070 --> 01:33:22,992 1828 01:33:22,992 --> 01:33:23,479 Yeah? 1829 01:33:23,479 --> 01:33:27,375 >> AUDIENCE: Is the potential size and the stack for the heap the same for 1830 01:33:27,375 --> 01:33:29,880 all programs? 1831 01:33:29,880 --> 01:33:31,910 >> ROB: Roughly. 1832 01:33:31,910 --> 01:33:35,090 Is the potential size of the stack and the heap the same for all programs? 1833 01:33:35,090 --> 01:33:37,180 Roughly. 1834 01:33:37,180 --> 01:33:40,080 There is some randomization to where the stack starts and 1835 01:33:40,080 --> 01:33:42,400 where the heap starts. 1836 01:33:42,400 --> 01:33:45,870 If you happen to have a whole lot of global variables and things, you might 1837 01:33:45,870 --> 01:33:49,520 take away from some space for your heap. 1838 01:33:49,520 --> 01:33:54,060 >> On a 64-bit system, you virtually have infinite memory. 1839 01:33:54,060 --> 01:33:55,820 There's just so much. 1840 01:33:55,820 --> 01:33:59,250 Between 32 bits and 64 bits, that is a significant difference. 1841 01:33:59,250 --> 01:34:02,350 >> You're going to get a whole lot more stack and heap space on a 64-bit 1842 01:34:02,350 --> 01:34:05,810 system because there's just more addresses that they can use. 1843 01:34:05,810 --> 01:34:09,360 But on an individual system, it will be roughly the same amount of stack 1844 01:34:09,360 --> 01:34:10,785 and heap space. 1845 01:34:10,785 --> 01:34:13,635 1846 01:34:13,635 --> 01:34:15,530 All right. 1847 01:34:15,530 --> 01:34:18,220 >> So last thing is compilation. 1848 01:34:18,220 --> 01:34:19,810 So you should know this process. 1849 01:34:19,810 --> 01:34:22,240 There are four big steps. 1850 01:34:22,240 --> 01:34:24,400 So the first one should be easy to remember. 1851 01:34:24,400 --> 01:34:25,085 Pre-processing. 1852 01:34:25,085 --> 01:34:28,390 It has the prefix pre in it. 1853 01:34:28,390 --> 01:34:32,080 So it comes before everything else. 1854 01:34:32,080 --> 01:34:34,000 >> The thing to remember is the hash. 1855 01:34:34,000 --> 01:34:37,250 So hash defines and hash includes in all of those. 1856 01:34:37,250 --> 01:34:39,560 Those are all pre-processor directives. 1857 01:34:39,560 --> 01:34:42,030 These are the things that the pre-processor takes care of. 1858 01:34:42,030 --> 01:34:43,680 >> So what does a pre-processor do? 1859 01:34:43,680 --> 01:34:44,850 It's a really dumb thing. 1860 01:34:44,850 --> 01:34:49,380 All it's capable of are all of these copy, and cut, and paste operations. 1861 01:34:49,380 --> 01:34:51,790 >> So hash includes standard i0 dot h. 1862 01:34:51,790 --> 01:34:52,990 What is that doing? 1863 01:34:52,990 --> 01:34:56,610 It's grabbing the standard i0 dot h file and pasting it into the top 1864 01:34:56,610 --> 01:34:58,960 wherever it says hash includes standard i0 dot h. 1865 01:34:58,960 --> 01:35:02,480 >> And any hash define that we've seen, what is that doing? 1866 01:35:02,480 --> 01:35:06,730 Its copying the value that the hash defined is defined as and pasting that 1867 01:35:06,730 --> 01:35:08,500 wherever you are using the value. 1868 01:35:08,500 --> 01:35:13,400 So the preprocessor just does really simple text based operations. 1869 01:35:13,400 --> 01:35:15,870 It does nothing smart. 1870 01:35:15,870 --> 01:35:18,920 So everything else is more complicated. 1871 01:35:18,920 --> 01:35:22,970 >> So now that preprocessor is done, we actually compile. 1872 01:35:22,970 --> 01:35:24,320 So what does compiling mean? 1873 01:35:24,320 --> 01:35:27,310 We're now going from c code to assembly code. 1874 01:35:27,310 --> 01:35:27,570 Yeah? 1875 01:35:27,570 --> 01:35:28,820 >> AUDIENCE: [INAUDIBLE]? 1876 01:35:28,820 --> 01:35:32,390 1877 01:35:32,390 --> 01:35:34,220 >> ROB: Yeah, we caught that. 1878 01:35:34,220 --> 01:35:36,880 1879 01:35:36,880 --> 01:35:38,660 So compiling. 1880 01:35:38,660 --> 01:35:40,310 We're going from c to assembly. 1881 01:35:40,310 --> 01:35:42,470 So this is an actual language change. 1882 01:35:42,470 --> 01:35:45,240 Compiling itself means going from a higher level language to 1883 01:35:45,240 --> 01:35:47,340 a lower level language. 1884 01:35:47,340 --> 01:35:50,720 >> And c is a high level language compared to assembly. 1885 01:35:50,720 --> 01:35:52,320 What is assembly? 1886 01:35:52,320 --> 01:35:56,440 Its instructions that are, pretty much, made for your CPU. 1887 01:35:56,440 --> 01:35:59,130 But your computer still does not understand assembly. 1888 01:35:59,130 --> 01:36:01,570 It only understands ones and zeros. 1889 01:36:01,570 --> 01:36:06,160 So the next step is assembling, which brings us from these instructions that 1890 01:36:06,160 --> 01:36:08,760 your CPU understands and actually translates them, to 1891 01:36:08,760 --> 01:36:10,820 the ones and zeros. 1892 01:36:10,820 --> 01:36:13,570 >> So C to assembly to binary. 1893 01:36:13,570 --> 01:36:15,870 But I don't have an executable yet. 1894 01:36:15,870 --> 01:36:19,550 So think of the cs50 library. 1895 01:36:19,550 --> 01:36:23,070 We have provided you with a binary for this cs50 library, which has GetString 1896 01:36:23,070 --> 01:36:24,400 and GetInt and all that. 1897 01:36:24,400 --> 01:36:25,700 >> But the cs50 library-- 1898 01:36:25,700 --> 01:36:27,650 in and of itself-- is not executable. 1899 01:36:27,650 --> 01:36:29,570 It does not have a main function. 1900 01:36:29,570 --> 01:36:32,230 It's just a bunch of binary that you can use. 1901 01:36:32,230 --> 01:36:41,730 So linking is how we bring together all of these different binary files 1902 01:36:41,730 --> 01:36:43,110 into an actual executable. 1903 01:36:43,110 --> 01:36:45,900 One that you can type dot slash a dot out. 1904 01:36:45,900 --> 01:36:51,660 >> So this is like the file that you wrote,-- whatever your program is-- 1905 01:36:51,660 --> 01:36:53,620 Ceaser dot c. 1906 01:36:53,620 --> 01:36:55,100 But now it's been compiled down to binary. 1907 01:36:55,100 --> 01:36:56,480 So Ceaser dot o. 1908 01:36:56,480 --> 01:36:59,620 And this is our cs50 libraries binary. 1909 01:36:59,620 --> 01:37:02,284 And they're being combined into a single executable. 1910 01:37:02,284 --> 01:37:02,758 Yeah? 1911 01:37:02,758 --> 01:37:04,008 >> AUDIENCE: [INAUDIBLE]? 1912 01:37:04,008 --> 01:37:08,800 1913 01:37:08,800 --> 01:37:12,710 >> ROB: So first include, remember, the hash include is actually a 1914 01:37:12,710 --> 01:37:13,810 pre-processor step. 1915 01:37:13,810 --> 01:37:14,750 But that's separate. 1916 01:37:14,750 --> 01:37:20,730 If you're not using any functions that are outside of your single file then, 1917 01:37:20,730 --> 01:37:26,100 no, you don't need to link anything since you have everything. 1918 01:37:26,100 --> 01:37:30,310 >> That said, printf is being linked in. 1919 01:37:30,310 --> 01:37:32,820 If you ever use printf, that's something that needs to be linked in 1920 01:37:32,820 --> 01:37:35,740 because you didn't write that. 1921 01:37:35,740 --> 01:37:39,530 And, in fact, printf is automatically linked in. 1922 01:37:39,530 --> 01:37:42,760 You know how at the command line or when you type make, you see it have 1923 01:37:42,760 --> 01:37:46,690 dash l cs50, which has link in the cs50 library? 1924 01:37:46,690 --> 01:37:49,070 Printf, and stuff like that, is going to be linked in automatically. 1925 01:37:49,070 --> 01:37:51,730 1926 01:37:51,730 --> 01:37:53,930 Any other questions on anything? 1927 01:37:53,930 --> 01:37:56,280 >> AUDIENCE: [INAUDIBLE]? 1928 01:37:56,280 --> 01:37:58,300 >> ROB: Linking? 1929 01:37:58,300 --> 01:38:03,450 We have a whole bunch of different binary files. 1930 01:38:03,450 --> 01:38:06,410 This is the canonical example that we use is cs50 library. 1931 01:38:06,410 --> 01:38:09,960 We have compiled and given to you the binary for this cs50 library. 1932 01:38:09,960 --> 01:38:12,410 >> You want to use GetString in your program. 1933 01:38:12,410 --> 01:38:14,750 So you go and use GetString. 1934 01:38:14,750 --> 01:38:19,700 But without my binary code for GetString, when you compile your code 1935 01:38:19,700 --> 01:38:23,140 down, you can't actually run your program because GetString String is 1936 01:38:23,140 --> 01:38:25,080 not yet completely defined. 1937 01:38:25,080 --> 01:38:29,220 >> It's only when you link in my binary that contains GetString that now, all 1938 01:38:29,220 --> 01:38:31,130 right, I can actually execute GetString. 1939 01:38:31,130 --> 01:38:32,330 My file is complete. 1940 01:38:32,330 --> 01:38:34,208 And I can run this. 1941 01:38:34,208 --> 01:38:34,697 Yeah? 1942 01:38:34,697 --> 01:38:37,631 >> AUDIENCE: Does linking convert the binary to executable? 1943 01:38:37,631 --> 01:38:42,032 So even if you don't have other libraries, wouldn't it still be 1944 01:38:42,032 --> 01:38:44,477 necessary to translate the [INAUDIBLE]? 1945 01:38:44,477 --> 01:38:48,640 >> ROB: So an executable is still in binary. 1946 01:38:48,640 --> 01:38:51,750 It's just combining a whole bunch of binaries. 1947 01:38:51,750 --> 01:38:55,124 1948 01:38:55,124 --> 01:38:56,591 >> AUDIENCE: Thank you so much. 1949 01:38:56,591 --> 01:38:58,560 >> ROB: No problem. 1950 01:38:58,560 --> 01:38:59,540 Any other questions? 1951 01:38:59,540 --> 01:39:02,001 Otherwise, we're all set. 1952 01:39:02,001 --> 01:39:02,690 All right. 1953 01:39:02,690 --> 01:39:02,990 Thanks. 1954 01:39:02,990 --> 01:39:03,590 >> [APPLAUSE] 1955 01:39:03,590 --> 01:39:04,490 >> AUDIENCE: Thank you. 1956 01:39:04,490 --> 01:39:05,740 >> ROB: Yeah. 1957 01:39:05,740 --> 01:39:06,582