1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Hey everyone! 3 00:00:12,300 --> 00:00:13,890 Welcome back to section. 4 00:00:13,890 --> 00:00:17,480 So glad to see so many of you both here, and everyone who's watching online. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 So, as usual welcome back. 7 00:00:20,920 --> 00:00:24,360 I hope that you all had a lovely weekend, full of rest, relaxation. 8 00:00:24,360 --> 00:00:26,026 It was beautiful out yesterday. 9 00:00:26,026 --> 00:00:27,525 So, I hope you enjoyed the outdoors. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> So first a couple of announcements. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Grading. 14 00:00:32,700 --> 00:00:37,350 So, most of you should have gotten an email from me about your Scratch Pset, 15 00:00:37,350 --> 00:00:39,920 as well as grading for Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 So, just a couple things. 18 00:00:42,220 --> 00:00:45,150 Be sure to use check50 in style50. 19 00:00:45,150 --> 00:00:47,250 These are meant to be resources for you guys, 20 00:00:47,250 --> 00:00:50,660 to make sure that you're getting as many points as you can 21 00:00:50,660 --> 00:00:52,390 without needlessly losing them. 22 00:00:52,390 --> 00:00:54,407 So, things like style are very important. 23 00:00:54,407 --> 00:00:55,740 We are going to take off for it. 24 00:00:55,740 --> 00:00:58,115 Some of you may have already noticed that from your Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 And check50 is just a really easy way to make sure 27 00:01:01,450 --> 00:01:05,050 that we're actually returning what needs to be returned to the user, 28 00:01:05,050 --> 00:01:06,690 and that everything's working properly. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> On the second note, make sure your uploading things to the correct folder. 31 00:01:12,040 --> 00:01:14,470 It makes my life just a little bit more difficult 32 00:01:14,470 --> 00:01:18,836 if you upload Pset 2 into Pset 1 because when I download things, 33 00:01:18,836 --> 00:01:20,085 they don't download correctly. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 And I know it's a little wonky in a system to get used to, 36 00:01:24,560 --> 00:01:26,950 but just be super careful, if only for me, 37 00:01:26,950 --> 00:01:30,080 so that when you're getting emails at like 2 A.M. and I'm grading. 38 00:01:30,080 --> 00:01:33,710 If not cause I have to look all around for your Pset. 39 00:01:33,710 --> 00:01:34,440 Cool. 40 00:01:34,440 --> 00:01:37,270 >> I know it's early, but I totally got taken off guard 41 00:01:37,270 --> 00:01:40,800 by an essay that's due this Friday, that my professors were just like, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Remember, you have an essay due on Friday. 43 00:01:42,550 --> 00:01:45,780 So, I know no one likes to think about midterms, 44 00:01:45,780 --> 00:01:50,620 but your first quiz is on October 15th, which October is starting this week. 45 00:01:50,620 --> 00:01:53,290 So, it might be sooner than you expected is all. 46 00:01:53,290 --> 00:01:57,510 So that you're not thrown off guard when I mention next week's section that oh, 47 00:01:57,510 --> 00:02:00,560 your quiz next week, I thought I'd give you a little bit more 48 00:02:00,560 --> 00:02:01,500 of a heads up now. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> So, your problem set, number three. 51 00:02:04,660 --> 00:02:07,070 How people have read the spec out of curiosity? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 We got a couple. 55 00:02:10,229 --> 00:02:12,320 Kind of down from last week but that's OK. 56 00:02:12,320 --> 00:02:13,650 I know it was beautiful out. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 So Break Out. 59 00:02:16,660 --> 00:02:21,010 Definitely after you get done today read your spec at least 60 00:02:21,010 --> 00:02:25,240 try like downloading distribution code and running 61 00:02:25,240 --> 00:02:27,430 like the first initial thing that they ask you to. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Because we are using distribution code and a library 64 00:02:32,590 --> 00:02:36,790 that we've only been using-- --It's only the second time we've done this Pset, 65 00:02:36,790 --> 00:02:38,650 crazy things can happen with your appliance, 66 00:02:38,650 --> 00:02:41,370 and you want to find that out now versus later. 67 00:02:41,370 --> 00:02:45,570 >> Because if it's Thursday night or it's Wednesday night and for some reason 68 00:02:45,570 --> 00:02:48,912 your appliance just doesn't want to run with the library 69 00:02:48,912 --> 00:02:50,620 or with the distribution code, that means 70 00:02:50,620 --> 00:02:52,309 you can't even start doing the coding. 71 00:02:52,309 --> 00:02:54,100 Because you can't check to see if it works. 72 00:02:54,100 --> 00:02:55,975 Your not gonna be able to see if it compiles. 73 00:02:55,975 --> 00:03:00,500 You want to take care of those early in the week, when you can still email me 74 00:03:00,500 --> 00:03:03,100 or one of the other TFs, and we can get those fixed. 75 00:03:03,100 --> 00:03:05,410 Because those are issues that are going to stop you 76 00:03:05,410 --> 00:03:07,120 from making any real progress. 77 00:03:07,120 --> 00:03:10,055 It's not like one bug, that you can just kind of skip over. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 If you're having issues with your appliance or distribution code, 80 00:03:13,420 --> 00:03:16,211 you really want to get that taken care of sooner rather than later. 81 00:03:16,211 --> 00:03:20,410 So even if you're not gonna actually start coding, download the distribution 82 00:03:20,410 --> 00:03:24,040 code, read the spec, make sure everything's working there. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 If you can just do that, I promise your lives will be easier. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 And so you're probably going to do it right now right? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 So, any questions there? 89 00:03:33,950 --> 00:03:35,850 Any logistic things? 90 00:03:35,850 --> 00:03:36,910 Everyone's good? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer for those of you in the room and online. 93 00:03:41,700 --> 00:03:45,437 I'm going to be trying to switch between PowerPoint in the appliance 94 00:03:45,437 --> 00:03:47,270 because we are going to be doing some coding 95 00:03:47,270 --> 00:03:53,630 today by popular demand of the anonymous suggestion poll I sent out last week. 96 00:03:53,630 --> 00:03:55,480 So, we will be doing some coding. 97 00:03:55,480 --> 00:03:57,800 So, if you guys also want to fire up your appliances, 98 00:03:57,800 --> 00:04:02,910 and you should have got an email from me, with a sample file. 99 00:04:02,910 --> 00:04:04,310 Please feel free to do that. 100 00:04:04,310 --> 00:04:07,340 >> So, we're going to talk about GDB, which is a debugger. 101 00:04:07,340 --> 00:04:09,970 It's going to help you kind of figure out where 102 00:04:09,970 --> 00:04:11,860 things are going wrong in your code. 103 00:04:11,860 --> 00:04:15,370 It's really just a way for you to step through your code as it's happening, 104 00:04:15,370 --> 00:04:19,100 and be able to print out variables or see what's actually happening 105 00:04:19,100 --> 00:04:22,980 under the hood verses your program just running, it's like faulting, 106 00:04:22,980 --> 00:04:25,030 and you're like, no idea what just happened here. 107 00:04:25,030 --> 00:04:26,730 I don't know what line it failed at. 108 00:04:26,730 --> 00:04:29,040 I don't know where it went wrong. 109 00:04:29,040 --> 00:04:31,280 So, GDB is going to help you with that. 110 00:04:31,280 --> 00:04:35,240 Also, if you decide to continue yes, and take 61, 111 00:04:35,240 --> 00:04:38,430 it will really, really be your best friend, cause I can tell you 112 00:04:38,430 --> 00:04:40,840 because I'm going through that class. 113 00:04:40,840 --> 00:04:43,620 >> We're going to look at binary search, which if you guys remember 114 00:04:43,620 --> 00:04:47,540 the great phone book example spectacle from class. 115 00:04:47,540 --> 00:04:50,620 We'll be implementing that, and walking through that a little bit more, 116 00:04:50,620 --> 00:04:54,650 and then we're going through four different sorts, which are Bubble, 117 00:04:54,650 --> 00:04:56,285 Selection, Insertion, and Merge. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Cool. 120 00:04:58,330 --> 00:05:00,390 So, GDB as I mentioned, is a debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 And these are kind of the big things, the big functions or commands 123 00:05:09,370 --> 00:05:13,240 that you use within GDB, and I will walk you through a demo of it in a second. 124 00:05:13,240 --> 00:05:15,360 >> So, this is not just going to stay abstract. 125 00:05:15,360 --> 00:05:18,000 I'll try and make it as concrete as possible for you guys. 126 00:05:18,000 --> 00:05:19,870 So, break. 127 00:05:19,870 --> 00:05:22,200 It'll either be break like, some number, which 128 00:05:22,200 --> 00:05:26,900 represents a line in your program, or you can name a function. 129 00:05:26,900 --> 00:05:30,150 So, if you say break main, it will stop at main, 130 00:05:30,150 --> 00:05:32,400 and let you walk through that function. 131 00:05:32,400 --> 00:05:36,350 >> Likewise, if you have some external function like Swap or Cube, 132 00:05:36,350 --> 00:05:38,450 that we looked at last week. 133 00:05:38,450 --> 00:05:41,780 If you say break one of those, whenever your program hits that, 134 00:05:41,780 --> 00:05:44,290 it'll wait for you to tell it what to do. 135 00:05:44,290 --> 00:05:47,860 Before it will just execute so you could actually step inside the function 136 00:05:47,860 --> 00:05:49,020 and see what's going on. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 So, Next, just skips over the next line, goes over functions. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Step. 141 00:05:55,560 --> 00:05:56,810 These are all little abstract. 142 00:05:56,810 --> 00:06:00,530 So, I'm just going to run through them, but you'll see them in use in a second. 143 00:06:00,530 --> 00:06:01,810 >> Step into a function. 144 00:06:01,810 --> 00:06:04,170 So as I was saying, like with Swap, it would 145 00:06:04,170 --> 00:06:07,110 allow you to actually as if you're like physically stepping inside, 146 00:06:07,110 --> 00:06:10,990 you can mess with those variables, print out what they are, see what's going on. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 List will literally just print out the surrounding code. 149 00:06:14,830 --> 00:06:17,570 So, if you kind of forget where you are in your program, 150 00:06:17,570 --> 00:06:19,880 or you're wondering what's going on around it, 151 00:06:19,880 --> 00:06:23,790 this will just print out a segment of like five or six lines around it. 152 00:06:23,790 --> 00:06:26,080 So, you can get oriented about where you are. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Print some variable. 155 00:06:28,650 --> 00:06:34,590 So, if you have the key like in Caesar, that we'll look at. 156 00:06:34,590 --> 00:06:36,220 You can say Print Key at any point. 157 00:06:36,220 --> 00:06:40,070 It'll tell you what the value is so that, maybe somewhere along the way, 158 00:06:40,070 --> 00:06:42,070 you overwrote your key. 159 00:06:42,070 --> 00:06:45,495 You can actually tell that because you can actually observe that value. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> In the locals, just prints out your local variables. 162 00:06:48,780 --> 00:06:53,120 So, anytime you're within a loop, and you just want to see like, oh. 163 00:06:53,120 --> 00:06:54,270 What is my I? 164 00:06:54,270 --> 00:06:57,020 What is this key value that I initialize here? 165 00:06:57,020 --> 00:06:58,537 What is the message at this point? 166 00:06:58,537 --> 00:07:00,370 It will just print all of those, so that you 167 00:07:00,370 --> 00:07:04,330 don't have to individually say, Print I. Print Message. 168 00:07:04,330 --> 00:07:04,970 Print Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 And then Display. 171 00:07:07,700 --> 00:07:10,370 What that does is as you step through the program, 172 00:07:10,370 --> 00:07:13,980 it'll just make sure that it's displaying some certain variable 173 00:07:13,980 --> 00:07:14,780 at every point. 174 00:07:14,780 --> 00:07:17,160 So that you also-- --it's kind of a shortcut where 175 00:07:17,160 --> 00:07:19,530 you don't have to keep going like, oh. 176 00:07:19,530 --> 00:07:23,150 Print Key or Print I. It just will automatically do it for you. 177 00:07:23,150 --> 00:07:25,959 >> So, with that, we're going to see how this goes. 178 00:07:25,959 --> 00:07:28,000 I'm going to try and switch over to my appliance. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 See if I can do this. 181 00:07:31,271 --> 00:07:31,770 All. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 We're just going to mirror it. 184 00:07:42,370 --> 00:07:44,530 There's nothing crazy on my laptop anyways. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 This needs to be this one. 189 00:08:01,054 --> 00:08:01,795 It's so tiny. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Let's see if we can do this. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alice is obviously struggling here just a little bit, 195 00:08:15,305 --> 00:08:17,995 but we'll get it in a momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 We are just going to increase this. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Can everyone kind of see that? 202 00:08:31,679 --> 00:08:32,470 Maybe a little bit? 203 00:08:32,470 --> 00:08:33,594 I know it's a little small. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 You can't quite figure out how to make this larger. 206 00:08:37,530 --> 00:08:38,350 If anyone knows. 207 00:08:38,350 --> 00:08:40,309 Does anyone know how to make it larger? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 We're going to roll with it . 210 00:08:42,140 --> 00:08:45,801 Doesn't matter anyways because it's just that's the code that you guys should 211 00:08:45,801 --> 00:08:46,300 have. 212 00:08:46,300 --> 00:08:48,310 >> What's more important is the terminal here. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 And we have here Why is it so small? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Settings. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 True Ike. 220 00:09:09,500 --> 00:09:10,880 How's this? 221 00:09:10,880 --> 00:09:11,770 Out of there. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Is that better for everyone? 224 00:09:21,810 --> 00:09:22,525 OK,. 225 00:09:22,525 --> 00:09:23,025 Cool. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> You know when you're in a CS class technical difficulties 228 00:09:28,220 --> 00:09:32,971 are kind of part of the-- So, let's clear this. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 So, right here in section, which we had here. 231 00:09:38,060 --> 00:09:40,830 Caesar is an executable file. 232 00:09:40,830 --> 00:09:41,800 So I made it. 233 00:09:41,800 --> 00:09:46,370 So, one thing to realize with GDB is that it only works on executable files. 234 00:09:46,370 --> 00:09:48,040 So, you can't run it on a dotsy. 235 00:09:48,040 --> 00:09:50,532 You have to actually make sure that your code compiles, 236 00:09:50,532 --> 00:09:51,865 and that it can actually be run. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> So, make sure that if it doesn't compile, get it to compile, 239 00:09:56,186 --> 00:09:57,810 so that you can kind of run through it. 240 00:09:57,810 --> 00:10:04,590 So, to start GDB, all you do, Gloria type GDB, and then just the 241 00:10:04,590 --> 00:10:06,250 file that you want. 242 00:10:06,250 --> 00:10:08,240 I always misspell Caesar. 243 00:10:08,240 --> 00:10:11,730 But you want to make sure since it's an executable, 244 00:10:11,730 --> 00:10:14,210 ti's dot flash so that means you're going 245 00:10:14,210 --> 00:10:19,240 to run CSI you're going to execute this files either with the debugger. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 So, you do that, you get this kind of gibberish. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 It's just all things about debugger. 250 00:10:25,750 --> 00:10:28,200 You don't really have to worry about it right now. 251 00:10:28,200 --> 00:10:31,460 And as you see, we have this open parens, GDP, close parens, 252 00:10:31,460 --> 00:10:34,690 and just kind of looks like our command line, right? 253 00:10:34,690 --> 00:10:37,010 >> So, what we want to do-- --So, the first thing 254 00:10:37,010 --> 00:10:39,570 is we want to choose a place to break it. 255 00:10:39,570 --> 00:10:42,332 So, there is one bug in this Caesar program 256 00:10:42,332 --> 00:10:44,290 that I introduce, that we're going to find out. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 It What it does is it takes the input Barfoo in all caps, and for some reason 259 00:10:56,350 --> 00:11:01,950 it doesn't change A. It just leaves it alone, Is everything else correct, 260 00:11:01,950 --> 00:11:03,980 but the second letter A remains unchanged. 261 00:11:03,980 --> 00:11:07,120 So, we're going to try and figure out why that is. 262 00:11:07,120 --> 00:11:10,440 So, the first thing you typically want to do whenever you start on GDB 263 00:11:10,440 --> 00:11:12,010 is figure out where to break it. 264 00:11:12,010 --> 00:11:14,956 >> So Caesar is a pretty short program. 265 00:11:14,956 --> 00:11:16,330 We just have one function, right? 266 00:11:16,330 --> 00:11:18,520 What was our function in Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 There's only one function, Main right? 269 00:11:24,350 --> 00:11:26,490 Main is a function for all your programs. 270 00:11:26,490 --> 00:11:29,230 If you didn't have Main, I might be a little worried right now, 271 00:11:29,230 --> 00:11:31,000 but I hope you all had Main in there. 272 00:11:31,000 --> 00:11:34,150 So, what we can do is we can just break Main, just like that. 273 00:11:34,150 --> 00:11:35,190 So, it says, OK. 274 00:11:35,190 --> 00:11:37,430 We set our breakpoint one there. 275 00:11:37,430 --> 00:11:42,870 >> So, now the thing to remember is Caesar takes one command line argument right 276 00:11:42,870 --> 00:11:45,150 and we haven't done that anywhere yet. 277 00:11:45,150 --> 00:11:47,560 So, what you do is when you actually go to run 278 00:11:47,560 --> 00:11:51,540 the program, any program that you're running in GDB that needs command line 279 00:11:51,540 --> 00:11:55,010 arguments, you're going to input when you first start running it. 280 00:11:55,010 --> 00:11:59,280 So, in this case, we do Run with a key of three. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 And it will actually start. 283 00:12:02,040 --> 00:12:08,480 >> So, if you see here, we have If RC is not equal to 2. 284 00:12:08,480 --> 00:12:12,210 So if you guys all have that file that I sent out up 285 00:12:12,210 --> 00:12:15,100 you'll see that that's like the first line our main function, right? 286 00:12:15,100 --> 00:12:17,890 It's checking to see if we have the correct number of arguments. 287 00:12:17,890 --> 00:12:20,620 So, if you're wondering if RC is correct, 288 00:12:20,620 --> 00:12:23,250 you can do something just like Print RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC is two, which is what we expected, right? 291 00:12:28,640 --> 00:12:32,010 >> So, we can go Next, and continue through. 292 00:12:32,010 --> 00:12:33,200 So, we have some key there. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 And we can print out our key to make sure that's correct. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interesting. 297 00:12:39,500 --> 00:12:41,210 Not quite what we expected. 298 00:12:41,210 --> 00:12:44,810 So, one thing to realize with GDB also, is 299 00:12:44,810 --> 00:12:49,000 that it's not until you actually hit Next, that the line that you just saw 300 00:12:49,000 --> 00:12:50,720 is actually executed. 301 00:12:50,720 --> 00:12:53,870 So, in this case Key hasn't been assigned yet. 302 00:12:53,870 --> 00:12:57,050 So, Key is some garbage value that you see on the bottom there. 303 00:12:57,050 --> 00:13:03,680 Negative $120-- --It's one billion and something odd things right? 304 00:13:03,680 --> 00:13:05,340 It's not the Key that we expected. 305 00:13:05,340 --> 00:13:10,720 But if we hit Next, and then we try and Print key, it's three. 306 00:13:10,720 --> 00:13:11,710 >> Everyone see that? 307 00:13:11,710 --> 00:13:13,780 So, if you get something that you're like, wait. 308 00:13:13,780 --> 00:13:15,540 This is completely wrong, and I don't know 309 00:13:15,540 --> 00:13:20,150 how this would happen because all I want to do is assign a number, a variable, 310 00:13:20,150 --> 00:13:22,900 try hitting Next, try printing it again, and see if that works. 311 00:13:22,900 --> 00:13:27,830 Because it's only going to execute and actually assign something after you 312 00:13:27,830 --> 00:13:29,340 hit Next. 313 00:13:29,340 --> 00:13:30,336 Make sense to everyone? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: When you random numbers what does that mean? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: It's just random. 317 00:13:34,790 --> 00:13:35,710 It's just garbage. 318 00:13:35,710 --> 00:13:38,320 It's just something that your computer will randomly assign. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Cool. 321 00:13:40,220 --> 00:13:45,760 So, now we can move through, and so now we have this plain text GetString. 322 00:13:45,760 --> 00:13:48,600 So, let me just introduce what will happen when we hit Next here. 323 00:13:48,600 --> 00:13:51,320 Our GDB kind of disappears, right? 324 00:13:51,320 --> 00:13:55,720 That's because GetString is now executing, right? 325 00:13:55,720 --> 00:14:01,460 So, when we saw plain text equals GetString, open parens and parens, 326 00:14:01,460 --> 00:14:04,380 and we hit Next, that has actually executed now. 327 00:14:04,380 --> 00:14:06,580 So, it's waiting for us to input something. 328 00:14:06,580 --> 00:14:13,560 >> So, we're going to input our food which is what it's failing as I told you 329 00:14:13,560 --> 00:14:18,020 and that just says that it's finished executing, that the closed 330 00:14:18,020 --> 00:14:19,980 bracket means it's exiting out of that loop. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 So, we can hit Next, and now, as I'm sure you're all familiar from Caesar, 333 00:14:25,420 --> 00:14:27,260 this is, what's this line going to do. 334 00:14:27,260 --> 00:14:32,030 It's for Int I equals 0, N equals Strlen, plain text, and then 335 00:14:32,030 --> 00:14:33,960 I is less than n, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 What is this loop going to do? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Open your message. 339 00:14:39,160 --> 00:14:39,770 Cool. 340 00:14:39,770 --> 00:14:41,330 So, let's start doing that. 341 00:14:41,330 --> 00:14:47,210 >> So, should this condition match, for our first one? 342 00:14:47,210 --> 00:14:52,250 If it's a B, it's plain text I. We can get information about our locals. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 So, I is zero, and if six, which we expect, and our key is three. 345 00:14:57,970 --> 00:14:59,227 All that make sense, right? 346 00:14:59,227 --> 00:15:01,310 Those numbers are all exactly what they should be. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 So, hum? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: I have random numbers for mine. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Well, we can check-- --we can chat about that in a second. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 But you should be getting this. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 So, if we have a capital B for our first one, 356 00:15:20,130 --> 00:15:22,080 this condition should catch it, right? 357 00:15:22,080 --> 00:15:27,120 So, if we hit Next, we see that this If actually executes. 358 00:15:27,120 --> 00:15:29,220 Because if you're following along in your code, 359 00:15:29,220 --> 00:15:33,460 this line here, where plain text I is replaced with this arithmetic, 360 00:15:33,460 --> 00:15:35,720 only executes if the If condition is correct right? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB is only going to show you things that are actually executing. 363 00:15:40,240 --> 00:15:45,140 So if this If condition wasn't met, it's just going to skip to the next line. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 So, we have that. 366 00:15:48,510 --> 00:15:51,171 This bracket means it's closed out of that loop now. 367 00:15:51,171 --> 00:15:52,420 So, it's going to start again. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Just like that. 370 00:15:56,280 --> 00:15:59,120 So, that we can get info about our locals here, 371 00:15:59,120 --> 00:16:02,575 and we see that our first letter has changed, right? 372 00:16:02,575 --> 00:16:05,150 It's now an E, as it should be. 373 00:16:05,150 --> 00:16:07,360 So, we can continue on. 374 00:16:07,360 --> 00:16:08,500 >> And we have this check. 375 00:16:08,500 --> 00:16:09,916 And this check should work, right? 376 00:16:09,916 --> 00:16:12,570 It's A. It should be changed three letters forward. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 But if you notice, we get something different. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 So in this case up here, it caught it, and so this line executed, 381 00:16:22,860 --> 00:16:28,620 which modified our B. But, in this case here, 382 00:16:28,620 --> 00:16:32,860 we have that it just skipped it, and went to the [? L siff. ?] 383 00:16:32,860 --> 00:16:34,660 So something's going on there. 384 00:16:34,660 --> 00:16:37,780 What that's telling you is that, we know that it should catch here, 385 00:16:37,780 --> 00:16:39,200 but it's not. 386 00:16:39,200 --> 00:16:42,210 Can anyone see what our problem is in that line? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 It's a very minute thing. 389 00:16:46,969 --> 00:16:48,510 And you could also look at your code. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 It's also line-- forget what line it is in there-- but it's in the [INAUDIBLE]. 392 00:16:54,940 --> 00:16:55,480 Yes? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: It's on the greater than page if you read it in the book. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Exactly. 395 00:16:59,430 --> 00:17:02,620 So, the debugger couldn't tell you that, but the debugger 396 00:17:02,620 --> 00:17:05,880 could get you down to a line that you know is not functioning. 397 00:17:05,880 --> 00:17:09,319 And sometimes, when especially later in the semester, when 398 00:17:09,319 --> 00:17:12,910 you're dealing with a hundred, a hundred few lines of code, and you 399 00:17:12,910 --> 00:17:16,190 don't know where it's failing, this is a great way to do it. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 So, we found our bug. 402 00:17:18,989 --> 00:17:21,530 You can fix it in your file, and then you could run it again, 403 00:17:21,530 --> 00:17:23,029 and everything would work perfectly. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 And the biggest thing is this can seem like, OK. 406 00:17:30,590 --> 00:17:31,090 Yeah. 407 00:17:31,090 --> 00:17:31,370 Cool. 408 00:17:31,370 --> 00:17:32,744 You knew what you're looking for. 409 00:17:32,744 --> 00:17:34,910 So, you knew what to do. 410 00:17:34,910 --> 00:17:39,021 >> GDB can be super helpful because you can print out all these things that you 411 00:17:39,021 --> 00:17:39,520 wouldn't. 412 00:17:39,520 --> 00:17:41,160 It's much more useful than PrintF. 413 00:17:41,160 --> 00:17:43,440 How many of you use like PrintF statements 414 00:17:43,440 --> 00:17:46,200 to figure out where a bug was, right? 415 00:17:46,200 --> 00:17:48,450 So, with this, you don't have to keep going back, 416 00:17:48,450 --> 00:17:51,139 and like commenting in PrintF, or commenting out, 417 00:17:51,139 --> 00:17:52,930 and figure out what you should be printing. 418 00:17:52,930 --> 00:17:55,670 This actually just allows you to step through, print out things 419 00:17:55,670 --> 00:18:00,000 as you're going through, so, you can observe how they change in real time, 420 00:18:00,000 --> 00:18:02,190 as your program is running. 421 00:18:02,190 --> 00:18:04,390 >> And it does take a little bit of getting used to. 422 00:18:04,390 --> 00:18:07,850 I would highly recommend just kind of being a little frustrated with it 423 00:18:07,850 --> 00:18:08,930 for right now. 424 00:18:08,930 --> 00:18:13,450 If you spend an hour over the next week learning how to use GDB, 425 00:18:13,450 --> 00:18:16,140 you will save yourself so much time later on. 426 00:18:16,140 --> 00:18:18,750 And literally. we tell this to people every year, 427 00:18:18,750 --> 00:18:23,890 and I remember when I took the class, I was like, I will be fine. 428 00:18:23,890 --> 00:18:24,700 No. 429 00:18:24,700 --> 00:18:27,030 Pset 6 came on and I was like, I'm gonna learn 430 00:18:27,030 --> 00:18:29,500 how to use GDB because I don't know what's going on here. 431 00:18:29,500 --> 00:18:32,940 >> So if you take the time so use it on smaller programs 432 00:18:32,940 --> 00:18:35,697 that you're going to be working on, like working 433 00:18:35,697 --> 00:18:37,530 through something like Visionare, like this. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Or if you want extra practice, I'm sure I could come up with buggy programs, 436 00:18:42,850 --> 00:18:45,300 for you to debug if you'd like. 437 00:18:45,300 --> 00:18:49,300 >> But if you just take some time to get used to it, just play around with it, 438 00:18:49,300 --> 00:18:50,550 it will really serve you well. 439 00:18:50,550 --> 00:18:52,591 And it's really one of those things that you just 440 00:18:52,591 --> 00:18:57,340 have to try, and get your hands dirty with, before you really understand it. 441 00:18:57,340 --> 00:19:02,090 I really only understood it once I had to debug things with it, 442 00:19:02,090 --> 00:19:08,170 and it's much nicer to have an idea of how to debug sooner rather than later. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Cool. 445 00:19:09,625 --> 00:19:12,960 I know that's kind of like a crash course in GDB, 446 00:19:12,960 --> 00:19:16,400 and I will definitely work on getting these to look bigger next time. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Cool. 449 00:19:18,280 --> 00:19:20,390 >> So, if we go back to our PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Is this going to work? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Yes. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 So, if you ever need any of those again, there's the list. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 So Binary Search, which everyone remembers the great spectacle of David 459 00:19:40,830 --> 00:19:42,259 ripping phone books in half. 460 00:19:42,259 --> 00:19:44,050 I don't really get the phone books anymore, 461 00:19:44,050 --> 00:19:46,530 because like where do you get phone books these days? 462 00:19:46,530 --> 00:19:48,220 I really do not know. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 The Binary Search. 465 00:19:50,590 --> 00:19:52,464 Does anyone remember how Binary Search works? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Anyone at all? 468 00:19:55,220 --> 00:19:56,325 Yeah? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: You know when you look at which half 470 00:19:58,283 --> 00:20:01,146 it would be in, Based on that, and get rid of the other half. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Exactly. 472 00:20:01,896 --> 00:20:06,290 So, Binary Search, it's kind of a-- --we like to call it divide and conquer. 473 00:20:06,290 --> 00:20:09,170 So, what you'll do is you'll look in the middle, 474 00:20:09,170 --> 00:20:11,990 and you'll see if it matches what you're looking for. 475 00:20:11,990 --> 00:20:15,420 And if it doesn't, then you try to figure out, is it going to be left 476 00:20:15,420 --> 00:20:16,450 half or the right half. 477 00:20:16,450 --> 00:20:19,325 So, this might be if you're looking at something that's alphabetized, 478 00:20:19,325 --> 00:20:20,720 you see, oh. 479 00:20:20,720 --> 00:20:22,750 Does Allison come before M? 480 00:20:22,750 --> 00:20:23,250 Yes. 481 00:20:23,250 --> 00:20:25,030 So, we're going to look at the first half. 482 00:20:25,030 --> 00:20:26,450 >> Or it could be like with numbers. 483 00:20:26,450 --> 00:20:28,830 Anything that you can compare, it can be sorted. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 You can use binary search on. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 So, anyone remember this graph or what this is? 488 00:20:37,455 --> 00:20:39,520 It's Asymptotic Complexity. 489 00:20:39,520 --> 00:20:42,830 So, this graph just describes how long it 490 00:20:42,830 --> 00:20:46,230 takes you to solve a problem as you increase the number of things 491 00:20:46,230 --> 00:20:47,090 that you're using. 492 00:20:47,090 --> 00:20:51,260 >> So, we have N, which is linear time. 493 00:20:51,260 --> 00:20:54,560 If N over two, which is slightly better, still grows super fast. 494 00:20:54,560 --> 00:20:58,360 And then we have Login, which is what we consider Binary Search. 495 00:20:58,360 --> 00:21:03,630 If we notice, as your problem gets much and much larger, 496 00:21:03,630 --> 00:21:06,600 the time it takes you to solve it doesn't really increase that much. 497 00:21:06,600 --> 00:21:09,010 It's like comparable here in the beginning. 498 00:21:09,010 --> 00:21:10,060 You're like, OK. 499 00:21:10,060 --> 00:21:13,000 Anything here doesn't really matter which one we use, 500 00:21:13,000 --> 00:21:16,220 but you get out to a million, a billion. 501 00:21:16,220 --> 00:21:20,010 You're trying to find some-- --you're trying to find a needle in a haystack. 502 00:21:20,010 --> 00:21:21,550 >> I think you want this problem. 503 00:21:21,550 --> 00:21:25,850 You want this complexity, not linear because for all you 504 00:21:25,850 --> 00:21:30,049 know your gonna be searching through each individual needle, thing of hay, 505 00:21:30,049 --> 00:21:31,340 trying to look for your needle. 506 00:21:31,340 --> 00:21:34,730 And that's not too fun in my opinion. 507 00:21:34,730 --> 00:21:35,500 I like fast. 508 00:21:35,500 --> 00:21:36,620 I like efficient. 509 00:21:36,620 --> 00:21:40,450 And as hardworking students you guys are, you know work smarter, 510 00:21:40,450 --> 00:21:43,010 not harder type thing, how you can make up these algorithms. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> So, we're going to walk through just a quick example. 513 00:21:47,910 --> 00:21:51,090 I think you guys should have a hand on Binary Search, 514 00:21:51,090 --> 00:21:54,352 but in case anyone is a little fuzzy, want to reinforce it, 515 00:21:54,352 --> 00:21:56,310 we're going to just go through an example here. 516 00:21:56,310 --> 00:21:59,490 So, we're looking for if the array contains seven. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> So, first thing we do is look in the middle, right? 519 00:22:06,010 --> 00:22:09,340 And also you're going to be coding Binary Search in just a second. 520 00:22:09,340 --> 00:22:11,310 So, it's going to be fun. 521 00:22:11,310 --> 00:22:13,710 So we look in the middle little arrays 3. 522 00:22:13,710 --> 00:22:15,501 Does 3 equal 7? 523 00:22:15,501 --> 00:22:16,000 Doesn't. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 It's six. 526 00:22:19,550 --> 00:22:21,480 So, is it less than or greater than seven? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Less than. 529 00:22:23,960 --> 00:22:24,570 Yes. 530 00:22:24,570 --> 00:22:25,170 Nice job guys. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 I feel I like I should have candy because I 533 00:22:27,360 --> 00:22:29,460 want to throw it out into the yards. 534 00:22:29,460 --> 00:22:30,270 It's what I am going to do next week. 535 00:22:30,270 --> 00:22:31,436 It will keep you guys sharp. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> So, we throw away that first half, right? 538 00:22:34,690 --> 00:22:35,670 it was less than. 539 00:22:35,670 --> 00:22:39,325 we know that everything on that left hand side 540 00:22:39,325 --> 00:22:41,700 is going to be less than what we're actually looking for. 541 00:22:41,700 --> 00:22:43,491 So, there's no need to pay attention to it. 542 00:22:43,491 --> 00:22:45,120 Just forget about it. 543 00:22:45,120 --> 00:22:48,720 So, now we look at our right hand side, and we look at the middle over there, 544 00:22:48,720 --> 00:22:50,510 and now it's nine. 545 00:22:50,510 --> 00:22:55,510 So, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Greater than what we're looking for, right? 547 00:22:57,470 --> 00:22:59,860 So, we're going to throw away everything to the right. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Like that. 550 00:23:01,940 --> 00:23:03,700 Now, all we're left with is one. 551 00:23:03,700 --> 00:23:07,760 So we check, is this one what we're looking for? it is. 552 00:23:07,760 --> 00:23:08,970 We found what we wanted. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 So we're done. 555 00:23:11,690 --> 00:23:12,550 Bilinear Search. 556 00:23:12,550 --> 00:23:15,740 >> And if you notice, we had seven inputs there. 557 00:23:15,740 --> 00:23:24,320 It only took us like three times, but if you're doing like a billion, 558 00:23:24,320 --> 00:23:28,190 you guys know how many steps it would take if we had four billion things? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Any guesses? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 It's 32. 563 00:23:33,960 --> 00:23:37,110 32 steps to find something in a four billion 564 00:23:37,110 --> 00:23:39,650 element array because of powers of two. 565 00:23:39,650 --> 00:23:43,550 So two is to 32, is to four billion. 566 00:23:43,550 --> 00:23:50,430 >> So pretty crazy how you're still within like a fairly small number of steps 567 00:23:50,430 --> 00:23:52,650 to find something in four billion elements. 568 00:23:52,650 --> 00:23:55,730 So on that note, we're going to code this 569 00:23:55,730 --> 00:23:58,950 so you guys can actually kind of see how this works. 570 00:23:58,950 --> 00:24:01,520 All right, so you guys can code. 571 00:24:01,520 --> 00:24:04,100 I'm going to let you guys talk for a little bit. 572 00:24:04,100 --> 00:24:07,970 Get to know people around you, which is what someone wanted from last section. 573 00:24:07,970 --> 00:24:10,280 >> So get to know the people around you. 574 00:24:10,280 --> 00:24:11,305 Talk for a little bit. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 And all I want from you guys right now is just 577 00:24:15,730 --> 00:24:17,575 try to create an outline of pseudocode. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 All I want from you guys is you're just going to fill in this while case. 583 00:24:29,520 --> 00:24:32,170 So I have set these upper and lower bounds which 584 00:24:32,170 --> 00:24:35,250 represent the beginning and end of our array. 585 00:24:35,250 --> 00:24:40,440 And you are going to actually loop through and figure out 586 00:24:40,440 --> 00:24:42,470 what we're doing within this while loop. 587 00:24:42,470 --> 00:24:45,810 >> So if you can figure out-- I have a hint there-- what are the cases 588 00:24:45,810 --> 00:24:46,640 that we have here? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 So if you want to figure out the cases, we will pseudocode those 591 00:24:51,560 --> 00:24:53,350 and then we'll actually code them. 592 00:24:53,350 --> 00:24:55,330 And it's going to be, I think, hopefully it'll 593 00:24:55,330 --> 00:24:56,788 be a little easier than you expect. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Because it's not that much code, actually, which is really cool. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENT: [INAUDIBLE]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 INSTRUCTOR: Yes. 601 00:25:37,650 --> 00:25:38,595 There was something to find in the middle. 602 00:25:38,595 --> 00:25:39,552 >> STUDENT: So we can use that. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> INSTRUCTOR: Perfect. 605 00:25:40,603 --> 00:25:42,950 So that's the first thing we need to do. 606 00:25:42,950 --> 00:25:44,330 So find the middle. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Great. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 So do you have an idea of how we might actually find the middle with code? 611 00:25:55,010 --> 00:25:55,980 >> STUDENT: Yeah. 612 00:25:55,980 --> 00:25:57,000 n over 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 INSTRUCTOR: So n over 2. 615 00:25:59,500 --> 00:26:05,170 So one thing to remember is that your upper and lower bounds change. 616 00:26:05,170 --> 00:26:08,110 We keep constricting the part of the array we're looking to. 617 00:26:08,110 --> 00:26:11,970 So n over 2 will only work for the first thing we do. 618 00:26:11,970 --> 00:26:17,810 So taking upper and lower into account, how might we get that middle element? 619 00:26:17,810 --> 00:26:20,640 Because we want the middle between upper and lower, right? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENT: [INAUDIBLE]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> INSTRUCTOR: So we have some middle. 625 00:26:28,080 --> 00:26:32,730 And it'll be upper plus lower over 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Awesome. 628 00:26:35,690 --> 00:26:36,570 There we go. 629 00:26:36,570 --> 00:26:37,280 One line down. 630 00:26:37,280 --> 00:26:38,560 You guys are on your way. 631 00:26:38,560 --> 00:26:41,400 So now that we have our middle, what do we want to do? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Just in general. 634 00:26:45,900 --> 00:26:47,734 You don't have to code it. 635 00:26:47,734 --> 00:26:48,335 Yes. 636 00:26:48,335 --> 00:26:49,210 STUDENT: [INAUDIBLE]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 INSTRUCTOR: So it's plus because you're finding the average between the two 639 00:27:10,310 --> 00:27:10,810 of them. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 So if you think of them as kind of increasing in from the sides, 642 00:27:17,370 --> 00:27:21,640 think about it as you approach the middle, you want like that. 643 00:27:21,640 --> 00:27:27,150 So if you were on either side of the middle, and we have like 5 and 7. 644 00:27:27,150 --> 00:27:31,440 When you add them together you get 12, you divide by 2, is 6. 645 00:27:31,440 --> 00:27:33,726 >> Sometimes it's hard to explain why that works, 646 00:27:33,726 --> 00:27:35,600 but if you work through an example sometimes, 647 00:27:35,600 --> 00:27:37,962 it'll help you figure out if it should be plus or minus. 648 00:27:37,962 --> 00:27:38,846 Yes. 649 00:27:38,846 --> 00:27:40,830 >> STUDENT: [INAUDIBLE] exactly in the middle 650 00:27:40,830 --> 00:27:43,950 if they had a case where there's a lot of smaller numbers 651 00:27:43,950 --> 00:27:45,860 and like one large number? 652 00:27:45,860 --> 00:27:49,750 >> INSTRUCTOR: So all you need is the middle of the array. 653 00:27:49,750 --> 00:27:53,010 So if you had a bunch of small numbers and then one really large number 654 00:27:53,010 --> 00:27:54,799 at the end, it doesn't matter. 655 00:27:54,799 --> 00:27:56,840 All that matters is that they're sorted, you just 656 00:27:56,840 --> 00:27:59,339 want to look at the middle of the array because you're still 657 00:27:59,339 --> 00:28:00,700 slicing your problem in half. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Cool. 660 00:28:03,680 --> 00:28:06,430 So now that we have the middle, what do we do next? 661 00:28:06,430 --> 00:28:07,150 >> STUDENT: Compare. 662 00:28:07,150 --> 00:28:08,150 INSTRUCTOR: The compare. 663 00:28:08,150 --> 00:28:11,670 So compare middle to value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Cool. 666 00:28:15,160 --> 00:28:17,950 So you see up here we have this value we want up here. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Remember this is an array. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 So middle refers to the index. 671 00:28:26,970 --> 00:28:29,785 So we want to do values of middle. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Don't forget if you want to compare, double equals. 674 00:28:35,650 --> 00:28:38,250 You do single equals you're just going to reassign it, 675 00:28:38,250 --> 00:28:41,090 and then, of course, it's going to be the value you want. 676 00:28:41,090 --> 00:28:42,300 So don't do that. 677 00:28:42,300 --> 00:28:44,350 >> So we're going to see if the values at the middle 678 00:28:44,350 --> 00:28:46,460 is equal to the value we want. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Don't forget your braces. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox should go away. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 So what do we do in this case? 685 00:28:56,200 --> 00:28:59,360 If it's what do we want to return? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 We're trying to say. 688 00:29:02,626 --> 00:29:03,440 >> STUDENT: Print off. 689 00:29:03,440 --> 00:29:05,314 >> INSTRUCTOR: Well, we don't want to print off. 690 00:29:05,314 --> 00:29:08,220 So this is a bool here, so we want to return true or false. 691 00:29:08,220 --> 00:29:12,280 We're saying, is this number an [? RRA? ?] So if it is, 692 00:29:12,280 --> 00:29:13,788 we just return it true. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 If I can spell true. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENT: Why wouldn't you return zero? 697 00:29:20,805 --> 00:29:22,930 INSTRUCTOR: So you could return zero if you wanted. 698 00:29:22,930 --> 00:29:26,780 But in this case because our function returns a bool, 699 00:29:26,780 --> 00:29:28,962 we need to return either true or false. 700 00:29:28,962 --> 00:29:30,920 STUDENT: When you're saying boolean expression, 701 00:29:30,920 --> 00:29:33,450 can you set it equal to false? 702 00:29:33,450 --> 00:29:39,860 Like if I want to say, if this condition is not met, like is upper equals false. 703 00:29:39,860 --> 00:29:42,332 Will it understand if you just put false on the other side? 704 00:29:42,332 --> 00:29:43,040 INSTRUCTOR: Yeah. 705 00:29:43,040 --> 00:29:44,820 So actually if you're ever doing something 706 00:29:44,820 --> 00:29:49,600 like is upper or is lower, that returns true or false 707 00:29:49,600 --> 00:29:53,850 and it's actually bad style to say equals equals true or equals 708 00:29:53,850 --> 00:29:54,840 equals false. 709 00:29:54,840 --> 00:30:00,210 You want to use that result as itself as your check. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Not what I wanted. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 That's what I wanted. 714 00:30:09,240 --> 00:30:13,205 So in the case of you're asking about something like save this in c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> So if we have int main (void) and something like this. 717 00:30:25,150 --> 00:30:31,922 And you have if is upper of some input and you're 718 00:30:31,922 --> 00:30:33,630 asking if you can do something like this? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Right? 721 00:30:35,679 --> 00:30:37,470 STUDENT: I was trying to do it [INAUDIBLE]. 722 00:30:37,470 --> 00:30:38,450 Because if it's-- 723 00:30:38,450 --> 00:30:39,200 INSTRUCTOR: Right. 724 00:30:39,200 --> 00:30:41,197 So you want this to be false, right? 725 00:30:41,197 --> 00:30:41,780 STUDENT: Yeah. 726 00:30:41,780 --> 00:30:45,960 INSTRUCTOR: So in this case you want it to execute if it's not true. 727 00:30:45,960 --> 00:30:50,510 So the cool thing you do there is this. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 So remember exclamation point negates things? 730 00:30:55,650 --> 00:30:58,270 It says [INAUDIBLE] means not. 731 00:30:58,270 --> 00:31:03,590 So if we look at just this part here, you'd 732 00:31:03,590 --> 00:31:05,740 say that evaluates to false as you want it to. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Not false is true which means this would execute. 735 00:31:09,880 --> 00:31:11,037 Does that make sense? 736 00:31:11,037 --> 00:31:11,620 STUDENT: Yeah. 737 00:31:11,620 --> 00:31:12,453 INSTRUCTOR: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 So we could just return true in this case. 741 00:31:16,330 --> 00:31:20,357 So now we have two other cases in this case. 742 00:31:20,357 --> 00:31:21,565 What are our two other cases? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Let's just do it this way. 745 00:31:32,900 --> 00:31:40,660 So let's start with else if values at the middle 746 00:31:40,660 --> 00:31:43,230 is less than the value we want. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 So our value in the middle is less than the value that we're looking for. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> So which bound do you think we want to update? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Upper or lower? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Upper? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 So which side of the array are we going to be looking at? 757 00:32:06,470 --> 00:32:07,500 >> STUDENT: The lower. 758 00:32:07,500 --> 00:32:09,750 >> INSTRUCTOR: We are we going to be looking at the left. 759 00:32:09,750 --> 00:32:11,120 So else if little value is less. 760 00:32:11,120 --> 00:32:14,730 So your middle value here is less than what we want. 761 00:32:14,730 --> 00:32:17,202 So we want to take the right side of our array. 762 00:32:17,202 --> 00:32:18,910 So we're going to update our lower bound. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 So we'll reassign our lower. 765 00:32:23,020 --> 00:32:25,221 And what do you think lower should be? 766 00:32:25,221 --> 00:32:26,304 STUDENT: The middle value? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 INSTRUCTOR: So the middle value-- 769 00:32:28,820 --> 00:32:30,136 STUDENT: Plus 1. 770 00:32:30,136 --> 00:32:31,010 INSTRUCTOR: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Can anyone tell me why we have that plus 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENT: [? No value ?] is more equal to it. 774 00:32:35,730 --> 00:32:36,120 >> INSTRUCTOR: Right. 775 00:32:36,120 --> 00:32:38,661 Because we already know that our middle value is not equal to 776 00:32:38,661 --> 00:32:42,750 it and we want to exclude it from all subsequent searches. 777 00:32:42,750 --> 00:32:46,360 If you forget that plus 1, this will like loop indefinitely. 778 00:32:46,360 --> 00:32:49,620 And you'll just be caught in an infinite loop and then you'll segfault 779 00:32:49,620 --> 00:32:50,370 and things go bad. 780 00:32:50,370 --> 00:32:54,780 So always make sure that you're not including the value that you just 781 00:32:54,780 --> 00:32:55,380 looked at. 782 00:32:55,380 --> 00:32:58,530 So we take care of that with a plus 1. 783 00:32:58,530 --> 00:33:04,840 >> So now we have our last condition which I always for safety sake 784 00:33:04,840 --> 00:33:12,664 you can check here, else if value at the middle is greater than the value 785 00:33:12,664 --> 00:33:13,163 we want. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 That means that we want the left hand half. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 So which one are we going to update? 790 00:33:23,260 --> 00:33:23,760 Upper. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 And what is this one going to equal? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Middle minus 1 because, of course, we want 795 00:33:33,690 --> 00:33:38,370 to make sure that we're not looking at that middle value again. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 And then we have it. 798 00:33:45,110 --> 00:33:45,610 That's it. 799 00:33:45,610 --> 00:33:46,820 That's all binary search is. 800 00:33:46,820 --> 00:33:48,190 It's not that bad, right? 801 00:33:48,190 --> 00:33:51,590 It's like 10 lines of code with white space. 802 00:33:51,590 --> 00:33:57,510 So very powerful, very useful, you will be using it in one of your later psets. 803 00:33:57,510 --> 00:33:59,360 Maybe not this one, but later. 804 00:33:59,360 --> 00:34:00,670 So learn it. 805 00:34:00,670 --> 00:34:01,510 Love it. 806 00:34:01,510 --> 00:34:02,980 It will treat you well. 807 00:34:02,980 --> 00:34:05,370 So does anyone have any questions on binary search? 808 00:34:05,370 --> 00:34:06,196 Yes. 809 00:34:06,196 --> 00:34:09,840 >> STUDENT: Does it matter whether your n is even or odd? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUCTOR: No. 811 00:34:10,750 --> 00:34:18,150 Because we cast it to the middle as an int, it will just truncate it. 812 00:34:18,150 --> 00:34:21,600 So it will stay an integer and it will eventually sort through everything. 813 00:34:21,600 --> 00:34:23,909 So you don't have to worry about that. 814 00:34:23,909 --> 00:34:24,580 Everyone good? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Awesome. 817 00:34:26,850 --> 00:34:27,919 Cool. 818 00:34:27,919 --> 00:34:30,836 So, you guys got this. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 So as we were talking about, I know David mentioned complexity runtimes. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> So in the best case, it's just one, which we call constant time. 825 00:34:50,340 --> 00:34:51,909 Can anyone tell me why that might be? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 What type of scenario would that entail? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENT: [INAUDIBLE] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 INSTRUCTOR: So the middle being the first element that we come to, right? 833 00:35:03,830 --> 00:35:08,167 So either an array of one or whatever we're looking for just 834 00:35:08,167 --> 00:35:09,750 happens to be smack dab in the middle. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 So that's our best case. 837 00:35:13,380 --> 00:35:17,540 You get into real problems, probably not going to reach [INAUDIBLE] that often. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 What about our worst case? 840 00:35:19,750 --> 00:35:21,270 Our worst case is log n. 841 00:35:21,270 --> 00:35:25,360 And that has to do with the whole powers of two thing that I talked about. 842 00:35:25,360 --> 00:35:30,930 >> So in the worst case it would mean that we had to chop the array down 843 00:35:30,930 --> 00:35:33,270 until it was an element of one. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 So we had to chop it down in half as many times as we possibly could. 846 00:35:38,930 --> 00:35:41,430 That's why it's log n because you just keep dividing by two. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 So assumptions, things you need to know if you're ever 849 00:35:45,830 --> 00:35:48,050 going to use a binary search. 850 00:35:48,050 --> 00:35:50,680 Your elements must be sorted. 851 00:35:50,680 --> 00:35:53,890 They have to be sorted because that's the only way you 852 00:35:53,890 --> 00:35:57,060 can know if you are able to throw out half of it. 853 00:35:57,060 --> 00:36:00,260 >> If you had this jumbled bag of numbers and you're saying, 854 00:36:00,260 --> 00:36:05,380 OK, I'm going to check the middle number and the number I'm looking for 855 00:36:05,380 --> 00:36:08,510 is less than that, I'm just going to arbitrarily throw out one half. 856 00:36:08,510 --> 00:36:11,130 You wouldn't know if your numbers in that other half. 857 00:36:11,130 --> 00:36:12,655 Your list has to be sorted. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 As well, this may be going ahead a little bit, 860 00:36:16,560 --> 00:36:18,360 but you need to have random access. 861 00:36:18,360 --> 00:36:21,940 You need to be able to just go to that middle element. 862 00:36:21,940 --> 00:36:25,110 If you have to traverse through something 863 00:36:25,110 --> 00:36:28,630 or it takes you extra steps to get to that middle element, 864 00:36:28,630 --> 00:36:31,750 it's not log n anymore because you're adding more work into it. 865 00:36:31,750 --> 00:36:34,800 And this will make a little more sense in two weeks, 866 00:36:34,800 --> 00:36:37,950 but I just kind of wanted to preface, give you guys an idea of what's 867 00:36:37,950 --> 00:36:38,999 to come. 868 00:36:38,999 --> 00:36:40,790 But those are the two important assumptions 869 00:36:40,790 --> 00:36:44,804 that you need for a binary list. 870 00:36:44,804 --> 00:36:45,720 Make sure it's sorted. 871 00:36:45,720 --> 00:36:47,920 That's the big one for you guys right now. 872 00:36:47,920 --> 00:36:52,170 And on that we can go into the rest of our sorts. 873 00:36:52,170 --> 00:36:56,444 So four sorts-- bubble, insertion, selection, and merge. 874 00:36:56,444 --> 00:36:57,485 They're all kind of cool. 875 00:36:57,485 --> 00:37:02,860 If you guys decide to take CS 124, you'll learn about all sorts of sorts. 876 00:37:02,860 --> 00:37:07,575 And if you're an XKCD fan, there is a really cool comic about 877 00:37:07,575 --> 00:37:11,530 like really ineffective sorts, which I highly recommend you going to look at. 878 00:37:11,530 --> 00:37:16,170 One of them is like panic sort, which is like, oh no, return random array. 879 00:37:16,170 --> 00:37:16,991 Shutdown system. 880 00:37:16,991 --> 00:37:17,490 Leave. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 So geeky humor is always good. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> So does anyone remember kind of like just a general idea 885 00:37:25,750 --> 00:37:27,810 of how bubble sort works. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 You remember? 888 00:37:32,155 --> 00:37:32,755 >> STUDENT: Yeah. 889 00:37:32,755 --> 00:37:33,970 >> INSTRUCTOR: Go for it. 890 00:37:33,970 --> 00:37:38,980 >> STUDENT: So you're going through and if it's bigger, then you swap the two. 891 00:37:38,980 --> 00:37:39,820 >> INSTRUCTOR: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Exactly. 893 00:37:40,564 --> 00:37:41,730 So you just iterate through. 894 00:37:41,730 --> 00:37:43,050 You check two numbers. 895 00:37:43,050 --> 00:37:46,510 If the one before is bigger than the one afterwards, 896 00:37:46,510 --> 00:37:50,230 you just swap them so that in this way all of the higher numbers 897 00:37:50,230 --> 00:37:54,990 bubble up towards the end of the list and all the lower numbers bubble down. 898 00:37:54,990 --> 00:37:59,355 >> Did he show you guys the cool sound effect sorting video? 899 00:37:59,355 --> 00:38:00,480 It's kind of cool. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 So as Robert just said, the algorithm that you just step through the list, 902 00:38:05,200 --> 00:38:07,930 swapping the adjacent values if they're not in order. 903 00:38:07,930 --> 00:38:10,975 And then just keep repeating until you don't make any swaps. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 So not bad, right? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 So we just have a quick example here. 908 00:38:16,319 --> 00:38:18,360 So this is going to sort them in ascending order. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 So when we go through the first time, we look through eight 911 00:38:23,470 --> 00:38:26,880 and six are obviously not in order, we swap them. 912 00:38:26,880 --> 00:38:27,985 >> So look at the next one. 913 00:38:27,985 --> 00:38:29,430 Eight and four not in order. 914 00:38:29,430 --> 00:38:30,450 Swap them. 915 00:38:30,450 --> 00:38:32,530 And then eight and two, swap them. 916 00:38:32,530 --> 00:38:33,470 There we go. 917 00:38:33,470 --> 00:38:39,519 So after your first pass, you know that your largest number 918 00:38:39,519 --> 00:38:41,810 is going to be all the way at the top because it's just 919 00:38:41,810 --> 00:38:44,210 going to be constantly larger than everything else 920 00:38:44,210 --> 00:38:46,810 and it's just going to bubble up all the way to the end there. 921 00:38:46,810 --> 00:38:48,226 Does that makes sense to everyone? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Cool. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> So then we look at our second pass. 926 00:38:53,920 --> 00:38:54,980 Six and four, switch. 927 00:38:54,980 --> 00:38:55,920 Six and two, switch. 928 00:38:55,920 --> 00:38:58,700 And now we have a few things in order. 929 00:38:58,700 --> 00:39:02,240 So for every pass that we make through our entire list, 930 00:39:02,240 --> 00:39:06,320 we know that like that many numbers at the end will have been sorted. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 So we do a third pass, which is one swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 And then on our fourth pass, we have zero slots. 935 00:39:15,910 --> 00:39:18,570 And so we know that our array has been sorted. 936 00:39:18,570 --> 00:39:20,900 >> And that is the big thing with bubble sort. 937 00:39:20,900 --> 00:39:23,720 We know that when we have zero swaps, that 938 00:39:23,720 --> 00:39:26,497 means that everything is in complete order. 939 00:39:26,497 --> 00:39:27,580 It's kind of how we check. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 So we are also going to code bubble sort which also is not that bad. 942 00:39:36,480 --> 00:39:38,120 None of these are that bad. 943 00:39:38,120 --> 00:39:40,210 I know they can seem a little scary. 944 00:39:40,210 --> 00:39:42,124 I know when I took the class, even when I 945 00:39:42,124 --> 00:39:44,290 was teaching the class for the first time last year, 946 00:39:44,290 --> 00:39:46,165 I was like, how do I do this? 947 00:39:46,165 --> 00:39:48,540 It makes sense in theory, but how do we actually do this? 948 00:39:48,540 --> 00:39:51,420 Which is why I also want to walk through code with you guys here. 949 00:39:51,420 --> 00:39:54,915 So I have a pseudocode for you guys this time. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 So just keep this in mind as we're about to transition over. 952 00:39:58,970 --> 00:40:04,210 So we have some counter that keeps track of our swaps, 953 00:40:04,210 --> 00:40:08,370 because we need to make sure that we're checking that. 954 00:40:08,370 --> 00:40:11,830 And we iterate the entire array as we just did with this example. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 If the element before is larger than the element after where we're at, 957 00:40:17,325 --> 00:40:20,760 we swap them and we increment our counter because as soon as we swap, 958 00:40:20,760 --> 00:40:23,850 we want to let our counter know that. 959 00:40:23,850 --> 00:40:26,247 Any questions there? 960 00:40:26,247 --> 00:40:27,580 Something seems funny over here. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENT: Do you set the counter to zero every time you go through the loop? 963 00:40:32,350 --> 00:40:34,339 Don't you keep going back to zero every time? 964 00:40:34,339 --> 00:40:35,505 INSTRUCTOR: Not necessarily. 965 00:40:35,505 --> 00:40:39,710 So what happens is we go through here. 966 00:40:39,710 --> 00:40:43,830 So do while, remember, this will execute once without fail. 967 00:40:43,830 --> 00:40:46,480 So it's going to set the counter equal to zero, 968 00:40:46,480 --> 00:40:48,070 then it's going to iterate through. 969 00:40:48,070 --> 00:40:50,590 As it iterates through, it will update counter. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 As it updates counter, when it's done, when it's reached the end of the array, 972 00:40:56,900 --> 00:41:00,830 if our list hasn't been sorted, counter will have been updated. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> So then it checks the condition and it says, OK, is counter greater than zero. 975 00:41:07,150 --> 00:41:09,290 If it is, do it again. 976 00:41:09,290 --> 00:41:14,340 You want to reset so that when you go through, counter is equal to zero. 977 00:41:14,340 --> 00:41:18,240 If you go through a sorted array, nothing changes, 978 00:41:18,240 --> 00:41:21,355 this fails, and you return the sorted list. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Does that makes sense? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENT: It might in a little bit. 983 00:41:26,356 --> 00:41:27,147 INSTRUCTOR: OK. 984 00:41:27,147 --> 00:41:28,980 If there's any other question that comes up. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Yes. 987 00:41:30,680 --> 00:41:33,760 >> STUDENT: What would the function be for swapping the elements? 988 00:41:33,760 --> 00:41:36,900 >> INSTRUCTOR: So we can actually write that if we're going to right now. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Cool. 991 00:41:38,300 --> 00:41:42,155 So on that note, Alison is going to switch back to the appliance. 992 00:41:42,155 --> 00:41:43,080 It's going to be fun. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 And we have our nice bubble sort thing here. 995 00:41:47,390 --> 00:41:50,800 So I already did cycling through the array. 996 00:41:50,800 --> 00:41:53,030 We have our swaps that are equal to zero. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 So we want to swap adjacent elements if they're out of order. 999 00:41:58,440 --> 00:42:03,020 So the first thing we need to do is iterate through our array. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> So how do you think we might iterate through our array? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 We have for and i equals 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 We want i to be less than n minus 1 minus k. 1006 00:42:22,454 --> 00:42:23,870 And I'll explain that in a second. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 So this is an optimization here where, remember how I said after every pass 1009 00:42:32,830 --> 00:42:36,655 through the array we know that whatever's on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> So after one pass we know that this is sorted. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 After two passes we know that all this is sorted. 1014 00:42:50,060 --> 00:42:52,750 After three passes we know that's sorted. 1015 00:42:52,750 --> 00:42:55,620 So the way I'm iterating through the array here, 1016 00:42:55,620 --> 00:43:01,090 is it's making sure to only go through what we know is unsorted. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 That's just an optimization. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 You could write it naively just iterating through everything, 1021 00:43:08,210 --> 00:43:09,970 it would just take longer. 1022 00:43:09,970 --> 00:43:12,470 With this four loop it's just a nice optimization 1023 00:43:12,470 --> 00:43:18,460 because we know that after every full iteration through the array here, 1024 00:43:18,460 --> 00:43:24,050 like every full loop here, we know that one more of these elements 1025 00:43:24,050 --> 00:43:25,760 will be sorted at the end. 1026 00:43:25,760 --> 00:43:28,294 >> So we don't have to worry about those. 1027 00:43:28,294 --> 00:43:29,710 Does that makes sense to everyone? 1028 00:43:29,710 --> 00:43:30,950 That cool little trick? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 So in that case, if we're iterating through, 1031 00:43:37,270 --> 00:43:50,590 we know that we want to check if array n and n plus 1 are in order. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 So here's the pseudocode. 1035 00:43:54,600 --> 00:43:57,540 We want to check if array n and n plus 1 are in order. 1036 00:43:57,540 --> 00:43:59,520 So what might we have there? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 It's going to be some conditional. 1039 00:44:03,120 --> 00:44:04,220 It will be an if. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENT: If array n is less than array n plus 1. 1041 00:44:07,066 --> 00:44:07,816 INSTRUCTOR: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Well, less than or greater than. 1044 00:44:10,699 --> 00:44:11,615 STUDENT: Greater than. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Then we want to swap them. 1047 00:44:17,620 --> 00:44:18,570 Exactly. 1048 00:44:18,570 --> 00:44:23,570 So now we get into what's the mechanism for swapping them? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 So we went through this briefly, a type of swap function last week. 1051 00:44:28,137 --> 00:44:29,595 Does anyone remember how it worked? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 So we can't just reassign them, right? 1054 00:44:34,950 --> 00:44:36,640 Because one of them will get lost. 1055 00:44:36,640 --> 00:44:41,696 If we said A is equal to B and then B is equal to A, all a sudden both of them 1056 00:44:41,696 --> 00:44:43,150 are just equal to B. 1057 00:44:43,150 --> 00:44:45,720 >> So what we have to do is we have a temporary variable that's 1058 00:44:45,720 --> 00:44:49,055 going to hold one of ours while we're in the process of swapping. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 So what we have is we'll have some int temp is equal to-- you can assign it 1061 00:44:56,464 --> 00:44:59,130 to whichever one you want, just make sure you keep track of it-- 1062 00:44:59,130 --> 00:45:01,840 so in this case, I'm going to assign it to array n plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 So that's going to hold whatever value is in that second block 1065 00:45:07,674 --> 00:45:08,590 that we're looking at. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> And then we can do is we can go ahead and reassign array n plus 1, 1068 00:45:13,240 --> 00:45:14,990 because we know we have that value stored. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 This is also one of the big things-- I don't know if any of you 1071 00:45:19,270 --> 00:45:23,780 had issues where if you switch two lines of code suddenly things worked. 1072 00:45:23,780 --> 00:45:25,880 Order is very important in CS. 1073 00:45:25,880 --> 00:45:29,450 So make sure you diagram things out if possible 1074 00:45:29,450 --> 00:45:31,230 as to what's actually happening. 1075 00:45:31,230 --> 00:45:34,256 So now we're going to reassign array n plus 1, 1076 00:45:34,256 --> 00:45:36,005 because we know we have that value stored. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> And we can assign that to array n or in this case array i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Too many variables. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 So now we've reassigned array i plus 1 to equal what's in array i. 1084 00:46:01,500 --> 00:46:08,240 And now we can go back and assign array i to what? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Anyone? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> STUDENT: 10. 1089 00:46:14,010 --> 00:46:14,680 >> INSTRUCTOR: 10. 1090 00:46:14,680 --> 00:46:15,180 Exactly. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 And one last thing. 1093 00:46:18,640 --> 00:46:21,840 If we have swapped it now, what do we need to do? 1094 00:46:21,840 --> 00:46:23,740 What's the one thing that's going to tell us 1095 00:46:23,740 --> 00:46:27,542 if we ever terminate this program? 1096 00:46:27,542 --> 00:46:29,250 What tells us that we have a sorted list? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 If we don't perform any swaps, right? 1099 00:46:33,750 --> 00:46:36,900 If swaps is equal to zero at the end of this. 1100 00:46:36,900 --> 00:46:42,975 So whenever you perform a swap, as we just did here, we want to update swaps. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 And I know there was a question earlier about can you 1103 00:46:47,210 --> 00:46:49,689 use zero or one instead of true or false. 1104 00:46:49,689 --> 00:46:50,980 And that's what this does here. 1105 00:46:50,980 --> 00:46:52,750 So this says if not swaps. 1106 00:46:52,750 --> 00:47:01,310 So if swaps is zero, which is-- I always get my truths and my falses mixed up. 1107 00:47:01,310 --> 00:47:03,960 We want us to evaluate to true and it's not. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 So if it's zero, then it's false. 1110 00:47:09,630 --> 00:47:12,560 If you negate it with a [? bang ?] it becomes true. 1111 00:47:12,560 --> 00:47:13,975 So then this line executes. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Truths and false and zeros and ones get crazy. 1114 00:47:17,370 --> 00:47:20,690 Just if you slowly walk through it it will make sense. 1115 00:47:20,690 --> 00:47:23,320 But that's what this little bit of code here does. 1116 00:47:23,320 --> 00:47:26,490 So this checks to see have we done any swaps. 1117 00:47:26,490 --> 00:47:30,054 So if it's anything besides zero, it's going to be false 1118 00:47:30,054 --> 00:47:31,970 and the whole thing is going to execute again. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Cool? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> STUDENT: What does break do? 1123 00:47:36,000 --> 00:47:38,990 >> INSTRUCTOR: Break just breaks you out of the loop. 1124 00:47:38,990 --> 00:47:41,570 So in this case it would just like end the program 1125 00:47:41,570 --> 00:47:43,828 and you would just have your sorted list. 1126 00:47:43,828 --> 00:47:44,536 STUDENT: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 INSTRUCTOR: I'm sorry? 1129 00:47:49,010 --> 00:47:52,110 STUDENT: Because previously we used written 1 over written zero 1130 00:47:52,110 --> 00:47:54,170 to present that if that will work or not. 1131 00:47:54,170 --> 00:47:54,878 >> INSTRUCTOR: Yeah. 1132 00:47:54,878 --> 00:47:56,410 So you can return zero or 1. 1133 00:47:56,410 --> 00:47:58,950 In this case, because we're not actually doing anything with the function, 1134 00:47:58,950 --> 00:48:00,150 we just want it to break. 1135 00:48:00,150 --> 00:48:02,680 We don't really care about it. 1136 00:48:02,680 --> 00:48:06,960 Brake is also good if it's used for breaking out 1137 00:48:06,960 --> 00:48:10,710 of four loops or conditions that you don't want to keep executing. 1138 00:48:10,710 --> 00:48:12,110 It just takes you out of them. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 It's a bit of a nuance thing. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 I feel like there's a lot of hand waving, 1143 00:48:18,445 --> 00:48:19,740 like you'll learn about this soon. 1144 00:48:19,740 --> 00:48:20,955 >> But you'll learn about this soon. 1145 00:48:20,955 --> 00:48:21,500 I promise. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 So does everyone get bubble sort? 1149 00:48:24,840 --> 00:48:25,550 Not too bad. 1150 00:48:25,550 --> 00:48:31,910 Iterate through, swap things using a temp variable, and we're all set there? 1151 00:48:31,910 --> 00:48:32,960 Cool. 1152 00:48:32,960 --> 00:48:34,080 Awesome. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Back to the PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Any questions in general about these so far? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Cool. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENT: [INAUDIBLE] int main usually. 1162 00:48:45,279 --> 00:48:46,695 Do you have to have that for this? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> INSTRUCTOR: So we were just looking just at the actual sorting algorithm. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 If you had it within like a larger program, 1167 00:48:56,350 --> 00:48:57,891 you would have an int main somewhere. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Depending on where you use this algorithm, 1170 00:49:02,880 --> 00:49:05,860 it would determine what's being returned by it. 1171 00:49:05,860 --> 00:49:09,960 But for our case, we're strictly looking at how does this actually 1172 00:49:09,960 --> 00:49:11,300 iterate through an array. 1173 00:49:11,300 --> 00:49:12,570 So we don't worry about it. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> So we were talking about best case and worst case scenarios for binary search. 1176 00:49:19,830 --> 00:49:22,470 So it's also important to do that for each of our sorts. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 So what do you think is the worst case runtime of bubble sort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 You guys remember? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENT: N minus 1. 1182 00:49:31,784 --> 00:49:32,700 INSTRUCTOR: N minus 1. 1183 00:49:32,700 --> 00:49:35,070 So that means there are n minus 1 comparisons. 1184 00:49:35,070 --> 00:49:40,060 So one thing to realize is that on the first iteration, 1185 00:49:40,060 --> 00:49:43,360 we go through, we compare these two-- so that's 1. 1186 00:49:43,360 --> 00:49:46,685 These two, three, four. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 So after one iteration we already have four comparisons. 1189 00:49:55,050 --> 00:49:58,230 When I'm talking about runtime and n. 1190 00:49:58,230 --> 00:50:04,680 N represents the number of comparisons as a function of how many elements 1191 00:50:04,680 --> 00:50:05,570 we have. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> So we go through, we have four. 1194 00:50:08,860 --> 00:50:11,780 The next time you know we don't have to take care of this. 1195 00:50:11,780 --> 00:50:15,140 We compare these two, these two, these two, 1196 00:50:15,140 --> 00:50:20,050 and if we didn't have that optimization with the four loop that I wrote, 1197 00:50:20,050 --> 00:50:22,750 you would be comparing in here anyways. 1198 00:50:22,750 --> 00:50:26,170 So you would have to run through the array 1199 00:50:26,170 --> 00:50:34,380 and make n comparisons n times, because every time we 1200 00:50:34,380 --> 00:50:36,670 run through it we sort one thing. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> And every time we run through the array, we make n comparisons. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 So our runtime for this is actually n squared, which 1205 00:50:46,330 --> 00:50:48,400 is much worse in our log end because that 1206 00:50:48,400 --> 00:50:51,965 means if we had four billion elements, it's 1207 00:50:51,965 --> 00:50:55,260 going to take us four billion squared instead of 32. 1208 00:50:55,260 --> 00:51:01,240 So not the best runtime, but for some things, 1209 00:51:01,240 --> 00:51:04,610 you know, if you're within a certain range of elements 1210 00:51:04,610 --> 00:51:06,540 bubble sort may be fine to use. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 So now what is the best case runtime? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 STUDENT: Zero? 1215 00:51:14,940 --> 00:51:16,420 Or 1? 1216 00:51:16,420 --> 00:51:18,140 >> INSTRUCTOR: So 1 would be one comparison. 1217 00:51:18,140 --> 00:51:19,114 Right. 1218 00:51:19,114 --> 00:51:20,002 >> STUDENT: N minus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> INSTRUCTOR: So, yeah. 1221 00:51:22,320 --> 00:51:22,990 So n minus 1. 1222 00:51:22,990 --> 00:51:26,510 Whenever you have a concept like n minus 1, we tend to just drop it off 1223 00:51:26,510 --> 00:51:31,680 and we just say n because you have to compare each of these-- each pair. 1224 00:51:31,680 --> 00:51:36,470 So it would be n minus 1, which we we'd just say is approximately n. 1225 00:51:36,470 --> 00:51:39,280 When you're dealing with runtime, everything is in approximates. 1226 00:51:39,280 --> 00:51:43,860 As long as the exponent is correct, you're pretty good. 1227 00:51:43,860 --> 00:51:45,700 >> That's how we deal with it. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 So that the best case is n, which means that the list is already sorted, 1230 00:51:51,780 --> 00:51:54,320 and all we do is run through and check that it's sorted. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Cool. 1233 00:51:56,855 --> 00:51:57,355 All right. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 So as you see here, we just have some more graphs. 1236 00:52:01,920 --> 00:52:02,660 So n squared. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Much worse than n as we see, and much, much worse than log 2n. 1240 00:52:09,730 --> 00:52:12,060 And then you also get into log logs. 1241 00:52:12,060 --> 00:52:18,020 And you take 124, you get into like log star, which is like crazy. 1242 00:52:18,020 --> 00:52:20,172 So if you're interested, lookup log star. 1243 00:52:20,172 --> 00:52:20,880 It's kind of fun. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 So we have this great chart. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Just a heads up, this a wonderful chart to have 1248 00:52:28,720 --> 00:52:31,350 for your mid-term because we long to ask you these thins. 1249 00:52:31,350 --> 00:52:36,090 So just a heads up, have this on your mid-term on your nice cheat sheet 1250 00:52:36,090 --> 00:52:36,616 there. 1251 00:52:36,616 --> 00:52:37,990 So we just looked at bubble sort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Worst case, n squared, best case, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 And we're going to look at the others. 1256 00:52:44,950 --> 00:52:47,940 >> And as you can see, the only one that really does well 1257 00:52:47,940 --> 00:52:50,910 is merge sort, which we'll get into why. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 So we're going to go to the next one here-- selection sort. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Does anyone remember how selection sort worked? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Go for it. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENT: Basically go through an order and create a new list. 1265 00:53:08,210 --> 00:53:11,001 And just as you're putting elements in, put them in the right place 1266 00:53:11,001 --> 00:53:11,750 in the new list. 1267 00:53:11,750 --> 00:53:14,040 >> INSTRUCTOR: So that sounds more like insertion sort. 1268 00:53:14,040 --> 00:53:15,040 But you're really close. 1269 00:53:15,040 --> 00:53:15,915 They're very similar. 1270 00:53:15,915 --> 00:53:17,440 Even I get them mixed up sometimes. 1271 00:53:17,440 --> 00:53:18,981 Before this section I was like, wait. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 So what you want to do is selection sort, 1275 00:53:24,141 --> 00:53:25,890 the way you can think about it and the way 1276 00:53:25,890 --> 00:53:30,140 I make sure I try not to get them mixed up, is it goes through 1277 00:53:30,140 --> 00:53:33,280 and it selects the smallest number and it 1278 00:53:33,280 --> 00:53:36,070 puts that at the beginning of your list. 1279 00:53:36,070 --> 00:53:37,730 It swaps it with that first spot. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 They actually have an example for me. 1282 00:53:45,370 --> 00:53:46,540 Awesome. 1283 00:53:46,540 --> 00:53:50,130 So just a way to think of it-- selection sort, select the smallest value. 1284 00:53:50,130 --> 00:53:51,940 And we're going to run through an example 1285 00:53:51,940 --> 00:53:55,320 that I think will help because I think visuals always help. 1286 00:53:55,320 --> 00:53:58,510 So we start out with something that is completely unsorted. 1287 00:53:58,510 --> 00:54:00,730 Red will be unsorted, green will be sorted. 1288 00:54:00,730 --> 00:54:02,190 It will all make sense in a second. 1289 00:54:02,190 --> 00:54:08,950 >> So we go through and we iterate from the beginning to the end. 1290 00:54:08,950 --> 00:54:12,320 And we say, OK, 2 is our smallest number. 1291 00:54:12,320 --> 00:54:15,680 So we're going to take 2 and we're going to move it to the front of our array 1292 00:54:15,680 --> 00:54:17,734 because it's the smallest number we have. 1293 00:54:17,734 --> 00:54:19,150 So that's what this is doing here. 1294 00:54:19,150 --> 00:54:20,820 It's just going to swap those two. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 So now we have a sorted part and an unsorted part. 1297 00:54:25,450 --> 00:54:27,810 And what's good to remember about selection sort 1298 00:54:27,810 --> 00:54:30,690 is we're only selecting from the unsorted part. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> The sorted part you just leave alone. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENT: How does it know what is the smallest without comparing it 1303 00:54:38,452 --> 00:54:39,868 to every other value in the array. 1304 00:54:39,868 --> 00:54:41,250 INSTRUCTOR: It does compare it. 1305 00:54:41,250 --> 00:54:42,041 We like skipped it. 1306 00:54:42,041 --> 00:54:43,850 This is just general overall. 1307 00:54:43,850 --> 00:54:44,831 Yeah. 1308 00:54:44,831 --> 00:54:47,205 When we write the code I'm sure you'll be more satisfied. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 But you store this first element as the smallest. 1311 00:54:53,030 --> 00:54:56,110 You compare and you say, OK, is it smaller? 1312 00:54:56,110 --> 00:54:56,660 Yes. 1313 00:54:56,660 --> 00:54:57,460 Keep it. 1314 00:54:57,460 --> 00:54:58,640 Here is it smaller? 1315 00:54:58,640 --> 00:54:59,660 No? 1316 00:54:59,660 --> 00:55:02,510 >> This is your smallest, reassign it to your value. 1317 00:55:02,510 --> 00:55:06,340 And you'll be much happier when we go through the code. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 So we go through, we swap it, so then we look at this unsorted portion. 1320 00:55:13,970 --> 00:55:15,810 So we're going to select three out. 1321 00:55:15,810 --> 00:55:18,890 We're going to put it on at the end of our sorted portion. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 And we're just going to keep doing that, doing that, and doing that. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 So this is our kind of pseudocode here. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 We'll code it up here in a second. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 But just something to walk through on a high level. 1330 00:55:37,270 --> 00:55:40,275 You're going to go from i equals 0 to n minus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 That's another optimization. 1333 00:55:43,530 --> 00:55:45,020 Don't worry too much about it. 1334 00:55:45,020 --> 00:55:46,620 So as you were saying. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 As Jacob was saying, how do we keep track of what our minimum is? 1337 00:55:54,406 --> 00:55:55,030 How do we know? 1338 00:55:55,030 --> 00:55:57,060 We have to compare everything in our list. 1339 00:55:57,060 --> 00:55:59,600 >> So minimum equals i. 1340 00:55:59,600 --> 00:56:03,870 It's just saying in this case the index of our minimum value. 1341 00:56:03,870 --> 00:56:07,660 So then it's going to iterate through and it goes from j equals i plus 1. 1342 00:56:07,660 --> 00:56:11,420 So we already know that that's our first element. 1343 00:56:11,420 --> 00:56:13,240 We don't need to compare it to itself. 1344 00:56:13,240 --> 00:56:16,970 So we start comparing it to the next one which is why it's i plus 1 to n 1345 00:56:16,970 --> 00:56:20,110 minus 1, which is the end of the array there. 1346 00:56:20,110 --> 00:56:25,090 And we said if array at j is less than array min, 1347 00:56:25,090 --> 00:56:29,200 then we reassign where our minimum indices is. 1348 00:56:29,200 --> 00:56:37,470 >> And if min is not equal to i, as in where we were back over here. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 So like when we first did this one. 1351 00:56:41,790 --> 00:56:49,310 In this case, it would start at zero, it would end up being two. 1352 00:56:49,310 --> 00:56:53,010 So min would not equal i in the end. 1353 00:56:53,010 --> 00:56:55,720 That lets us know that we need to swap them. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 I feel like a concrete example will help much more than this. 1356 00:57:00,470 --> 00:57:04,970 So I'll code this up with you guys right now and I think it'll be better. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Sorts tend to work that way in that it's often better just to see them. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 So what we want to do is we first want the smallest 1361 00:57:17,280 --> 00:57:19,890 element in its position in the array. 1362 00:57:19,890 --> 00:57:21,280 Exactly what Jacob was saying. 1363 00:57:21,280 --> 00:57:23,090 You need to store that somehow. 1364 00:57:23,090 --> 00:57:25,900 So we're going to start here iterating over the array. 1365 00:57:25,900 --> 00:57:28,970 We're going to say it's our first one just to start with. 1366 00:57:28,970 --> 00:57:38,308 So we are going to have int smallest is equal to array at i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> So one thing to notice, every time this loop executes, 1369 00:57:45,050 --> 00:57:48,550 we are starting one step further along. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 When we start we look at this one. 1372 00:57:57,440 --> 00:58:00,840 The next time we iterate through, we're starting at this one 1373 00:58:00,840 --> 00:58:02,680 and assigning it our smallest value. 1374 00:58:02,680 --> 00:58:10,450 So it's very similar to bubble sort where we know that after one pass, 1375 00:58:10,450 --> 00:58:11,700 this last element is sorted. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 With selection sort, it's just the opposite. 1378 00:58:15,120 --> 00:58:18,950 >> At every pass, we know that the first one is sorted. 1379 00:58:18,950 --> 00:58:21,360 After the second pass, the second one will be sorted. 1380 00:58:21,360 --> 00:58:26,470 And as you saw with the slide examples, our sorted portion just keeps growing. 1381 00:58:26,470 --> 00:58:34,020 So by setting our smallest one to arrays i, all it's doing 1382 00:58:34,020 --> 00:58:37,340 is constricting what we're looking at so as 1383 00:58:37,340 --> 00:58:40,164 to minimize the number of comparisons we make. 1384 00:58:40,164 --> 00:58:41,770 Does that make sense to everyone? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Do you need me to run through that again slower or in different words? 1387 00:58:46,380 --> 00:58:47,180 I'm happy to. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> So we're storing the value at this point, 1392 00:58:55,540 --> 00:58:57,840 but we also want to store the index. 1393 00:58:57,840 --> 00:59:01,010 So we're going to store the position of the smallest 1394 00:59:01,010 --> 00:59:02,770 one, which is just going to be i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 So now Jacob is satisfied. 1397 00:59:05,440 --> 00:59:06,870 We have things stored. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 And now we need to look through the unsorted part of the array. 1400 00:59:11,870 --> 00:59:18,170 So in this case this would be our unsorted. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 This is i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> So what we're going to do is going to be for a loop. 1406 00:59:30,040 --> 00:59:32,066 Whenever you need to iterate through an array, 1407 00:59:32,066 --> 00:59:33,440 your mind could go to for a loop. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 So for some int k equals-- what do we think 1410 00:59:38,090 --> 00:59:39,700 k is going to equal to start with? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 This is what we set as our smallest value and we want to compare it. 1413 00:59:44,766 --> 00:59:47,090 What do we want to compare it to? 1414 00:59:47,090 --> 00:59:48,730 It's going to be this next one, right? 1415 00:59:48,730 --> 00:59:53,200 So we want k to be initialized to i plus 1 to start. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> And we want k in this case we already have size stored up here, 1418 01:00:02,800 --> 01:00:03,930 so we can just use size. 1419 01:00:03,930 --> 01:00:06,240 Size being the size of the array. 1420 01:00:06,240 --> 01:00:09,620 And we just want to update k by one each time. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Cool. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 So now we need to find the smallest element here. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 So if we iterate through, we want to say, if array at k 1427 01:00:31,380 --> 01:00:37,080 is less than our smallest value-- this is where we're actually 1428 01:00:37,080 --> 01:00:42,950 keeping track of what's the smallest here-- 1429 01:00:42,950 --> 01:00:47,740 then we want to reassign what our smallest value is. 1430 01:00:47,740 --> 01:00:50,645 >> This means that, oh, we're iterating through here. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Whatever value is here is not our smallest thing. 1433 01:00:53,740 --> 01:00:54,448 We don't want it. 1434 01:00:54,448 --> 01:00:56,100 We want to reassign it. 1435 01:00:56,100 --> 01:01:02,050 So if we're reassigning it, what do you think might be in this code here? 1436 01:01:02,050 --> 01:01:04,160 We want to reassign smallest and position. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 So what is smallest now? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 STUDENT: Array k. 1441 01:01:09,130 --> 01:01:09,963 INSTRUCTOR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 And what is position now? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 What's the indices of our smallest value? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 It's just k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 So array k, k, they match up. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 So we wanted to reassign that. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 And then after we found our smallest, so at the end of this for loop 1454 01:01:39,950 --> 01:01:45,100 here we have found what our smallest value is, so we just swap it. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 In this case, like say our smallest value is out here. 1457 01:01:50,816 --> 01:01:51,940 This is our smallest value. 1458 01:01:51,940 --> 01:01:57,690 >> We just want to swap it here, which is what that swap function at the bottom 1459 01:01:57,690 --> 01:02:01,270 did, which we just wrote up together a couple minutes ago. 1460 01:02:01,270 --> 01:02:02,775 So it should look familiar. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 And then it will just iterate through until it reaches all the way 1463 01:02:08,030 --> 01:02:13,100 to the end, which means that you have zero elements that are unsorted 1464 01:02:13,100 --> 01:02:14,800 and everything else has been sorted. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Make sense? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 A little more concretely? 1469 01:02:19,280 --> 01:02:19,990 The code help? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENT: For a size, you never really define it or change it, 1472 01:02:26,410 --> 01:02:27,340 how does it know? 1473 01:02:27,340 --> 01:02:32,380 >> INSTRUCTOR: So one thing to notice up here is int size. 1474 01:02:32,380 --> 01:02:35,680 So we're saying in this sort-- sort is a function in this case-- it's 1475 01:02:35,680 --> 01:02:40,770 selection sort, it's passed in with the function. 1476 01:02:40,770 --> 01:02:43,460 So if it wasn't passed in, you would do something 1477 01:02:43,460 --> 01:02:47,840 like with the length of the array or you would iterate through 1478 01:02:47,840 --> 01:02:49,390 to find the length. 1479 01:02:49,390 --> 01:02:52,680 But because it's passed in, we can just use it. 1480 01:02:52,680 --> 01:02:55,720 You just assume that the user gave you a valid size that 1481 01:02:55,720 --> 01:02:57,698 actually represents a size of your array. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Cool? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> If you guys have any trouble with these or want more practice coding sorts 1486 01:03:05,870 --> 01:03:08,050 on your own, you should go to study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 It's a tool. 1489 01:03:12,670 --> 01:03:15,040 They have a checker that you can actually write. 1490 01:03:15,040 --> 01:03:16,180 They do pseudocode. 1491 01:03:16,180 --> 01:03:19,310 They have more videos and slides including the ones I use here. 1492 01:03:19,310 --> 01:03:23,150 So if you're still feeling a little fuzzy, try that out. 1493 01:03:23,150 --> 01:03:25,670 As always, come talk to me, too. 1494 01:03:25,670 --> 01:03:26,320 Question? 1495 01:03:26,320 --> 01:03:28,611 >> STUDENT: Are you saying the size is previously defined? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 INSTRUCTOR: Yes. 1498 01:03:29,900 --> 01:03:35,570 Size is previously defined up here in the function declaration. 1499 01:03:35,570 --> 01:03:39,060 So you assume that it's been passed in by the user, and for simplicity's sake, 1500 01:03:39,060 --> 01:03:41,896 we're going to assume that the user gave us the correct size. 1501 01:03:41,896 --> 01:03:43,240 Cool. 1502 01:03:43,240 --> 01:03:44,390 So that's selection sort. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Guys, I know we're learning a lot today. 1505 01:03:47,640 --> 01:03:49,710 It's a dense data for section. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 So with that, we are going to go to insertion sort. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 So before that we have to do our runtime analysis here. 1511 01:04:06,100 --> 01:04:10,190 So in the best case, granted since I showed you 1512 01:04:10,190 --> 01:04:11,960 the table I already kind of gave it away. 1513 01:04:11,960 --> 01:04:15,430 But best case runtime, what do we think? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Everything sorted. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N squared. 1518 01:04:22,070 --> 01:04:24,780 Anyone have an explanation for why you think? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENT: You're comparing through-- 1521 01:04:30,519 --> 01:04:31,268 INSTRUCTOR: Right. 1522 01:04:31,268 --> 01:04:32,540 You're comparing through. 1523 01:04:32,540 --> 01:04:35,630 At every iteration, even though we're decrementing this by one, 1524 01:04:35,630 --> 01:04:38,950 you're still searching through everything to find the smallest one. 1525 01:04:38,950 --> 01:04:42,390 So even if your smallest value is here at the beginning, 1526 01:04:42,390 --> 01:04:44,710 you're still comparing it against everything else 1527 01:04:44,710 --> 01:04:46,550 to make sure it's the smallest thing. 1528 01:04:46,550 --> 01:04:49,820 So you'll end up running through approximately n squared times. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 All right. 1531 01:04:51,590 --> 01:04:52,785 And what's the worst case? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Also n squared because you're going to be doing that same procedure. 1534 01:04:57,980 --> 01:05:01,670 So in this case, selection sort has something 1535 01:05:01,670 --> 01:05:04,010 that we also call expected runtime. 1536 01:05:04,010 --> 01:05:07,400 So in the others, we just know the upper and lower bounds. 1537 01:05:07,400 --> 01:05:11,180 Depending on how crazy our list is or how unsorted it is, 1538 01:05:11,180 --> 01:05:15,350 they vary between n or n squared. 1539 01:05:15,350 --> 01:05:16,550 We don't know. 1540 01:05:16,550 --> 01:05:22,820 >> But because selection sort has the same worst and best case, that tells us that 1541 01:05:22,820 --> 01:05:25,880 no matter what type of input we have, whether it's completely 1542 01:05:25,880 --> 01:05:29,130 sorted or completely reverse sorted, it's 1543 01:05:29,130 --> 01:05:30,740 going to take the same amount of time. 1544 01:05:30,740 --> 01:05:33,760 So in that case, if you remember from our table, 1545 01:05:33,760 --> 01:05:38,610 it actually had a value that these two sorts don't have, 1546 01:05:38,610 --> 01:05:40,390 which is expected runtime. 1547 01:05:40,390 --> 01:05:43,350 So we know that whenever we run selection sort, 1548 01:05:43,350 --> 01:05:45,380 it's guaranteed to run an n squared time. 1549 01:05:45,380 --> 01:05:46,630 There is no variability there. 1550 01:05:46,630 --> 01:05:47,630 It's just expected. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 And, again, if you want to learn more, take CS 124 in the Spring. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 All right. 1555 01:05:56,712 --> 01:05:57,545 We've seen this one. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Cool. 1558 01:05:59,030 --> 01:06:00,930 So insertion sort. 1559 01:06:00,930 --> 01:06:03,330 And I'm probably going to blaze through this. 1560 01:06:03,330 --> 01:06:05,440 I won't have you guys code it. 1561 01:06:05,440 --> 01:06:06,580 We'll just walk through it. 1562 01:06:06,580 --> 01:06:10,500 So insertion sort is kind of similar to selection sort 1563 01:06:10,500 --> 01:06:14,460 in that we have both an unsorted and sorted part of the array. 1564 01:06:14,460 --> 01:06:20,260 >> But what's different is that as we go through one by one, 1565 01:06:20,260 --> 01:06:24,210 we just take whatever number is next in our unsorted, 1566 01:06:24,210 --> 01:06:28,507 and correctly sort it into our sorted array. 1567 01:06:28,507 --> 01:06:30,090 It'll make more sense with an example. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 So everything starts as unsorted, just like with selection sort. 1570 01:06:35,430 --> 01:06:38,740 And we're going to sort this in ascending order as we have been. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 So on our first pass we take the first value 1573 01:06:43,340 --> 01:06:46,700 and we say, OK, you are now in a list by yourself. 1574 01:06:46,700 --> 01:06:49,150 >> Because you are in a list by yourself, you are sorted. 1575 01:06:49,150 --> 01:06:52,460 Congratulations for being the first element in this array. 1576 01:06:52,460 --> 01:06:54,800 You're already sorted all on your own. 1577 01:06:54,800 --> 01:06:58,900 So now we have a sorted and an unsorted array. 1578 01:06:58,900 --> 01:07:01,760 So now we take the first. 1579 01:07:01,760 --> 01:07:05,600 What happens between here and here is that we say, 1580 01:07:05,600 --> 01:07:08,890 OK, we're going to look at the first value of our unsorted array 1581 01:07:08,890 --> 01:07:13,270 and we're going to input it in its correct place in the sorted array. 1582 01:07:13,270 --> 01:07:21,460 >> So what we do is we take 5 and we say, OK, 5 is greater than 3, 1583 01:07:21,460 --> 01:07:24,630 so we just insert it right to the right of that. 1584 01:07:24,630 --> 01:07:25,130 We're good. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 So then we go on to our next one. 1587 01:07:28,420 --> 01:07:29,720 And we take 2. 1588 01:07:29,720 --> 01:07:34,330 We say, OK, 2 is less than 3, so we know that it 1589 01:07:34,330 --> 01:07:36,220 needs to be at the front of our list now. 1590 01:07:36,220 --> 01:07:41,800 So what we do is we push 3 and 5 down and we move 2 into that first slot. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 So we're just inserting it into the correct place it should be. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Then we look at our next one, and we say 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 is greater than everything in our sorted array, 1596 01:07:53,620 --> 01:07:56,000 so we just tag it on to the end. 1597 01:07:56,000 --> 01:07:56,960 And then we look at 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 is less than 6, it's less than 5 but it's greater than 3. 1600 01:08:03,020 --> 01:08:06,270 So we just insert it right into the middle between 3 and 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 So to make that a little bit more concrete, 1603 01:08:10,530 --> 01:08:12,280 here is kind of the idea of what happened. 1604 01:08:12,280 --> 01:08:16,430 So for each unsorted element, we determine where in the sorted portion 1605 01:08:16,430 --> 01:08:17,090 it is. 1606 01:08:17,090 --> 01:08:20,680 >> So keeping in mind the sorted and unsorted, 1607 01:08:20,680 --> 01:08:26,080 we have to traverse through and figure out where it fits in the sorted array. 1608 01:08:26,080 --> 01:08:31,460 And we insert it by shifting the elements to the right of it down. 1609 01:08:31,460 --> 01:08:34,910 And then we just keep iterating through until we 1610 01:08:34,910 --> 01:08:39,270 have a completely sorted list where unsorted is now zero 1611 01:08:39,270 --> 01:08:41,720 and sorted takes up the entirety of our list. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 So, again, to make things even more concrete, we have pseudocode. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> So basically for i is equal to 0 to n minus 1, 1616 01:08:52,410 --> 01:08:54,790 that's just the length of our array. 1617 01:08:54,790 --> 01:09:00,979 We have some element that is equal to the first array or the first indices. 1618 01:09:00,979 --> 01:09:03,200 We set j equal to that. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 So while j is greater than zero and the array, j minus 1 1621 01:09:09,210 --> 01:09:11,660 is greater than the element, so all that's doing 1622 01:09:11,660 --> 01:09:17,479 is making sure that your j really represents 1623 01:09:17,479 --> 01:09:20,010 the unsorted portion of the array. 1624 01:09:20,010 --> 01:09:30,745 >> So while there is still things to sort and j minus one is-- what 1625 01:09:30,745 --> 01:09:31,840 is the element her? 1626 01:09:31,840 --> 01:09:34,760 J was never defined here. 1627 01:09:34,760 --> 01:09:35,677 It's kind of annoying. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Anyways. 1630 01:09:36,689 --> 01:09:39,899 So j minus 1, you're checking the element before it. 1631 01:09:39,899 --> 01:09:46,460 You're saying, OK, is the element before wherever I am-- let's 1632 01:09:46,460 --> 01:09:47,540 actually draw this out. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 So let's say this is like on our second pass. 1635 01:09:56,830 --> 01:09:59,525 So i is going to be equal to 1, which is here. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> So i is going to be equal to 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 This would be 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 All right. 1642 01:10:16,750 --> 01:10:20,945 So our element in this case is going to be equal to 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 And we have some j that's going to be equal to 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j is decrementing. 1647 01:10:30,971 --> 01:10:31,720 That's what it is. 1648 01:10:31,720 --> 01:10:35,680 So j is equal to i, so what this is saying is that as we move forward, 1649 01:10:35,680 --> 01:10:37,530 we're just making sure that we're not over 1650 01:10:37,530 --> 01:10:43,520 indexing this way when we're trying to insert things into our sorted list. 1651 01:10:43,520 --> 01:10:49,850 >> So when j is equal to 1 in this case and array j minus one-- so array j minus 1 1652 01:10:49,850 --> 01:10:54,610 is 2 in this case-- if that's greater than the element, 1653 01:10:54,610 --> 01:10:57,700 then all this is doing is shifting things down. 1654 01:10:57,700 --> 01:11:04,790 So in this case, array j minus one would be array zero, which is 2. 1655 01:11:04,790 --> 01:11:08,430 2 is not greater than 4, so this doesn't execute. 1656 01:11:08,430 --> 01:11:11,460 So the shift doesn't move down. 1657 01:11:11,460 --> 01:11:18,790 What this does here is just moving your sorted array down. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 In this case, actually, we could do-- let's make this 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 So if we're to walk through with this example, we're now here. 1662 01:11:31,970 --> 01:11:32,740 This is sorted. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 This is unsorted. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Cool? 1667 01:11:39,860 --> 01:11:46,620 So i is equal to 2, so our element is equal to 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 And our j is equal to 2. 1670 01:11:52,270 --> 01:12:00,620 So we look through and we say, OK, is array j minus one 1671 01:12:00,620 --> 01:12:03,470 greater than the element that we're looking at? 1672 01:12:03,470 --> 01:12:05,540 And the answer is yes, right? 1673 01:12:05,540 --> 01:12:11,275 4 is greater than 3 and j is 2, so this code executes. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> So now what we do an array at 2, so right here, we swap them. 1676 01:12:18,550 --> 01:12:25,620 So we just say, OK, array at 2 is now going to be 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 And j is going to equal j minus 1, which is 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 That's horrible, but you guys get the idea. 1681 01:12:37,200 --> 01:12:38,360 J is now equal to 1. 1682 01:12:38,360 --> 01:12:44,360 And array j is just going to be equal to our element, which was 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 I erased something I shouldn't have or miswrote something, 1685 01:12:48,570 --> 01:12:49,910 but you guys get the idea. 1686 01:12:49,910 --> 01:12:50,640 >> It move at n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 And then if this were, it would loop again and it would say, OK, j is 1 now. 1689 01:12:57,960 --> 01:13:00,665 And array j minus 1 is now 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Is 2 less than our element? 1692 01:13:03,760 --> 01:13:04,540 No? 1693 01:13:04,540 --> 01:13:07,970 That means that we've inserted this element 1694 01:13:07,970 --> 01:13:10,110 in the correct spot in our sorted array. 1695 01:13:10,110 --> 01:13:14,400 Then we can take this and we say, OK, our sorted array is here. 1696 01:13:14,400 --> 01:13:19,940 And it would take this number 6 and be like, OK, is 6 less than this number? 1697 01:13:19,940 --> 01:13:20,480 No? 1698 01:13:20,480 --> 01:13:21,080 Cool. 1699 01:13:21,080 --> 01:13:22,680 We're fine. 1700 01:13:22,680 --> 01:13:23,530 >> Do it again. 1701 01:13:23,530 --> 01:13:24,740 We say 7. 1702 01:13:24,740 --> 01:13:29,010 Is 7 less than the end of our sorted array? 1703 01:13:29,010 --> 01:13:29,520 No. 1704 01:13:29,520 --> 01:13:30,430 So we're fine. 1705 01:13:30,430 --> 01:13:32,760 So this would be sorted. 1706 01:13:32,760 --> 01:13:38,610 Basically all this does is it's saying take 1707 01:13:38,610 --> 01:13:42,060 the first element of your unsorted array, 1708 01:13:42,060 --> 01:13:46,010 figure out where it goes in your sorted array. 1709 01:13:46,010 --> 01:13:48,780 And this just takes care of swaps to do that. 1710 01:13:48,780 --> 01:13:51,300 You're basically just swapping until it's in the right spot. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 The visual image is that you're moving everything down by doing that. 1713 01:13:56,990 --> 01:13:59,420 >> So it's like half bubble sort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Check out study 50. 1716 01:14:03,420 --> 01:14:06,000 I highly recommend trying to code this on your own. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 If you have any issues or you want to see sample code for an insertion sort, 1719 01:14:12,450 --> 01:14:13,750 please let me know. 1720 01:14:13,750 --> 01:14:14,500 I'm always around. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 So worst case runtime and best case runtime. 1723 01:14:20,200 --> 01:14:30,700 As you guy saw from the table I already showed you, it's both n squared and n. 1724 01:14:30,700 --> 01:14:35,590 >> So kind of going off of what we talked about with our previous sorts, worst 1725 01:14:35,590 --> 01:14:38,760 case runtime is that if it's completely unsorted, 1726 01:14:38,760 --> 01:14:42,530 we have to compare all of these n times. 1727 01:14:42,530 --> 01:14:47,020 We do a whole lot of comparisons because if it's in reverse order, 1728 01:14:47,020 --> 01:14:50,360 we're going to say, OK, this is the same, this is good, 1729 01:14:50,360 --> 01:14:54,650 and this one will have to be compared against the first one to be moved back. 1730 01:14:54,650 --> 01:14:56,710 And as we get toward the tail end, we have 1731 01:14:56,710 --> 01:14:59,440 to compare, compare, and compare against everything. 1732 01:14:59,440 --> 01:15:03,030 >> So it ends up being approximately n squared. 1733 01:15:03,030 --> 01:15:09,510 If it's correct then you say, OK, 2, you're good. 1734 01:15:09,510 --> 01:15:11,330 3, you're compared to 2. 1735 01:15:11,330 --> 01:15:12,310 You're good. 1736 01:15:12,310 --> 01:15:14,150 4, you just compare to the tail. 1737 01:15:14,150 --> 01:15:14,990 You're good. 1738 01:15:14,990 --> 01:15:17,140 6, compare to the tail, you're fine. 1739 01:15:17,140 --> 01:15:20,870 So for every spot if it's already sorted, you're making one comparison. 1740 01:15:20,870 --> 01:15:22,320 So it's just n. 1741 01:15:22,320 --> 01:15:26,840 And because we have a best case runtime of n and a worst case runtime of n 1742 01:15:26,840 --> 01:15:28,680 squared, we have no expected runtime. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> It just depends on the chaos of our list there. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 And again, another graph and another table. 1747 01:15:39,530 --> 01:15:41,170 So differences between sorts. 1748 01:15:41,170 --> 01:15:44,180 I'm just going to breeze through, I feel like we've talked extensively 1749 01:15:44,180 --> 01:15:46,570 about how they all kind of vary and link together. 1750 01:15:46,570 --> 01:15:50,564 So merge sort is the last one I shall bore you guys with. 1751 01:15:50,564 --> 01:15:52,105 We do have a pretty colorful picture. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 So merge sort is a recursive algorithm. 1754 01:15:56,040 --> 01:15:59,910 So do you guys know what a recursive function is? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Anyone want to say? 1757 01:16:03,320 --> 01:16:04,739 You want to try? 1758 01:16:04,739 --> 01:16:07,280 So a recursive function is just a function that calls itself. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 So if you guys are familiar with the Fibonacci sequence, 1761 01:16:11,590 --> 01:16:15,670 that's deemed recursive because you take the previous two 1762 01:16:15,670 --> 01:16:17,530 and add them together to get your next one. 1763 01:16:17,530 --> 01:16:21,440 So recursive, I always think of recursion as like a spiral 1764 01:16:21,440 --> 01:16:24,430 so you're like spiraling down into it. 1765 01:16:24,430 --> 01:16:27,150 But it's just a function that calls itself. 1766 01:16:27,150 --> 01:16:32,660 >> And, actually, really quickly I can show you what that looks like. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 So recursive here, if we look, this is the recursive way to sum over an array. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 So all that we do is we have sum function 1771 01:16:47,880 --> 01:16:52,210 sum that takes a size and an array. 1772 01:16:52,210 --> 01:16:55,210 And if you notice, size decrements by one each time. 1773 01:16:55,210 --> 01:17:00,365 And all it does is if x is equal to zero-- so if the size of the array 1774 01:17:00,365 --> 01:17:02,710 is equal to zero-- it returns zero. 1775 01:17:02,710 --> 01:17:10,440 >> Otherwise it sums this last element of the array, 1776 01:17:10,440 --> 01:17:14,790 and then takes a sum of the rest of the array. 1777 01:17:14,790 --> 01:17:17,555 So it's just breaking it down into smaller and smaller problems. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Long story short, recursion, function that calls itself. 1780 01:17:21,890 --> 01:17:25,740 If that's all you got out of this, that's what a recursive function is. 1781 01:17:25,740 --> 01:17:29,870 If you take 51, you will get very, very comfortable with recursion. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 It's really cool. 1784 01:17:32,370 --> 01:17:34,660 It made sense at like 3 AM one night out. 1785 01:17:34,660 --> 01:17:37,900 And I was like, why have I never use this? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> So for merge sort, basically what it's going to do is it's 1788 01:17:42,430 --> 01:17:45,620 going to break it down and break it down until it's just single elements. 1789 01:17:45,620 --> 01:17:47,570 The single elements are easy to sort. 1790 01:17:47,570 --> 01:17:48,070 We see that. 1791 01:17:48,070 --> 01:17:50,760 If you have one element, it's already considered sorted. 1792 01:17:50,760 --> 01:17:53,800 So on an input of n elements, if n is less than 2, 1793 01:17:53,800 --> 01:17:58,120 just return because that means it's either 0 or 1 as we've seen. 1794 01:17:58,120 --> 01:18:00,050 Those are considered sorted elements. 1795 01:18:00,050 --> 01:18:02,170 >> Otherwise break it in half. 1796 01:18:02,170 --> 01:18:06,336 Sort the first half, sort the second half, and then merge them together. 1797 01:18:06,336 --> 01:18:07,460 Why it's called merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 So we have here we'll sort these. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 So we keep having them until the array size is 1. 1802 01:18:17,210 --> 01:18:20,790 So when it's 1, we just return because this is a sorted array, 1803 01:18:20,790 --> 01:18:23,940 and this is a sorted array, and that's a sorted array, we're all sorted. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 So then what we do is we start merging them together. 1806 01:18:29,420 --> 01:18:31,820 >> So the way you can think about merging is 1807 01:18:31,820 --> 01:18:36,240 you just remove the smaller number of each of the sub arrays 1808 01:18:36,240 --> 01:18:38,330 and just append it to the emerged array. 1809 01:18:38,330 --> 01:18:44,290 So if you look here, when we have these sets we have 4, 6, and 1. 1810 01:18:44,290 --> 01:18:47,280 When we want to merge these, we look at these first two 1811 01:18:47,280 --> 01:18:50,730 and we say, OK, 1 is smaller, it goes to the front. 1812 01:18:50,730 --> 01:18:54,330 4 and 6, there's nothing to compare it to, just tag it on to the end. 1813 01:18:54,330 --> 01:18:58,020 >> When we combine these two, we just take the smaller one of these two, 1814 01:18:58,020 --> 01:18:59,310 so it's 1. 1815 01:18:59,310 --> 01:19:01,690 And now we take the smaller of these two, so 2. 1816 01:19:01,690 --> 01:19:03,330 Smaller of these two, 3. 1817 01:19:03,330 --> 01:19:06,260 Smaller of these two, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 So you're just pulling off these. 1819 01:19:08,630 --> 01:19:11,210 And because they've been sorted previously, 1820 01:19:11,210 --> 01:19:14,300 you just have one comparison each time there. 1821 01:19:14,300 --> 01:19:19,610 So more code here, just representation. 1822 01:19:19,610 --> 01:19:24,410 So you start at the middle and you sort left and the right 1823 01:19:24,410 --> 01:19:26,180 and then you just merge those. 1824 01:19:26,180 --> 01:19:30,080 >> And we don't have code for merge right here. 1825 01:19:30,080 --> 01:19:34,110 But, again, if you go on study 50, it'll be there. 1826 01:19:34,110 --> 01:19:36,860 Otherwise come talk to me if you're still confused. 1827 01:19:36,860 --> 01:19:42,340 So cool thing here is that best case, worst case, and expected runtime 1828 01:19:42,340 --> 01:19:46,250 are all in log n, which is far better than we've 1829 01:19:46,250 --> 01:19:48,000 seen for the rest of our sorts. 1830 01:19:48,000 --> 01:19:51,840 We've seen n squared and what we actually 1831 01:19:51,840 --> 01:19:54,380 get here is n log n, which is great. 1832 01:19:54,380 --> 01:19:55,830 >> Look at how much better that is. 1833 01:19:55,830 --> 01:19:56,780 Such a nice curve. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 So much more efficient. 1836 01:20:00,120 --> 01:20:03,510 If you ever can, use merge sort. 1837 01:20:03,510 --> 01:20:04,810 It will save you time. 1838 01:20:04,810 --> 01:20:07,670 Then again, as we said, if you're down in this lower region, 1839 01:20:07,670 --> 01:20:09,480 it doesn't make that much of a difference. 1840 01:20:09,480 --> 01:20:11,360 You get up to thousands and thousands of inputs, 1841 01:20:11,360 --> 01:20:13,318 you definitely want a more efficient algorithm. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 And, again, our lovely table of all sorts that you guys learned today. 1844 01:20:19,400 --> 01:20:21,157 >> So I know it's been a dense day. 1845 01:20:21,157 --> 01:20:23,490 This isn't necessarily going to help you with your pset. 1846 01:20:23,490 --> 01:20:28,250 But I just want to make a disclaimer that section is not just about psets. 1847 01:20:28,250 --> 01:20:31,240 All this material is fair game for your midterms. 1848 01:20:31,240 --> 01:20:35,430 And also if you do continue on with CS, these are really important fundamentals 1849 01:20:35,430 --> 01:20:37,870 that you would need to know. 1850 01:20:37,870 --> 01:20:41,700 So some days will be a little more pset help, 1851 01:20:41,700 --> 01:20:44,600 but some weeks will be much more actual content 1852 01:20:44,600 --> 01:20:46,600 that may not seem super useful to you right now, 1853 01:20:46,600 --> 01:20:51,215 but I promise if you continue on will be very, very useful. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> So that's it for section. 1856 01:20:54,250 --> 01:20:55,250 Down to the wire. 1857 01:20:55,250 --> 01:20:56,570 I did it within one minute. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 But there you go. 1860 01:20:58,970 --> 01:21:01,240 And I will have donuts or candy. 1861 01:21:01,240 --> 01:21:03,464 Is anyone allergic to anything, by the way? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Eggs and milk. 1864 01:21:05,890 --> 01:21:08,120 So donuts are a no? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 All right. 1868 01:21:10,770 --> 01:21:12,120 Chocolate no? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts are good. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 We're going to have Starburst next week then. 1874 01:21:17,045 --> 01:21:18,240 That's what I'll get. 1875 01:21:18,240 --> 01:21:19,690 You guys have a great week. 1876 01:21:19,690 --> 01:21:20,460 Read your spec. 1877 01:21:20,460 --> 01:21:22,130 >> Let me know if you have any questions. 1878 01:21:22,130 --> 01:21:25,300 Pset two grades should be out to you by Thursday. 1879 01:21:25,300 --> 01:21:28,320 If you have any questions about how I graded something 1880 01:21:28,320 --> 01:21:32,250 or why I graded something the way I did, please email me, come talk to me. 1881 01:21:32,250 --> 01:21:34,210 I'm a little crazy this week, but I promise 1882 01:21:34,210 --> 01:21:36,340 I will still reply within 24 hours. 1883 01:21:36,340 --> 01:21:38,240 So have a great week, everyone. 1884 01:21:38,240 --> 01:21:40,090 Good luck on your pset. 1885 01:21:40,090 --> 01:21:41,248