WEBVTT X-TIMESTAMP-MAP=LOCAL:00:00:00.000,MPEGTS:900000 00:00:00.000 --> 00:00:03.437 [MUSIC PLAYING] 00:00:17.200 --> 00:00:20.110 DAVID MALAN: So odds are you know someone who is or perhaps are 00:00:20.110 --> 00:00:22.240 yourself a computer person. 00:00:22.240 --> 00:00:23.462 But what does that mean? 00:00:23.462 --> 00:00:25.420 Well I propose that a computer person is simply 00:00:25.420 --> 00:00:28.270 someone who's really good at computational thinking. 00:00:28.270 --> 00:00:32.200 Thinking methodically, or more formally, thinking algorithmically, 00:00:32.200 --> 00:00:35.770 whereby you take inputs to some problem, you solve that problem 00:00:35.770 --> 00:00:39.900 and produce output, but you do so step by step by step, along the way 00:00:39.900 --> 00:00:42.130 defining any of the terms or ideas that you 00:00:42.130 --> 00:00:44.410 need to use so that anyone else following along 00:00:44.410 --> 00:00:46.990 can understand exactly what it is you're doing. 00:00:46.990 --> 00:00:50.088 Computer science itself is really about computational thinking, then. 00:00:50.088 --> 00:00:51.880 It's not about programming, with which it's 00:00:51.880 --> 00:00:55.270 often conflated, although programming is a wonderfully useful tool with which 00:00:55.270 --> 00:00:58.150 you can solve problems, but computer science itself 00:00:58.150 --> 00:01:00.333 is about solving problems themselves. 00:01:00.333 --> 00:01:02.500 And it can be in any number of domains, whether it's 00:01:02.500 --> 00:01:05.710 software or hardware or artificial intelligence or machine learning 00:01:05.710 --> 00:01:07.045 or data science or beyond. 00:01:07.045 --> 00:01:09.170 That's the wonderful thing about computer science-- 00:01:09.170 --> 00:01:11.890 it's just so wonderfully applicable to other fields. 00:01:11.890 --> 00:01:14.440 It's all about equipping you with a mental model, 00:01:14.440 --> 00:01:16.390 so to speak, a set of concepts, as well as 00:01:16.390 --> 00:01:19.420 some practical skills via which you can bring to bear solutions 00:01:19.420 --> 00:01:22.490 to problems in other domains entirely. 00:01:22.490 --> 00:01:24.940 Now what, though, does it mean to solve a problem? 00:01:24.940 --> 00:01:28.090 I propose that we think about problem-solving quite simply as this. 00:01:28.090 --> 00:01:31.240 If you've got some problem to be solved, you have an input. 00:01:31.240 --> 00:01:34.690 And the goal is to solve that problem and come up with some solution, which 00:01:34.690 --> 00:01:36.190 we'll call simply our output. 00:01:36.190 --> 00:01:38.890 And in between those inputs and outputs hopefully 00:01:38.890 --> 00:01:42.460 are the step-by-step instructions via which we can solve that problem. 00:01:42.460 --> 00:01:45.370 Now how we're going to solve that problem we'll have to come back to. 00:01:45.370 --> 00:01:48.320 For now we'll consider it to be the proverbial black box. 00:01:48.320 --> 00:01:51.700 So we don't quite know or need to know right now just how it works, 00:01:51.700 --> 00:01:54.430 but that it can work, and we'll come back to this soon. 00:01:54.430 --> 00:01:57.940 But for now, we do need a way to represent these inputs, 00:01:57.940 --> 00:02:00.430 and we do need a way to represent our outputs. 00:02:00.430 --> 00:02:02.410 Right now I happen to be speaking English 00:02:02.410 --> 00:02:04.827 and you happen to be hearing English, and so we've sort of 00:02:04.827 --> 00:02:08.650 tacitly agreed that we'll represent our words using this particular language. 00:02:08.650 --> 00:02:12.117 Now computers tend not to use English, they have their own system, 00:02:12.117 --> 00:02:14.950 if you will, with what you might be familiar even if you don't quite 00:02:14.950 --> 00:02:17.590 speak it yourself, and indeed, there are different ways 00:02:17.590 --> 00:02:19.150 you can represent information. 00:02:19.150 --> 00:02:22.150 For instance, let's consider the simplest of problems-- for instance, 00:02:22.150 --> 00:02:24.010 counting the number of people in a room. 00:02:24.010 --> 00:02:25.220 I could do this old-school. 00:02:25.220 --> 00:02:29.030 I don't need computers or English, I can simply use my physical hand and say, 00:02:29.030 --> 00:02:30.780 I'm starting with zero people and now I'll 00:02:30.780 --> 00:02:35.260 count one, and then two, and then three, and then four, and then five, 00:02:35.260 --> 00:02:35.770 and then-- 00:02:35.770 --> 00:02:38.520 I'm out of fingers, but I can at least employ my other hand, maybe 00:02:38.520 --> 00:02:40.660 a couple of feet and get as high as 10, maybe even 00:02:40.660 --> 00:02:42.760 20 using this physical system. 00:02:42.760 --> 00:02:45.010 This is pretty equivalent, actually, to just keeping 00:02:45.010 --> 00:02:47.738 score counting the old-school way with hash marks. 00:02:47.738 --> 00:02:49.780 Right now we've not counted anything, but as soon 00:02:49.780 --> 00:02:53.080 as I start drawing some lines, I might represent the number 1, 00:02:53.080 --> 00:02:56.110 or 2 people in the room, or 3, or 4. 00:02:56.110 --> 00:02:59.350 Or by convention I can draw a slash just to make super clear that this is now 00:02:59.350 --> 00:03:01.900 representing 5, and then I can do another five of those 00:03:01.900 --> 00:03:04.250 to count up the 10 and beyond. 00:03:04.250 --> 00:03:07.660 Now these systems of hashes, as well as this system of counting on my fingers, 00:03:07.660 --> 00:03:08.830 actually has a name. 00:03:08.830 --> 00:03:10.410 That of unary notation. 00:03:10.410 --> 00:03:14.380 Uno implying one, simply signifying that I only have one digit-- 00:03:14.380 --> 00:03:16.990 pun not intended-- via which I can count things. 00:03:16.990 --> 00:03:20.678 This takes the form of my fingers on my hand or these hash marks on the screen. 00:03:20.678 --> 00:03:22.720 But it doesn't get me very far, because of course 00:03:22.720 --> 00:03:26.530 on my one hand with five fingers, I can only count up to five total. 00:03:26.530 --> 00:03:29.710 And even on the board it feels pretty inefficient, because for every number 00:03:29.710 --> 00:03:31.540 I want to count higher, I have to draw yet 00:03:31.540 --> 00:03:34.940 another line on the screen, which just continue to accumulate. 00:03:34.940 --> 00:03:37.090 But suppose we were a little more clever about this 00:03:37.090 --> 00:03:40.060 and we thought about this problem from a different angle. 00:03:40.060 --> 00:03:43.600 Maybe I could take into account not just the number of fingers 00:03:43.600 --> 00:03:46.660 that I've raised, but the order in which I've raised them 00:03:46.660 --> 00:03:50.080 or the pattern via which I've permuted them rather than just taking 00:03:50.080 --> 00:03:52.120 into account how many of them are up. 00:03:52.120 --> 00:03:56.050 If I take that approach, maybe I can actually count even higher than five 00:03:56.050 --> 00:03:59.460 on just one hand before resorting to another hand or feet. 00:03:59.460 --> 00:04:00.460 Now how could I do that? 00:04:00.460 --> 00:04:05.380 Well instead of counting up 0 to 1 to 2 to 3 to 4 00:04:05.380 --> 00:04:09.490 to 5, why do I instead start with some patterns instead? 00:04:09.490 --> 00:04:13.793 So I'll still start with 0, I'll still start with 1, but now for 2, 00:04:13.793 --> 00:04:15.710 I'm not just going to raise the second finger, 00:04:15.710 --> 00:04:19.390 I'm instead going to go from 0 to 1 to 2, 00:04:19.390 --> 00:04:22.750 putting down that first finger or thumb, simply representing 2 00:04:22.750 --> 00:04:24.130 with this one finger. 00:04:24.130 --> 00:04:26.170 And when I'm ready to represent the number 3, 00:04:26.170 --> 00:04:28.120 I'll bring that finger back up. 00:04:28.120 --> 00:04:32.650 And so using just two fingers now have I represented four possible values-- 00:04:32.650 --> 00:04:36.220 0, 1, 2, and 3. 00:04:36.220 --> 00:04:38.500 From 0 to 3, of course, is four total values, 00:04:38.500 --> 00:04:43.930 and so I've counted as high as 3 now using not three fingers, but only two. 00:04:43.930 --> 00:04:46.030 How, though, can I count higher than 3? 00:04:46.030 --> 00:04:48.100 Well, I just need to raise an additional finger. 00:04:48.100 --> 00:04:53.620 And so let's start at 0, to 1, to 2, to 3, to 4-- whoops-- 00:04:53.620 --> 00:04:56.680 to 5, to 6, and now to 7. 00:04:56.680 --> 00:05:00.790 And if it didn't hurt so much, I could continue counting as high as 8 and 9 00:05:00.790 --> 00:05:05.050 and 10 and beyond by simply permuting my fingers in different ways. 00:05:05.050 --> 00:05:07.420 So how high can I now count on this one hand? 00:05:07.420 --> 00:05:11.770 Using unary notation with fingers just up or down, I can count as high as 5-- 00:05:11.770 --> 00:05:13.450 from 0 to 5. 00:05:13.450 --> 00:05:17.070 But with these same five fingers, if I instead use not unary, 00:05:17.070 --> 00:05:19.710 but let's call it binary notation where we're actually 00:05:19.710 --> 00:05:24.178 taking into account whether the fingers are up or down and the pattern thereof, 00:05:24.178 --> 00:05:26.220 well now it would seem that each of these fingers 00:05:26.220 --> 00:05:29.830 can be in one of two possible states or configurations. 00:05:29.830 --> 00:05:33.480 They can either be up or they can be down, or just one of them can be up 00:05:33.480 --> 00:05:36.610 or can be down, or just one other can be up or down. 00:05:36.610 --> 00:05:40.740 So if there's two possible states or configurations for each of these five 00:05:40.740 --> 00:05:44.070 fingers, that's like 2 times 2 times 2 times 2 times 2, 00:05:44.070 --> 00:05:50.200 or 2 to the power of 5 for five fingers, which is actually 32 possible patterns. 00:05:50.200 --> 00:05:52.500 Which is to say with my one human hand, now can I 00:05:52.500 --> 00:05:59.130 count using not unary, but binary from 0 to 31, which is 32 possible values. 00:05:59.130 --> 00:06:00.450 Now what's the goal at hand? 00:06:00.450 --> 00:06:02.432 It's quite simply to represent information. 00:06:02.432 --> 00:06:04.140 Because if we have inputs and outputs, we 00:06:04.140 --> 00:06:07.770 need to decide a priori how we're going to represent those values. 00:06:07.770 --> 00:06:11.310 Now it turns out in computers, binary is wonderfully well-suited. 00:06:11.310 --> 00:06:14.670 Because after all, what's the one physical input to any computer 00:06:14.670 --> 00:06:17.490 you have, whether it's your laptop or desktop or these days, 00:06:17.490 --> 00:06:19.075 even a phone in your pocket? 00:06:19.075 --> 00:06:22.200 Well odds are, at the end of the day-- or even perhaps earlier in the day-- 00:06:22.200 --> 00:06:26.430 you need to physically plug that device into the wall and actually recharge it. 00:06:26.430 --> 00:06:28.890 And somehow or other there's electricity or electrons 00:06:28.890 --> 00:06:31.710 flowing from the wall that are stored in the battery in your device 00:06:31.710 --> 00:06:36.240 if it has a battery, and that is the input that drives your entire machine's 00:06:36.240 --> 00:06:37.470 operation. 00:06:37.470 --> 00:06:39.900 And so if that's the only possible input, 00:06:39.900 --> 00:06:42.930 it's pretty straightforward to imagine that you might have your computer 00:06:42.930 --> 00:06:46.230 plugged in or not, power is flowing or not, 00:06:46.230 --> 00:06:48.940 you've got a charge in your battery or you don't. 00:06:48.940 --> 00:06:53.280 And so this binary world where something can be in two possible states-- 00:06:53.280 --> 00:06:56.280 on or off, plugged in or not-- 00:06:56.280 --> 00:07:00.660 is wonderfully conducive to now using binary in the context of computers 00:07:00.660 --> 00:07:02.310 to represent information. 00:07:02.310 --> 00:07:04.230 After all, if I want to represent a number, 00:07:04.230 --> 00:07:06.390 I might simply turn on the lights. 00:07:06.390 --> 00:07:09.600 And so my phone here has a light built in, and right now that light is off, 00:07:09.600 --> 00:07:13.260 but if I consider this then to be off, we'll call it a 0. 00:07:13.260 --> 00:07:17.610 And if I turn this flashlight now on, I can be said to be representing a 1. 00:07:17.610 --> 00:07:21.000 And so simply with a simple light bulb can I represent two possible values 00:07:21.000 --> 00:07:22.860 just like my finger can be up and down. 00:07:22.860 --> 00:07:25.700 But computers don't necessarily use lots of little light bulbs, 00:07:25.700 --> 00:07:28.200 they use something else that's called a transistor. 00:07:28.200 --> 00:07:31.230 A transistor is a tiny little switch, and that switch, of course, 00:07:31.230 --> 00:07:35.250 can be either on or off-- letting electricity in or not. 00:07:35.250 --> 00:07:37.740 And so when you have a computer, inside of which 00:07:37.740 --> 00:07:40.868 is a motherboard and CPU and bunches of other pieces of hardware, 00:07:40.868 --> 00:07:42.660 one of the underlying components ultimately 00:07:42.660 --> 00:07:44.160 are these things called transistors. 00:07:44.160 --> 00:07:47.580 And computers today have millions of them inside, each of which 00:07:47.580 --> 00:07:50.610 can be on or off-- so far more than my five fingers, 00:07:50.610 --> 00:07:54.420 and that's ultimately how a computer can go about representing information. 00:07:54.420 --> 00:07:58.470 So long as it has access to some physical supply of electricity can 00:07:58.470 --> 00:08:00.510 it use that electricity to turn these switches 00:08:00.510 --> 00:08:05.520 on or off in distinct patterns, thereby representing 0, 1, 2, 3, 4, 00:08:05.520 --> 00:08:09.480 all the way up to 31 or even millions or billions or beyond. 00:08:09.480 --> 00:08:11.820 And so computers use binary. 00:08:11.820 --> 00:08:16.380 Computers speak binary-- only 0's and 1's or off and on, 00:08:16.380 --> 00:08:19.530 because it's so wonderfully well-conducive to the physical world 00:08:19.530 --> 00:08:21.420 on which they're ultimately based. 00:08:21.420 --> 00:08:23.460 We humans, meanwhile, tend to communicate 00:08:23.460 --> 00:08:25.650 not only in English and other spoken languages, 00:08:25.650 --> 00:08:28.230 but in a numeric system called decimal. 00:08:28.230 --> 00:08:31.860 So decimal, dec meaning 10, has 10 digits at its disposal-- 00:08:31.860 --> 00:08:36.539 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, whereas binary has just two-- 00:08:36.539 --> 00:08:39.990 0 and 1-- and unary, you might say, has just one-- 00:08:39.990 --> 00:08:43.049 1, the hash mark that I drew on the board. 00:08:43.049 --> 00:08:46.320 But if I only have 0's and 1's at my disposal, how can 00:08:46.320 --> 00:08:49.740 I possibly count to 2 or 3 or beyond? 00:08:49.740 --> 00:08:53.130 Well, we need some way of mapping these 0's and 1's to the more familiar 00:08:53.130 --> 00:08:54.960 numbers that we ourselves know. 00:08:54.960 --> 00:08:56.608 So how can we go about doing this? 00:08:56.608 --> 00:08:59.400 It's one thing to describe it in terms of patterns on your fingers, 00:08:59.400 --> 00:09:02.730 but again, a device just has switches that it can turn on and off. 00:09:02.730 --> 00:09:05.910 Well it turns out even if you don't yet speak binary 00:09:05.910 --> 00:09:07.860 or have never really thought about doing so, 00:09:07.860 --> 00:09:10.950 turns out that it's not all that dissimilar to the system of numbers 00:09:10.950 --> 00:09:12.090 with which we grew up. 00:09:12.090 --> 00:09:14.190 In fact, in grade school, you and I probably 00:09:14.190 --> 00:09:17.220 grew up learning how to represent numbers in rather the same way. 00:09:17.220 --> 00:09:18.630 For instance, consider this-- 00:09:18.630 --> 00:09:21.140 clearly the number 123. 00:09:21.140 --> 00:09:22.170 But why is that? 00:09:22.170 --> 00:09:24.930 It's not inherently the number 123. 00:09:24.930 --> 00:09:27.870 Really, this is just three symbols on the screen. 00:09:27.870 --> 00:09:31.140 We of course immediately recognize them as 1 and 2 and 3, 00:09:31.140 --> 00:09:35.607 and we infer from that, oh, this is the number 123, but why is that exactly? 00:09:35.607 --> 00:09:37.440 Well if you're like me, you probably grew up 00:09:37.440 --> 00:09:39.330 representing numbers in the following way, 00:09:39.330 --> 00:09:42.660 even if it's been quite some time since you thought about it like this. 00:09:42.660 --> 00:09:46.092 With the symbol here, 1, 2, and 3, if you're like me, 00:09:46.092 --> 00:09:48.300 you probably grew up thinking of this rightmost digit 00:09:48.300 --> 00:09:50.850 as being in the ones place, and this middle digit 00:09:50.850 --> 00:09:53.550 is being in the tens place, and this leftmost digit 00:09:53.550 --> 00:09:55.130 as being in the one hundredths place. 00:09:55.130 --> 00:09:56.880 And if it were a longer number, you'd have 00:09:56.880 --> 00:09:59.980 the one thousandths place and ten thousandths place and beyond. 00:09:59.980 --> 00:10:02.850 Now how do we get from 1, 2, 3 to 123? 00:10:02.850 --> 00:10:09.210 Well, the arithmetic we were taught says to do 100 times 1, and then 10 times 00:10:09.210 --> 00:10:14.160 2, and then 1 times 3, and then add all three of those products 00:10:14.160 --> 00:10:21.670 together, giving us, of course, 100 plus 20 plus 3, which of course is 123. 00:10:21.670 --> 00:10:25.160 Now that actually doesn't feel like much progress, because we started at 123 00:10:25.160 --> 00:10:27.980 and we got to 123, but that's not quite that. 00:10:27.980 --> 00:10:30.320 We actually started with the pattern of symbols-- 00:10:30.320 --> 00:10:34.430 1, 2, 3, like a pattern of fingers, and ultimately ascribe mathematical meaning 00:10:34.430 --> 00:10:37.340 to those symbols as 123. 00:10:37.340 --> 00:10:40.850 And it turns out computers, even though they speak binary and therefore only 00:10:40.850 --> 00:10:46.010 have 0's and 1's at their disposal-- no 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9, 00:10:46.010 --> 00:10:50.000 they count in exactly the same way, and they represent inputs and outputs 00:10:50.000 --> 00:10:52.100 in fundamentally the same way. 00:10:52.100 --> 00:10:53.420 Consider this. 00:10:53.420 --> 00:10:57.530 Suppose that I have 3 bits at my disposal, 3 switches or light bulbs, 00:10:57.530 --> 00:10:58.280 if you will. 00:10:58.280 --> 00:11:01.070 And those light bulbs or switches are all initially off. 00:11:01.070 --> 00:11:05.300 I claim that I'll represent those states as 0, 0, 0. 00:11:05.300 --> 00:11:08.960 And together, those three 0's represent the decimal number we ourselves know 00:11:08.960 --> 00:11:09.620 is 0. 00:11:09.620 --> 00:11:10.580 Now why is that? 00:11:10.580 --> 00:11:14.060 Well, if here if we consider this to be the ones place as before, 00:11:14.060 --> 00:11:16.700 but the middle digit we won't consider being in the tens place, 00:11:16.700 --> 00:11:19.640 we're going to consider this as being in the twos place, 00:11:19.640 --> 00:11:22.130 and this leftmost digit as being in the fours place. 00:11:22.130 --> 00:11:23.060 Now why? 00:11:23.060 --> 00:11:25.370 Well in our decimal system, there's a reason 00:11:25.370 --> 00:11:28.460 that we have the ones place, the tens place, the hundredths place, 00:11:28.460 --> 00:11:29.120 and beyond-- 00:11:29.120 --> 00:11:31.120 those are actually all powers of 10. 00:11:31.120 --> 00:11:35.040 10 to the 0, 10 to the 1, 10 to the 2, and beyond. 00:11:35.040 --> 00:11:39.290 Now in binary, bi meaning two, you only have two digits at your disposal, 0 00:11:39.290 --> 00:11:43.520 and 1, and so instead of using powers of 10, we're going to use powers of 2. 00:11:43.520 --> 00:11:44.750 And indeed we have. 00:11:44.750 --> 00:11:50.360 2 to the 0 is 1; 2 to the 1 is 2, 2 to the 2 is 4, and if we kept going, 00:11:50.360 --> 00:11:54.260 we'd get 8, 16, 32, 64, and beyond. 00:11:54.260 --> 00:11:57.170 And so this pattern of symbols or this pattern of light bulbs 00:11:57.170 --> 00:12:00.500 or this pattern of switches, all of which I'm proposing are off, 00:12:00.500 --> 00:12:03.740 simply represents now the number we humans know as 0. 00:12:03.740 --> 00:12:04.460 Why? 00:12:04.460 --> 00:12:10.790 Well we have 4 times 0 plus 2 times 0 plus 1 times 0, 00:12:10.790 --> 00:12:17.450 which of course gives me 0 plus 0 plus 0, for a total numeric value of 0. 00:12:17.450 --> 00:12:21.620 So in binary, 0, 0, 0 or all three switches off represents 0, 00:12:21.620 --> 00:12:23.360 and indeed, that's what we would expect. 00:12:23.360 --> 00:12:25.010 But we've instead we did this. 00:12:25.010 --> 00:12:28.970 Suppose that using binary, and therefore these same three places-- 00:12:28.970 --> 00:12:31.647 ones place, twos place, and fours place and beyond, 00:12:31.647 --> 00:12:33.230 we had a different pattern of symbols. 00:12:33.230 --> 00:12:35.420 How, for instance, might we represent 1? 00:12:35.420 --> 00:12:40.070 Well, if we had a pattern that's 0, 0, and 1 in binary, that's 00:12:40.070 --> 00:12:43.400 going to translate, of course, to the decimal number we all know and agree 00:12:43.400 --> 00:12:44.660 is the number 1. 00:12:44.660 --> 00:12:46.490 How do I represent the number 2? 00:12:46.490 --> 00:12:48.830 Well, if I start from scratch again, I'm going 00:12:48.830 --> 00:12:54.080 to represent the decimal number we know as 2 as a pattern that's 0, 1, and 0. 00:12:54.080 --> 00:12:57.170 A switch that's off, another that's on, another that's off. 00:12:57.170 --> 00:12:57.800 Why? 00:12:57.800 --> 00:13:03.080 4 times 0 is 0, 2 times 1 is 2, 1 times 0 is 0, 00:13:03.080 --> 00:13:05.040 and so we're left with total of 2. 00:13:05.040 --> 00:13:06.950 And if we want to represent 3, I don't even 00:13:06.950 --> 00:13:09.830 need to change the value or state of those switches, 00:13:09.830 --> 00:13:12.230 I can simply turn this one from off to on, 00:13:12.230 --> 00:13:14.380 and now I'm representing the number 3. 00:13:14.380 --> 00:13:18.050 If I want to count up to 4, I can simply start fresh in the fours place, 00:13:18.050 --> 00:13:20.180 in the twos place, in the ones place here-- 00:13:20.180 --> 00:13:22.430 1, 0, and 0. 00:13:22.430 --> 00:13:25.220 And then lastly, suppose that I want to count up even higher. 00:13:25.220 --> 00:13:31.640 7 can simply be 1, 1, and 1, because that gives me a 4, a 2, and a 1. 00:13:31.640 --> 00:13:34.190 4 plus 2 is 6, plus 1 is 7. 00:13:34.190 --> 00:13:36.530 But what if I want to represent the number 8? 00:13:36.530 --> 00:13:40.790 To represent the number 8, it would seem that I need a little more space. 00:13:40.790 --> 00:13:44.000 And so I might need to introduce the eights place so that I 00:13:44.000 --> 00:13:50.480 can have a 1, a 0, a 0, and a 0, eighth place being 2 to the 3, but to do this, 00:13:50.480 --> 00:13:52.250 I do indeed need more hardware. 00:13:52.250 --> 00:13:55.903 I need another switch, another light bulb, and another physical device 00:13:55.903 --> 00:13:56.820 inside of my computer. 00:13:56.820 --> 00:14:00.200 Now fortunately, our computers today have millions of these tiny transistors 00:14:00.200 --> 00:14:03.500 and switches, so it's not all that problematic to count as high as 8, 00:14:03.500 --> 00:14:07.190 but the implication is, that in order to represent larger and larger values, 00:14:07.190 --> 00:14:09.380 do we need more physical storage? 00:14:09.380 --> 00:14:12.800 And indeed, thematic and computer science is exactly that constraint. 00:14:12.800 --> 00:14:15.560 You can only do so much computationally, perhaps, 00:14:15.560 --> 00:14:20.060 if you have a finite amount of memory or a finite amount of hardware 00:14:20.060 --> 00:14:20.838 or switches. 00:14:20.838 --> 00:14:23.630 And we'll see, then, that there is non-trivial implications for how 00:14:23.630 --> 00:14:27.500 much data you can represent, and how many problems, therefore, 00:14:27.500 --> 00:14:28.648 you can solve. 00:14:28.648 --> 00:14:29.690 So that's it for numbers. 00:14:29.690 --> 00:14:33.080 Using just 0's and 1's can we count as high as we want and represent 00:14:33.080 --> 00:14:36.600 any number of values so long as we have enough bits at our disposal. 00:14:36.600 --> 00:14:38.930 But numbers only get us so far in computing. 00:14:38.930 --> 00:14:41.240 After all, it's not just Excel and calculators 00:14:41.240 --> 00:14:42.560 with which we use computers. 00:14:42.560 --> 00:14:44.930 It's of course to send information textually, 00:14:44.930 --> 00:14:48.710 and to use letters of the alphabet, and compose text messages and emails 00:14:48.710 --> 00:14:52.340 and documents and more, but how, then, do you represent letters 00:14:52.340 --> 00:14:54.980 if all you have at the end of the day are these 0's and 1's 00:14:54.980 --> 00:14:56.720 underneath the hood, so to speak? 00:14:56.720 --> 00:14:59.270 Well to do that, we all simply need to agree, 00:14:59.270 --> 00:15:02.270 just like we've agreed to speak in here English for now, 00:15:02.270 --> 00:15:06.530 on a particular system by which to represent letters of the alphabet. 00:15:06.530 --> 00:15:09.710 Now we don't have all that many choices at hand because if we only have 00:15:09.710 --> 00:15:12.710 0's and 1's-- switches that can be turned on and off-- 00:15:12.710 --> 00:15:14.750 that doesn't give us terribly many options. 00:15:14.750 --> 00:15:18.810 But what we could do as humans is just collectively agree that you know what? 00:15:18.810 --> 00:15:22.510 We are going to use a certain pattern of 0's and 1's to represent capital A. 00:15:22.510 --> 00:15:25.570 And we're going to use a different pattern of 0's and 1's to represent 00:15:25.570 --> 00:15:27.760 capital B. A different pattern of 0's and 1's 00:15:27.760 --> 00:15:30.882 to represent C and D and all the way through Z. And you know what? 00:15:30.882 --> 00:15:32.590 If we care about lowercase letters, we'll 00:15:32.590 --> 00:15:37.090 use slightly different patterns of 0's and 1's to represent those as well. 00:15:37.090 --> 00:15:39.430 And this is exactly what humans did decades ago. 00:15:39.430 --> 00:15:41.560 We standardized on something called ASCII-- 00:15:41.560 --> 00:15:44.200 the American Standard Code for Information Interchange, 00:15:44.200 --> 00:15:48.627 which was the result of people agreeing that we are going to use-- 00:15:48.627 --> 00:15:49.210 you know what? 00:15:49.210 --> 00:15:52.690 The number 65 in decimal to represent capital A, 00:15:52.690 --> 00:15:56.230 and the number 66 to represent capital B, 00:15:56.230 --> 00:15:59.500 and the number 97 to represent lowercase a, 00:15:59.500 --> 00:16:04.300 and 98 to represent lowercase b, and everything before and beyond. 00:16:04.300 --> 00:16:08.290 And so this system, this code, ASCII, is simply a collective agreement 00:16:08.290 --> 00:16:11.590 that whenever you're in the context of a text-based program and not 00:16:11.590 --> 00:16:14.530 a numeric-based program, any patterns of bits, 00:16:14.530 --> 00:16:18.550 such as those that might represent 65 in a calculator, 00:16:18.550 --> 00:16:22.030 should instead be interpreted in the context of Microsoft Word 00:16:22.030 --> 00:16:26.020 or an SMS message or iMessage as actually representing a letter. 00:16:26.020 --> 00:16:29.740 So how bits are interpreted is entirely context-dependent. 00:16:29.740 --> 00:16:32.843 Depending on the program you have opened, the same pattern of bits 00:16:32.843 --> 00:16:34.510 might be interpreted in different ways-- 00:16:34.510 --> 00:16:37.580 as numbers or letters or even something else. 00:16:37.580 --> 00:16:42.490 So how, then, do we represent so many other symbols 00:16:42.490 --> 00:16:44.320 that aren't just A through Z? 00:16:44.320 --> 00:16:46.480 Well it turns out that the American Standard 00:16:46.480 --> 00:16:48.520 Code for Information Interchange was indeed 00:16:48.520 --> 00:16:51.610 fairly skewed toward American representation of letters, 00:16:51.610 --> 00:16:52.780 particularly English. 00:16:52.780 --> 00:16:56.590 But there are so many more characters with accents and other symbology, let 00:16:56.590 --> 00:16:58.990 alone punctuation marks, and in foreign languages, 00:16:58.990 --> 00:17:02.410 too, are there hundreds if not thousands of distinct characters 00:17:02.410 --> 00:17:05.050 that you need to represent ideally in order to send that text 00:17:05.050 --> 00:17:06.250 and write that document. 00:17:06.250 --> 00:17:08.230 But ASCII alone couldn't handle it. 00:17:08.230 --> 00:17:12.880 Because ASCII tended to use 7 or maybe in some contexts 8 bits total, 00:17:12.880 --> 00:17:14.470 and with 8 bits-- 00:17:14.470 --> 00:17:16.569 or binary digits, if you will-- 00:17:16.569 --> 00:17:18.910 can you represent how many possible values-- 00:17:18.910 --> 00:17:22.690 2 times 2 times 2 times 2 times 2 times 2 times 2 times 00:17:22.690 --> 00:17:25.569 2 for 8 possible bits, each of which can be a 0 or 1. 00:17:25.569 --> 00:17:28.930 That only gives you 256 possible letters. 00:17:28.930 --> 00:17:32.490 Now that's more than enough for 26 letters of the English alphabet, A 00:17:32.490 --> 00:17:35.170 through Z, both uppercase and lowercase, but once you 00:17:35.170 --> 00:17:38.260 start adding in punctuation and accents and other characters, 00:17:38.260 --> 00:17:39.800 you very quickly run out. 00:17:39.800 --> 00:17:42.110 And so the world produced Unicode instead, 00:17:42.110 --> 00:17:45.340 which doesn't just use 8 bits or 1 byte, if you will-- 00:17:45.340 --> 00:17:47.860 1 byte simply meaning quite simply a bit, 00:17:47.860 --> 00:17:51.700 but instead introduced a variable length encoding of letters. 00:17:51.700 --> 00:17:54.520 And so some letters might use 8 bits or 1 byte. 00:17:54.520 --> 00:17:57.550 Other letters might use 2 bytes or 16 bits. 00:17:57.550 --> 00:18:00.250 Other letters might use 3 bytes or even 4. 00:18:00.250 --> 00:18:03.090 And via 4 possible bytes maximally-- 00:18:03.090 --> 00:18:07.090 2 to the 32 bits-- can you actually represent 4 billion possible values, 00:18:07.090 --> 00:18:08.950 which is a huge number of values. 00:18:08.950 --> 00:18:11.200 But how does the system of encoding actually work? 00:18:11.200 --> 00:18:13.030 Let's consider by way of an example. 00:18:13.030 --> 00:18:15.460 In both ASCII and Unicode, ASCII now being 00:18:15.460 --> 00:18:19.570 a subset of Unicode insofar as it only uses 1 byte per letter, 00:18:19.570 --> 00:18:21.280 you might represent A with-- 00:18:21.280 --> 00:18:25.007 capital A with 65, capital B with 66, and so forth. 00:18:25.007 --> 00:18:28.090 And dot-dot-dot implies we've handled the rest as well and they all happen 00:18:28.090 --> 00:18:29.650 to be back-to-back-to-back. 00:18:29.650 --> 00:18:32.470 So suppose in the context of a text message 00:18:32.470 --> 00:18:36.160 you happen to receive a pattern of 0's and 1's that if you actually 00:18:36.160 --> 00:18:38.380 did the math in the ones place and the twos place 00:18:38.380 --> 00:18:45.520 and so forth, actually worked out to be the decimal number 72, 73, 33. 00:18:45.520 --> 00:18:47.860 Well what text message have you just received? 00:18:47.860 --> 00:18:50.890 Of course at the end of the day, computers only understand binary, 00:18:50.890 --> 00:18:53.650 and that information is sent from phone to phone 00:18:53.650 --> 00:18:56.270 over the internet-- more on that another time. 00:18:56.270 --> 00:19:00.190 But those 0's and 1's interpreted in the context of a text messaging program 00:19:00.190 --> 00:19:03.160 will be interpreted not as binary, not as decimal, 00:19:03.160 --> 00:19:06.010 but probably as ASCII or more generally Unicode. 00:19:06.010 --> 00:19:11.500 And so if you've received a text message that says, 72, 73, 33, well what might 00:19:11.500 --> 00:19:12.400 that spell? 00:19:12.400 --> 00:19:14.860 Well if we consider our excerpt of a chart here, 00:19:14.860 --> 00:19:18.580 that's 72 and 73, of course, translates to H and an I, 00:19:18.580 --> 00:19:21.640 and you wouldn't know it from that preceding chart, but 33 it turns out-- 00:19:21.640 --> 00:19:24.520 just represents a very excited exclamation point, 00:19:24.520 --> 00:19:28.293 because that, too, has a representation in ASCII and Unicode. 00:19:28.293 --> 00:19:31.210 Now underneath the hood are patterns of 0's and 1's, but we don't need 00:19:31.210 --> 00:19:33.280 to think about things at that level. 00:19:33.280 --> 00:19:35.410 Indeed, what we've done here by introducing ASCII, 00:19:35.410 --> 00:19:37.390 and in turn, Unicode, is introduce what's 00:19:37.390 --> 00:19:41.110 called an abstraction, which is a technique in computer science via which 00:19:41.110 --> 00:19:45.580 we can think about a problem more usefully at a higher level as opposed 00:19:45.580 --> 00:19:48.550 to the lowest level in which it's actually implemented. 00:19:48.550 --> 00:19:51.850 After all, it'd be much easier to receive a message that you view 00:19:51.850 --> 00:19:53.550 as H-I-! 00:19:53.550 --> 00:19:55.870 than actually as a pattern of 0's and 1's that you then 00:19:55.870 --> 00:19:58.150 have to think about and translate in your head 00:19:58.150 --> 00:20:00.230 to the actual message that was intended. 00:20:00.230 --> 00:20:03.550 So an abstraction is just a way of taking a fairly low level if not very 00:20:03.550 --> 00:20:06.380 complicated representation and thinking about it 00:20:06.380 --> 00:20:08.680 in a higher, more useful level that lends itself 00:20:08.680 --> 00:20:12.890 more readily to communication, or more generally to problem-solving. 00:20:12.890 --> 00:20:15.417 Now what about all of those other characters on the screen? 00:20:15.417 --> 00:20:17.250 After all, on a typical board might you have 00:20:17.250 --> 00:20:20.800 letters and numbers and punctuation, but also these accented characters, too. 00:20:20.800 --> 00:20:24.900 Well thanks to Unicode, you indeed have as many as 4 billion possibilities, 00:20:24.900 --> 00:20:28.230 and it's no surprise, perhaps, that proliferating on the internet 00:20:28.230 --> 00:20:32.400 these days are a little friendly faces called emojis 00:20:32.400 --> 00:20:35.310 that you might have received yourself in text messages, emails, 00:20:35.310 --> 00:20:36.450 or some other form. 00:20:36.450 --> 00:20:40.530 Now these emojis here, though they might look like smiley faces, 00:20:40.530 --> 00:20:44.670 are actually characters that companies like Google and Microsoft and Apple 00:20:44.670 --> 00:20:47.310 have simply decided to represent pictorially. 00:20:47.310 --> 00:20:50.280 Underneath the hood, anytime you receive one of these emojis, 00:20:50.280 --> 00:20:52.860 you're actually receiving a pattern of bits-- 00:20:52.860 --> 00:20:56.400 0's and 1's that in the context of an email or text 00:20:56.400 --> 00:20:59.610 message or some other program, are being interpreted as 00:20:59.610 --> 00:21:02.613 and therefore displayed as a corresponding picture 00:21:02.613 --> 00:21:04.530 that Google and Microsoft and Apple and others 00:21:04.530 --> 00:21:06.840 have decided how to present visually. 00:21:06.840 --> 00:21:10.170 And indeed, different platforms present these same patterns of 0's and 1's 00:21:10.170 --> 00:21:13.410 differently depending on how the artist at those companies 00:21:13.410 --> 00:21:15.570 have decided to draw these emoji. 00:21:15.570 --> 00:21:20.370 Consider this one, for instance-- face with tears of joy is its formal name, 00:21:20.370 --> 00:21:25.330 but more technically, this is encoded by a very specific decimal number. 00:21:25.330 --> 00:21:32.160 Capital A is a 65, capital B is 66, what is this face with tears of joy? 00:21:32.160 --> 00:21:36.090 Well it is the number 128,514. 00:21:36.090 --> 00:21:38.430 After all, if you've got four billion possibilities, 00:21:38.430 --> 00:21:40.410 surely we could use something within that range 00:21:40.410 --> 00:21:42.802 to represent this face and any number of others. 00:21:42.802 --> 00:21:44.760 But underneath the hood, if you actually looked 00:21:44.760 --> 00:21:48.480 at a text message in which you received a face with tears of joy, 00:21:48.480 --> 00:21:52.890 what you've actually received is this pattern of 0's and 1's somehow encoded 00:21:52.890 --> 00:21:55.300 on your phone or your computer. 00:21:55.300 --> 00:21:58.530 And so in the context of a calculator or Microsoft Excel 00:21:58.530 --> 00:22:01.140 might we interpret some pattern of bits as numbers. 00:22:01.140 --> 00:22:03.240 And in the context of a text messaging program 00:22:03.240 --> 00:22:05.370 or Google Docs or Microsoft Word might we 00:22:05.370 --> 00:22:09.750 interpret that same pattern of bits as instead characters or even emoji. 00:22:09.750 --> 00:22:13.410 But what if we want to represent different types of media altogether? 00:22:13.410 --> 00:22:17.430 After all, the world of computing is not composed of just numbers and letters. 00:22:17.430 --> 00:22:22.543 There's also colors and images and videos and audio files and more, 00:22:22.543 --> 00:22:24.960 but at the end of the day, if we only have at our disposal 00:22:24.960 --> 00:22:29.160 0's and 1's, how do we go about representing all of those richer media? 00:22:29.160 --> 00:22:32.460 Well as before, we humans just need to agree collectively 00:22:32.460 --> 00:22:37.530 to represent those media using 0's and 1's in some standard way. 00:22:37.530 --> 00:22:40.318 Perhaps one of the most familiar acronyms, even if you've never 00:22:40.318 --> 00:22:43.610 really thought about what it is that you might see on a computer, is this one-- 00:22:43.610 --> 00:22:44.160 RGB. 00:22:44.160 --> 00:22:46.360 It stands for red, green, and blue. 00:22:46.360 --> 00:22:50.070 And this refers to the process by which many computers represent 00:22:50.070 --> 00:22:51.780 colors on the screen. 00:22:51.780 --> 00:22:52.980 In fact, what is a color? 00:22:52.980 --> 00:22:57.990 Well, you might represent the color black and white simply by a single bit. 00:22:57.990 --> 00:23:02.370 1 might represent black and 0 might represent white, or vice versa. 00:23:02.370 --> 00:23:05.730 We in that case only have what's called 1-bit color, whereby 00:23:05.730 --> 00:23:10.380 the bit is either on or off implying black or white or white or black. 00:23:10.380 --> 00:23:13.470 But with RGB, you actually use more bits than just one. 00:23:13.470 --> 00:23:15.810 Conventionally you would use 8 bits to represent 00:23:15.810 --> 00:23:19.830 red, 8 bits to represent green, and 8 bits to represent blue. 00:23:19.830 --> 00:23:26.070 So 24 bits total, the first 8 of which or first byte is red, second is green, 00:23:26.070 --> 00:23:27.420 third is blue. 00:23:27.420 --> 00:23:28.450 Now what does that mean? 00:23:28.450 --> 00:23:30.930 Well in order to represent a color, you simply 00:23:30.930 --> 00:23:33.240 decide, how much red do you want to add to the mix? 00:23:33.240 --> 00:23:34.920 How much green and how much blue? 00:23:34.920 --> 00:23:38.190 Combining essentially those wavelengths of light 00:23:38.190 --> 00:23:41.260 in order to see a disparate color on the screen. 00:23:41.260 --> 00:23:45.240 And if you think about red, green, and blue now as being single bytes each, 00:23:45.240 --> 00:23:50.040 that means you have a possible range of values of 0 to 255. 00:23:50.040 --> 00:23:54.420 After all, if a single byte is 8 bits, and with 8 bits, each of which 00:23:54.420 --> 00:23:59.490 can be a 0 or 1-- so 2 times 2 times 2 times 2 times 2 times 2 times 2 times 00:23:59.490 --> 00:24:01.620 2 gives you 256 values. 00:24:01.620 --> 00:24:05.121 So if you start from 0, you can count as high as 255. 00:24:05.121 --> 00:24:11.520 Suppose that you had 72 as your amount of red for a color, and 73 for green, 00:24:11.520 --> 00:24:13.138 and 33 for blue. 00:24:13.138 --> 00:24:15.180 That is to say in the context of a text messaging 00:24:15.180 --> 00:24:16.810 program, this same pattern of bits-- 00:24:16.810 --> 00:24:22.350 72, 73, 33 presented as decimal represented a textural message of HI!. 00:24:22.350 --> 00:24:24.600 But suppose you were to see that same pattern of bits 00:24:24.600 --> 00:24:29.220 instead in a photo-editing program like Photoshop, or in the context of opening 00:24:29.220 --> 00:24:30.540 an image on the screen. 00:24:30.540 --> 00:24:34.703 Well that same pattern of bits, or in turn, decimal numbers, just 00:24:34.703 --> 00:24:36.870 represents some amount of red, some amount of green, 00:24:36.870 --> 00:24:38.010 and some amount of blue. 00:24:38.010 --> 00:24:41.250 So 72 is a decent amount-- a medium amount 00:24:41.250 --> 00:24:45.510 of red out of 255 total values, 73 is a medium amount of green, 00:24:45.510 --> 00:24:47.880 and 33 is a little bit of blue. 00:24:47.880 --> 00:24:50.880 If you combine now all of these three values in your mind's eye 00:24:50.880 --> 00:24:54.370 by overlapping them, what you get is this shade of yellow. 00:24:54.370 --> 00:24:56.340 Which is to say that if you wanted to represent 00:24:56.340 --> 00:24:58.110 this particular shade of yellow would you 00:24:58.110 --> 00:25:03.690 use three bytes whose values are respectively 72, 73, and 33. 00:25:03.690 --> 00:25:07.080 And in the context of Photoshop or some other graphical program 00:25:07.080 --> 00:25:11.970 would that pattern be interpreted as and displayed as this color on the screen. 00:25:11.970 --> 00:25:15.180 Now this color is deliberately presented here as just 1 square-- 00:25:15.180 --> 00:25:18.360 1 dot, if you will, or more properly, 1 pixel. 00:25:18.360 --> 00:25:19.600 Because what is an image? 00:25:19.600 --> 00:25:22.410 Well if you've ever looked really close on your computer screen 00:25:22.410 --> 00:25:25.500 or on your phone or even on your TV, you might actually 00:25:25.500 --> 00:25:28.747 see all of the thousands of dots that compose it. 00:25:28.747 --> 00:25:31.080 This is getting harder to do on today's modern hardware, 00:25:31.080 --> 00:25:33.630 because if you have something like a retina display, 00:25:33.630 --> 00:25:36.930 that means these dots or pixels or ever so tiny and ever so close 00:25:36.930 --> 00:25:39.810 together that it's actually hard now for the human eye to see them, 00:25:39.810 --> 00:25:41.610 but they are in fact there. 00:25:41.610 --> 00:25:44.430 Any image on the screen, any photo on the screen 00:25:44.430 --> 00:25:47.100 is really just a pattern of dots or pixels-- 00:25:47.100 --> 00:25:50.400 a grid of dots from left to right, top to bottom. 00:25:50.400 --> 00:25:54.030 And every one of those dots or pixels on the screen 00:25:54.030 --> 00:25:59.760 probably has 24 bits representing its particular color. 00:25:59.760 --> 00:26:03.387 Indeed, a picture is essentially just a pattern of color so small 00:26:03.387 --> 00:26:05.220 that you don't really see all of those dots, 00:26:05.220 --> 00:26:08.760 but you see the net effect of a beautiful photo or image or something 00:26:08.760 --> 00:26:10.920 else altogether. 00:26:10.920 --> 00:26:13.140 So consider how we might see these. 00:26:13.140 --> 00:26:17.400 When Apple or Google or Microsoft or any other company that supports emojis 00:26:17.400 --> 00:26:20.130 presents those emojis on the screen, we of course 00:26:20.130 --> 00:26:22.650 see them as images because Apple and Microsoft and Google 00:26:22.650 --> 00:26:26.010 have decided what images shall be displayed when 00:26:26.010 --> 00:26:28.140 it receives a certain pattern of bits. 00:26:28.140 --> 00:26:30.720 But how are they storing those images and how 00:26:30.720 --> 00:26:34.350 is your Mac or PC or phone displaying that image to you? 00:26:34.350 --> 00:26:38.250 Well it's hard to see where those bits are let alone the pixels in it 00:26:38.250 --> 00:26:43.080 at this particular size, but if I go ahead and zoom in and zoom in and zoom 00:26:43.080 --> 00:26:46.050 in a little more still, you can begin to see 00:26:46.050 --> 00:26:51.000 the individual dots or squares or pixels that compose even this one emoji. 00:26:51.000 --> 00:26:56.020 And so just to display this smiling face, this face with tears of joy, 00:26:56.020 --> 00:27:00.600 do you need 24 bits for this pixel, 24 bits for this pixel, 00:27:00.600 --> 00:27:05.160 24 bits for this pixel, 24 bits for this pixel, and so on and so forth? 00:27:05.160 --> 00:27:08.850 So if you've ever noticed that when you download an image or download a photo 00:27:08.850 --> 00:27:12.450 or receive one in the mail, odds are it's not in the order of bytes. 00:27:12.450 --> 00:27:15.000 It's probably kilobytes for thousands of bytes, 00:27:15.000 --> 00:27:17.190 or megabytes for millions of bytes. 00:27:17.190 --> 00:27:21.270 How in the world does a simple photo have so many bytes or in turn bits? 00:27:21.270 --> 00:27:23.310 It's because every one of the dots in that image 00:27:23.310 --> 00:27:25.270 takes up some amount of space. 00:27:25.270 --> 00:27:28.740 So to represent yellow might we use a certain pattern of 0's and 1's or 3 00:27:28.740 --> 00:27:29.250 bytes. 00:27:29.250 --> 00:27:31.730 To represent black or gray or any other number-- 00:27:31.730 --> 00:27:36.640 colors on the screen might we represent those using different patterns still. 00:27:36.640 --> 00:27:40.490 Now that's it for images, but what about videos? 00:27:40.490 --> 00:27:43.160 A video is really just a sequence of images 00:27:43.160 --> 00:27:46.310 being presented to you so quickly that you and your human eye 00:27:46.310 --> 00:27:49.802 don't notice that you're really just watching image after image after image. 00:27:49.802 --> 00:27:52.010 In fact, it's conventional in Hollywood and elsewhere 00:27:52.010 --> 00:27:55.880 to display as many as 24 images or frames per second, 00:27:55.880 --> 00:27:59.540 or perhaps even 30 frames or images per seconds. 00:27:59.540 --> 00:28:02.600 And so even though they are in fact distinct images, 00:28:02.600 --> 00:28:05.750 you are seeing them so quickly, and the characters on the screen 00:28:05.750 --> 00:28:08.090 are moving within each frame or image ever 00:28:08.090 --> 00:28:12.035 so slightly, that it creates ultimately the illusion of movement. 00:28:12.035 --> 00:28:13.910 And if you think back to childhood, you might 00:28:13.910 --> 00:28:15.702 have had one of those old-school flip books 00:28:15.702 --> 00:28:19.790 on which was drawn some kind of cartoon one frame or image at a time. 00:28:19.790 --> 00:28:21.973 And if you flipped through that flip book one page 00:28:21.973 --> 00:28:24.140 ever so quickly again and again and again and again, 00:28:24.140 --> 00:28:27.230 letting the physics of it all take its toll, 00:28:27.230 --> 00:28:31.550 you might see a character or the picture in the book actually appearing to move, 00:28:31.550 --> 00:28:32.510 but it's not. 00:28:32.510 --> 00:28:35.840 All of those pages are just images and all of those images are not moving, 00:28:35.840 --> 00:28:38.570 but when you see them so fast and so quickly in succession 00:28:38.570 --> 00:28:40.700 does it appear to create that same movement. 00:28:40.700 --> 00:28:43.460 So these things here, Animojis in Apple's world, 00:28:43.460 --> 00:28:47.060 are just videos ultimately that track your facial movements and such, 00:28:47.060 --> 00:28:51.410 but all they really are are a pattern of bits, each set of which 00:28:51.410 --> 00:28:52.730 represents an image. 00:28:52.730 --> 00:28:55.520 And each of those images is displayed to you on your phone 00:28:55.520 --> 00:28:58.580 so quickly that you see the illusion of movement. 00:28:58.580 --> 00:29:00.380 And so here again is an abstraction. 00:29:00.380 --> 00:29:01.400 What is a video? 00:29:01.400 --> 00:29:03.500 Well, a video is a collection of images. 00:29:03.500 --> 00:29:04.490 Well what's an image? 00:29:04.490 --> 00:29:06.080 An image is a collection of pixels. 00:29:06.080 --> 00:29:07.130 Well what's a pixel? 00:29:07.130 --> 00:29:10.550 A pixel is simply some number of bits representing some amount of red 00:29:10.550 --> 00:29:11.630 and green and blue. 00:29:11.630 --> 00:29:12.500 Well what is a bit? 00:29:12.500 --> 00:29:16.070 It's simply a representation digitally of something being present, 00:29:16.070 --> 00:29:18.310 like electricity or not. 00:29:18.310 --> 00:29:20.870 And so it's much more powerful now to be operating 00:29:20.870 --> 00:29:24.680 at this level of abstraction-- talking about videos for what they are, and not 00:29:24.680 --> 00:29:27.832 getting into the weeds of the lowest level that at the end of the day, 00:29:27.832 --> 00:29:29.540 it's really just some form of electricity 00:29:29.540 --> 00:29:32.120 that we call bits, that we in turn call pixels, 00:29:32.120 --> 00:29:35.600 that we in turn called images, that we in turn call videos. 00:29:35.600 --> 00:29:38.660 And we can operate in a number of these layers of abstraction 00:29:38.660 --> 00:29:41.090 in order to represent inputs to some problem. 00:29:41.090 --> 00:29:44.690 To create a film, to convert a film, to display a film 00:29:44.690 --> 00:29:48.020 might be just one of the problems to solve. 00:29:48.020 --> 00:29:50.660 All right, so we now have a way to represent information, 00:29:50.660 --> 00:29:53.390 whether it's binary, decimal, or some other approach altogether. 00:29:53.390 --> 00:29:54.920 So it's time to solve problems. 00:29:54.920 --> 00:29:57.090 But how do we go about solving problems? 00:29:57.090 --> 00:29:59.120 What is inside of this black box? 00:29:59.120 --> 00:30:01.460 Well that's where our so-called algorithms 00:30:01.460 --> 00:30:04.768 are-- step-by-step instructions for solving some problem. 00:30:04.768 --> 00:30:06.560 And to solve these problems, we simply need 00:30:06.560 --> 00:30:08.750 to decide first what problem to solve. 00:30:08.750 --> 00:30:11.990 Well let's consider a familiar one, like that of looking up someone's name 00:30:11.990 --> 00:30:13.255 and number in a phone book. 00:30:13.255 --> 00:30:16.130 Now these days, the phone book, of course, takes a more digital form, 00:30:16.130 --> 00:30:18.922 but at the end of the day, these two formats are pretty equivalent. 00:30:18.922 --> 00:30:22.430 After all, here in my hand is a phone book with maybe 1,000 pages, 00:30:22.430 --> 00:30:25.400 on which are bunches of names and numbers sorted alphabetically 00:30:25.400 --> 00:30:26.570 from A to Z. 00:30:26.570 --> 00:30:29.810 On my phone, meanwhile, while I might have to click an icon instead, 00:30:29.810 --> 00:30:31.700 do I have contacts that are similarly sorted 00:30:31.700 --> 00:30:34.790 from A to Z by first name or last name, and touching any one of them 00:30:34.790 --> 00:30:36.240 pulls up its number. 00:30:36.240 --> 00:30:38.780 So this one, though, is a little more physical for us 00:30:38.780 --> 00:30:43.340 to see the solution to a problem, like finding, say, Mike Smith. 00:30:43.340 --> 00:30:45.950 Mike Smith may or may not be in this phone book, but if he is, 00:30:45.950 --> 00:30:47.750 my goal quite simply is to find him. 00:30:47.750 --> 00:30:49.110 So let me try this. 00:30:49.110 --> 00:30:51.260 Let me try opening this book, and then one step 00:30:51.260 --> 00:30:53.600 at a time looking down for Mike Smith. 00:30:53.600 --> 00:30:56.120 And if I don't see him, move on to the next page. 00:30:56.120 --> 00:30:59.660 If I still don't see him, move on to the next page, and next page, 00:30:59.660 --> 00:31:02.990 and next page, and so forth, one page at a time. 00:31:02.990 --> 00:31:06.800 I propose that we consider first-- is this algorithm correct? 00:31:06.800 --> 00:31:11.090 Opening the phone book, looking down, turning page, and repeating. 00:31:11.090 --> 00:31:13.550 Well, at some point, if Mike is in this phone book, 00:31:13.550 --> 00:31:16.097 I am going to reach him, at which point I can call him. 00:31:16.097 --> 00:31:17.930 And if Mike Smith is not in this phone book, 00:31:17.930 --> 00:31:19.490 I'm eventually not going to reach him, but I 00:31:19.490 --> 00:31:21.865 am going to hit the end of the phone book, at which point 00:31:21.865 --> 00:31:23.690 I'll presumably stop. 00:31:23.690 --> 00:31:27.770 But it doesn't feel terribly efficient, however correct it may be. 00:31:27.770 --> 00:31:28.770 Why is it not efficient? 00:31:28.770 --> 00:31:30.350 Well I'm starting at the beginning of the phone book. 00:31:30.350 --> 00:31:32.690 I know it's alphabetical, and yet I'm turning one page 00:31:32.690 --> 00:31:35.780 at a time through the A's, through the B's, through the C's and beyond, 00:31:35.780 --> 00:31:38.420 just waiting and waiting until I finally reach Mike Smith. 00:31:38.420 --> 00:31:39.767 Well how might I do this better? 00:31:39.767 --> 00:31:41.600 Well, I learned in grade school not only how 00:31:41.600 --> 00:31:43.520 to count by ones, but also an account by twos. 00:31:43.520 --> 00:31:48.020 So instead of 1 page, 2 page, 3 page, 4, why don't instead do 2, 00:31:48.020 --> 00:31:52.610 4, 6, 8, 10, 12-- flying through the phone book. 00:31:52.610 --> 00:31:56.480 It certainly sounds faster, and it is, but is that approach correct? 00:31:56.480 --> 00:31:59.390 Well, I propose that there could be a problem. 00:31:59.390 --> 00:32:03.470 I might just get unlucky, and once I do reach the S section of the phone book, 00:32:03.470 --> 00:32:07.340 what if by bad luck Mike Smith is sandwiched between two of those pages? 00:32:07.340 --> 00:32:11.000 And therefore I hit the T section and Z section and run out of pages? 00:32:11.000 --> 00:32:13.520 I might conclude incorrectly that Mike Smith is not, 00:32:13.520 --> 00:32:15.040 in fact, in this phone book. 00:32:15.040 --> 00:32:17.810 But do I have to throw out the algorithm altogether? 00:32:17.810 --> 00:32:19.220 Probably not, right? 00:32:19.220 --> 00:32:21.740 I could be a little clever here and improve this algorithm, 00:32:21.740 --> 00:32:25.400 maintaining its efficiency, but fixing its correctness. 00:32:25.400 --> 00:32:29.830 After all, if I do see a page on which there are last names starting with T, 00:32:29.830 --> 00:32:32.900 while I can stop and say, well we know Mike is not farther than this 00:32:32.900 --> 00:32:35.660 because Smith starts with S, so I can double-back hopefully 00:32:35.660 --> 00:32:39.320 just one page or few, and therefore fix what's 00:32:39.320 --> 00:32:41.782 otherwise an incorrect approach in this algorithm. 00:32:41.782 --> 00:32:43.490 In fact, I can be even smarter than that. 00:32:43.490 --> 00:32:47.810 As soon as I see someone's name that starts with S-N instead of S-M, 00:32:47.810 --> 00:32:50.780 I can similarly flip back one page and therefore ensure 00:32:50.780 --> 00:32:53.390 that I can go twice as fast through most of the phone book, 00:32:53.390 --> 00:32:57.620 and only once I hit that section do I have to double-back one or terribly few 00:32:57.620 --> 00:32:58.130 pages. 00:32:58.130 --> 00:33:02.030 So I get the overall performance gains, and I also solve the problem. 00:33:02.030 --> 00:33:05.000 But honestly, if you even use this technology anymore, 00:33:05.000 --> 00:33:07.850 odds are you don't start at the beginning turning one or two 00:33:07.850 --> 00:33:08.947 pages at a time. 00:33:08.947 --> 00:33:11.030 If you're like me, you probably more instinctively 00:33:11.030 --> 00:33:12.710 open up roughly to say the middle. 00:33:12.710 --> 00:33:15.380 You'll look down and you realize, oh, I haven't found Mike yet 00:33:15.380 --> 00:33:17.785 because I'm actually here in the M section. 00:33:17.785 --> 00:33:20.240 But what do you know about where you've just jumped? 00:33:20.240 --> 00:33:22.700 Well Mike Smith is indeed to the right here, 00:33:22.700 --> 00:33:25.970 because he's in the name starting with S. But if I'm in the M section, 00:33:25.970 --> 00:33:27.380 I do know something else. 00:33:27.380 --> 00:33:30.320 I know that Mike is not in the left-hand section of this book-- 00:33:30.320 --> 00:33:32.720 he is not among the A through M's. 00:33:32.720 --> 00:33:37.460 And so I can both literally and figuratively tear this problem in half, 00:33:37.460 --> 00:33:41.090 throw half of it away, thereby leaving myself with just, 00:33:41.090 --> 00:33:43.640 say, 500 pages out of 1,000. 00:33:43.640 --> 00:33:47.160 So whereas that first algorithm I took one byte at a time out of it-- 00:33:47.160 --> 00:33:51.140 one page at a time, the second algorithm I took two bytes at a time out of it-- 00:33:51.140 --> 00:33:52.250 two at a time. 00:33:52.250 --> 00:33:56.150 Well with this algorithm, I just took 500 bytes out of the problem 00:33:56.150 --> 00:34:00.350 all at once, thereby getting closer to the output to this problem 00:34:00.350 --> 00:34:01.620 much more quickly. 00:34:01.620 --> 00:34:02.450 What do I then do? 00:34:02.450 --> 00:34:06.530 Well, I simply am probably going to apply that same algorithm again 00:34:06.530 --> 00:34:09.230 and again and again-- dividing and conquering this phone book, 00:34:09.230 --> 00:34:09.860 if you will. 00:34:09.860 --> 00:34:12.739 Jumping roughly to the middle now, looking down-- dah, darn it! 00:34:12.739 --> 00:34:15.429 I ended up in the T section now, so I've gone too far, 00:34:15.429 --> 00:34:17.929 but I know Mike is not in the right-hand side of this book-- 00:34:17.929 --> 00:34:20.030 he's not among the T's through Z's. 00:34:20.030 --> 00:34:23.870 So I can again tear the problem in half, throw that half away, 00:34:23.870 --> 00:34:27.000 thereby leaving me with just a quarter of the original problem, 00:34:27.000 --> 00:34:30.949 say 250 pages down, down from 1,000, finding Mike ever 00:34:30.949 --> 00:34:33.210 so much more quickly than before. 00:34:33.210 --> 00:34:37.159 And if I repeat and I repeat and I repeat, each time actually looking down 00:34:37.159 --> 00:34:40.760 looking for Mike, I should hopefully find myself ultimately left 00:34:40.760 --> 00:34:45.199 with just a single page on which Mike either is or is not, at which point 00:34:45.199 --> 00:34:47.610 I can call him or quit. 00:34:47.610 --> 00:34:52.070 So just how much more quickly did I find Mike Smith via this algorithm 00:34:52.070 --> 00:34:53.420 than the first two? 00:34:53.420 --> 00:34:56.989 Well in a 1,000-page phone book, I might get unlucky and Mike's not even there, 00:34:56.989 --> 00:35:01.080 and so in the worst case, I might look in as many as 1,000 pages. 00:35:01.080 --> 00:35:04.450 In the second algorithm, I might also get unlucky and not ever find Mike 00:35:04.450 --> 00:35:08.780 because he's just not there, and therefore look at as many 500 pages. 00:35:08.780 --> 00:35:11.000 But in this third algorithm where I'm iteratively 00:35:11.000 --> 00:35:15.440 dividing and conquering again and again, splitting the problem in half 00:35:15.440 --> 00:35:19.130 so I go from a very large input to a much smaller to an even smaller problem 00:35:19.130 --> 00:35:23.900 still again and again, how many times might I split that phone in half? 00:35:23.900 --> 00:35:27.980 Well if I start off with roughly 1,000 pages and I split it in half, 00:35:27.980 --> 00:35:32.090 that gives me 500, 250, 125, and so forth. 00:35:32.090 --> 00:35:36.410 Turns out that I can split 1,000 pages roughly 10 times in total 00:35:36.410 --> 00:35:38.860 before I'm left with just that final page. 00:35:38.860 --> 00:35:40.790 And so consider the implications of that. 00:35:40.790 --> 00:35:42.860 First algorithm-- 1,000 steps, maybe. 00:35:42.860 --> 00:35:45.140 Second algorithm-- 500 steps, maybe. 00:35:45.140 --> 00:35:50.720 Third algorithm-- 10 steps, maybe, to find Mike Smith before I can call 00:35:50.720 --> 00:35:52.275 or decide he's not there. 00:35:52.275 --> 00:35:53.900 And that's a pretty powerful technique. 00:35:53.900 --> 00:35:57.610 And if we extrapolate from this relatively small example or phone book 00:35:57.610 --> 00:35:59.990 to maybe a much larger phone book, say a phone book 00:35:59.990 --> 00:36:03.738 that a bit nonsensically has 4 billion pages in it, well, 00:36:03.738 --> 00:36:05.780 how many steps might those three algorithms take? 00:36:05.780 --> 00:36:08.120 The first algorithm might take 4 billion. 00:36:08.120 --> 00:36:10.430 The second algorithm might take 2 billion. 00:36:10.430 --> 00:36:13.520 The third algorithm might take 4 billion divided 00:36:13.520 --> 00:36:16.220 by 2 divided by 2 divided by 2-- 00:36:16.220 --> 00:36:21.620 you can divide 4 billion and half roughly 32 times only, at which point 00:36:21.620 --> 00:36:23.780 you're left with just that one page. 00:36:23.780 --> 00:36:26.570 So 4 billion steps for the first algorithm, 2 billion 00:36:26.570 --> 00:36:31.520 steps for the second algorithm, but 32 steps for the third algorithm. 00:36:31.520 --> 00:36:35.900 And simply by harnessing this intuition that we all probably already have 00:36:35.900 --> 00:36:39.990 in formalizing it in more methodical form-- in algorithmic form, 00:36:39.990 --> 00:36:42.920 if you will, can we solve problems using some of the building 00:36:42.920 --> 00:36:45.110 blocks that we already have at our disposal. 00:36:45.110 --> 00:36:47.320 And indeed, problem-solving in computer science 00:36:47.320 --> 00:36:49.790 is all about implementing these algorithms 00:36:49.790 --> 00:36:53.330 and applying them to problems of interest to you. 00:36:53.330 --> 00:36:56.500 But how do we think about just how good this algorithm is? 00:36:56.500 --> 00:37:00.310 It sort of stands to reason that it has to be minimally correct. 00:37:00.310 --> 00:37:01.930 But how efficient is it? 00:37:01.930 --> 00:37:04.060 I've been talking in terms of absolute numbers. 00:37:04.060 --> 00:37:08.860 1,000, 500, or 10, or 4 billion, 2 billion, and 32. 00:37:08.860 --> 00:37:12.640 But it would be nice to compare algorithms in a more general way 00:37:12.640 --> 00:37:15.850 so that I can use the same searching algorithm, if you will, 00:37:15.850 --> 00:37:17.710 to find not Mike Smith, but someone else. 00:37:17.710 --> 00:37:21.550 Or to search not a phone book, but Google or search engine more generally. 00:37:21.550 --> 00:37:24.460 And so computer scientists also have a more formal technique 00:37:24.460 --> 00:37:27.710 via which to describe the efficiency of algorithms. 00:37:27.710 --> 00:37:31.480 And we might consider these not even with numbers or formulas, per se, 00:37:31.480 --> 00:37:34.180 but with simple visual representations thereof. 00:37:34.180 --> 00:37:35.800 Here, for instance, is a simple plot. 00:37:35.800 --> 00:37:39.140 On the x or horizontal axis is going to be the size of the problem. 00:37:39.140 --> 00:37:42.250 How many pages are in the phone book, which we'll generally call n, 00:37:42.250 --> 00:37:44.650 where n is a number for a computer scientist. 00:37:44.650 --> 00:37:46.900 Much like a mathematician might go with x or y 00:37:46.900 --> 00:37:50.080 or z, computer scientists might tend to start counting with n. 00:37:50.080 --> 00:37:51.950 On the vertical or y-axis here, we'll say 00:37:51.950 --> 00:37:53.950 this is going to be the time to solve a problem, 00:37:53.950 --> 00:37:56.020 be it a phone book or something else. 00:37:56.020 --> 00:37:58.600 And that might be seconds or minutes or page turns 00:37:58.600 --> 00:38:02.230 or some other quantifiable unit of measure. 00:38:02.230 --> 00:38:06.460 So how do I go about describing that first algorithm where 00:38:06.460 --> 00:38:08.320 I turn one page at a time? 00:38:08.320 --> 00:38:13.060 Well I propose that it manifests a linear relationship, or n, or a line, 00:38:13.060 --> 00:38:14.530 a straight line on the chart. 00:38:14.530 --> 00:38:16.100 Why is it a straight line? 00:38:16.100 --> 00:38:18.730 Well, if Verizon or the local phone company, for instance, 00:38:18.730 --> 00:38:22.510 next year adds just one more page to that phone book, that means for me, 00:38:22.510 --> 00:38:25.450 it might take me one more unit of measure of time 00:38:25.450 --> 00:38:29.770 to find someone like Mike Smith, because we've gone from 1,000 to 1001 pages. 00:38:29.770 --> 00:38:33.340 So the slope of this line indeed can be straight or linear. 00:38:33.340 --> 00:38:36.100 That second algorithm now where I'm flying through the phone book 00:38:36.100 --> 00:38:40.870 twice as fast is really fundamentally the same algorithm or same shape. 00:38:40.870 --> 00:38:44.090 It just so happens that for a given size of the problem, 00:38:44.090 --> 00:38:46.390 it's not going to take this many seconds n, 00:38:46.390 --> 00:38:49.150 it's going to take me n over 2 seconds because I'm 00:38:49.150 --> 00:38:51.100 doing twice as much work at a time. 00:38:51.100 --> 00:38:54.070 And so this line, too, is linear or straight, 00:38:54.070 --> 00:38:58.570 but we might describe it in terms of n over 2, where n is the number of pages 00:38:58.570 --> 00:39:01.720 but I only have to look at half of them except for maybe that very last one 00:39:01.720 --> 00:39:05.620 if I double-back, and so its shape is fundamentally the same. 00:39:05.620 --> 00:39:08.830 So better, but not fundamentally better, it would seem. 00:39:08.830 --> 00:39:13.180 But that third and final algorithm has a fundamentally disparate shape, 00:39:13.180 --> 00:39:18.170 depicted here with our green curved line which has a logarithmic slope to it. 00:39:18.170 --> 00:39:21.310 So if n is the number of pages, and the algorithm in use 00:39:21.310 --> 00:39:25.930 is division and conquering, it turns out that has a logarithmic slope. 00:39:25.930 --> 00:39:27.650 Now what does that actually mean? 00:39:27.650 --> 00:39:31.420 Well it turns out that if Verizon adds one more page to the phone book 00:39:31.420 --> 00:39:34.480 next year, that is a drop in the bucket for that final algorithm where 00:39:34.480 --> 00:39:36.550 I'm just tearing the problem in half. 00:39:36.550 --> 00:39:40.030 But more powerfully, if Verizon doesn't just add one page, 00:39:40.030 --> 00:39:43.600 perhaps to neighboring towns merged together and form one massive phone 00:39:43.600 --> 00:39:47.260 book next year, going from 1,000 pages to 2,000 pages 00:39:47.260 --> 00:39:49.720 all in one big, fat book, well how many more 00:39:49.720 --> 00:39:53.410 steps does it take that third algorithm to search for anyone in it? 00:39:53.410 --> 00:39:54.460 Just one. 00:39:54.460 --> 00:39:58.960 Because with 2,000 pages, you can take 1,000-page byte out of that problem all 00:39:58.960 --> 00:40:02.560 in one fell swoop even though it's twice as big as before. 00:40:02.560 --> 00:40:07.030 And so even as the size of the problem gets bigger and bigger and bigger 00:40:07.030 --> 00:40:09.430 and even farther away, the amount of time 00:40:09.430 --> 00:40:12.740 it takes to solve a problem using that algorithm only 00:40:12.740 --> 00:40:15.460 increases ever so slightly. 00:40:15.460 --> 00:40:18.010 That's not a one-to-one or a one-to-two ratio, 00:40:18.010 --> 00:40:20.440 it's instead said to be logarithmic. 00:40:20.440 --> 00:40:23.560 And this, then, is a fundamentally different curve-- 00:40:23.560 --> 00:40:27.910 it's a fundamentally better algorithm in that the problem can grow exponentially 00:40:27.910 --> 00:40:31.450 large, and the amount of time it takes to solve it itself 00:40:31.450 --> 00:40:33.940 grows far less quickly than that. 00:40:38.530 --> 00:40:40.780 Now it's one thing to talk about all these algorithms. 00:40:40.780 --> 00:40:42.760 At some point we need to put them to paper, 00:40:42.760 --> 00:40:45.980 or more technically, program them into a computer. 00:40:45.980 --> 00:40:50.380 So how do we go about formalizing these step-by-step instructions in such a way 00:40:50.380 --> 00:40:53.140 that all of us can agree that they are correct, all of us 00:40:53.140 --> 00:40:56.080 can discuss their efficiency, and most importantly, all of us 00:40:56.080 --> 00:40:59.740 can program a device to execute these steps for us? 00:40:59.740 --> 00:41:02.080 Well let me propose that we first implement 00:41:02.080 --> 00:41:05.590 an algorithm like that of searching a phone book in what's called pseudocode. 00:41:05.590 --> 00:41:09.190 Pseudocode is not a formal programming language, it has no one definition. 00:41:09.190 --> 00:41:12.730 It generally means using short, succinct phrases, often in English, 00:41:12.730 --> 00:41:16.300 to describe your algorithm step-by-step-by-step in such a way that 00:41:16.300 --> 00:41:20.470 you yourself understand it, and anyone reading it can also understand it. 00:41:20.470 --> 00:41:23.260 Now along the way do you have to make certain assumptions, 00:41:23.260 --> 00:41:27.370 because you need to decide at what layer of abstraction to actually operate. 00:41:27.370 --> 00:41:29.620 And we'll take a look at where the opportunities there 00:41:29.620 --> 00:41:31.600 are, but let me propose that we implement 00:41:31.600 --> 00:41:33.970 this algorithm for searching for Mike Smith, 00:41:33.970 --> 00:41:36.340 for instance, in the following way. 00:41:36.340 --> 00:41:40.810 Now this is an algorithm, or really, a program, albeit written in pseudocode. 00:41:40.810 --> 00:41:43.450 And even though written in pseudocode or English, it 00:41:43.450 --> 00:41:45.820 manifests certain constructs that we're actually 00:41:45.820 --> 00:41:49.240 going to see in any number of today's popular programming languages, 00:41:49.240 --> 00:41:52.360 a programming language being an English-like language 00:41:52.360 --> 00:41:54.880 that humans have decided can be used in a certain way 00:41:54.880 --> 00:41:56.650 to tell a computer what to do. 00:41:56.650 --> 00:41:59.080 Now this pseudocode is just for us humans, 00:41:59.080 --> 00:42:01.330 but what are some of the fundamental constructs 00:42:01.330 --> 00:42:04.480 in it that we'll see in actual programming languages? 00:42:04.480 --> 00:42:06.550 Well first highlighted in yellow here are 00:42:06.550 --> 00:42:10.630 all of the verbs or actions that more technically we'll call functions. 00:42:10.630 --> 00:42:14.740 Statements that tell the computer, or in this case, human what to do. 00:42:14.740 --> 00:42:19.630 Pickup, open to, look at, call, open or open, or quit-- all of them 00:42:19.630 --> 00:42:20.800 calls to actions. 00:42:20.800 --> 00:42:23.530 In the context of a computer with these same types of verbs, 00:42:23.530 --> 00:42:25.660 we more traditionally call it functions. 00:42:25.660 --> 00:42:28.120 What else is laying inside of this program? 00:42:28.120 --> 00:42:29.990 Well these pictured here in yellow. 00:42:29.990 --> 00:42:33.250 If, else if, else if, else, well these represent 00:42:33.250 --> 00:42:35.650 what are called conditions or branches. 00:42:35.650 --> 00:42:37.960 Forks in the road, so to speak, via which 00:42:37.960 --> 00:42:41.410 you make a decision to go this way or this way or this way or that. 00:42:41.410 --> 00:42:44.020 But how do you decide down which road to go? 00:42:44.020 --> 00:42:46.120 You need what are called Boolean expressions. 00:42:46.120 --> 00:42:49.840 Named after mathematician Boole, these Boolean expressions 00:42:49.840 --> 00:42:52.960 are short phrases that either have yes or no answers, 00:42:52.960 --> 00:42:58.060 or true or false answers, or if you will, 1 or 0-- on or off answers. 00:42:58.060 --> 00:43:01.210 Smith is among names, Smith is earlier in book. 00:43:01.210 --> 00:43:04.210 Smith is later in book-- each of them could be asked effectively 00:43:04.210 --> 00:43:06.220 with a question mark to which the answer is 00:43:06.220 --> 00:43:08.860 yes or no, and based on that answer can you 00:43:08.860 --> 00:43:11.920 go down any one of those four roads. 00:43:11.920 --> 00:43:13.390 And then lastly is this-- 00:43:13.390 --> 00:43:16.150 go back to step 2 or go back to step 2. 00:43:16.150 --> 00:43:19.360 Highlighted in yellow here's an example of a loop, a deliberate 00:43:19.360 --> 00:43:23.380 cycle that gets you to do something again and again 00:43:23.380 --> 00:43:27.400 and again until some condition is no longer true 00:43:27.400 --> 00:43:30.500 and you eventually quit or call Mike instead. 00:43:30.500 --> 00:43:33.760 And so looping in a program allows you to write less code, 00:43:33.760 --> 00:43:35.830 but do something again and again and again just 00:43:35.830 --> 00:43:39.838 by referring back to some work that you've already done. 00:43:39.838 --> 00:43:42.880 Now these constructs, though we've seen them in the context of pseudocode 00:43:42.880 --> 00:43:46.270 and searching a phone book, can be found in any number of languages 00:43:46.270 --> 00:43:49.630 and programs, be it Python or C++ or Java. 00:43:49.630 --> 00:43:52.300 And so when it comes to programming a computer, or more 00:43:52.300 --> 00:43:54.370 generally solving a problem with a computer, 00:43:54.370 --> 00:43:56.630 we'll ultimately express ourselves in fundamentally 00:43:56.630 --> 00:43:59.380 the same way, with functions, conditions, and Boolean expressions, 00:43:59.380 --> 00:44:01.660 and loops, and many other constructs still, 00:44:01.660 --> 00:44:05.290 but we'll do it in a way that's methodical, we'll do it in a way 00:44:05.290 --> 00:44:07.090 wherein we've all agreed how to represent 00:44:07.090 --> 00:44:10.180 the inputs to that process and the outputs thereto, 00:44:10.180 --> 00:44:14.800 and ultimately use that representation and these layers of abstraction 00:44:14.800 --> 00:44:17.600 in order to solve our problems. 00:44:17.600 --> 00:44:21.460 But sometimes too much abstraction is not always a good thing. 00:44:21.460 --> 00:44:23.980 Sometimes it's both necessary and quite helpful 00:44:23.980 --> 00:44:28.570 to get into the weeds of the lower level implementation details, so to speak. 00:44:28.570 --> 00:44:30.580 And let's see if we can't see this together. 00:44:30.580 --> 00:44:34.540 Take out if you could a pen or pencil, as well as a sheet of paper, 00:44:34.540 --> 00:44:37.540 and in just a moment allow me to program you, if you will. 00:44:37.540 --> 00:44:40.270 I'll use a bit of verbal pseudocode to program 00:44:40.270 --> 00:44:43.420 you to draw a particular picture on that sheet of paper. 00:44:43.420 --> 00:44:46.600 The onus is on me to choose an appropriate level of abstraction 00:44:46.600 --> 00:44:48.950 so that you're on the same page, if you will, 00:44:48.950 --> 00:44:53.620 as I, so that ultimately what I program is what you implement correctly. 00:44:53.620 --> 00:44:54.150 Let's try. 00:44:56.910 --> 00:44:57.850 All right. 00:44:57.850 --> 00:45:00.894 First, go ahead if you would and draw a square. 00:45:05.340 --> 00:45:06.620 All right. 00:45:06.620 --> 00:45:10.325 And next to that square to the right, go ahead if you could and draw a circle. 00:45:14.700 --> 00:45:19.880 To the right of that circle, go ahead and draw a diagonal line 00:45:19.880 --> 00:45:22.010 from bottom left to top right. 00:45:26.090 --> 00:45:29.210 All right, and lastly, go ahead if you would 00:45:29.210 --> 00:45:33.390 and draw a triangle to the right of that line. 00:45:33.390 --> 00:45:33.890 All right. 00:45:33.890 --> 00:45:36.200 Now hopefully you're quite proud of what you just drew, 00:45:36.200 --> 00:45:39.680 and it's perfectly correct as you followed my instructions step-by-step. 00:45:39.680 --> 00:45:44.030 So surely what you drew looks like this? 00:45:44.030 --> 00:45:48.560 Well that's a square, to a circle to the right, a straight line from bottom 00:45:48.560 --> 00:45:52.200 left to top right, to the right of which is a triangle. 00:45:52.200 --> 00:45:55.550 Now with some probability, you probably didn't draw quite this. 00:45:55.550 --> 00:45:59.420 Fortunately there's no one there to see, but where might you have gone wrong 00:45:59.420 --> 00:46:01.940 or maybe where might I have gone wrong? 00:46:01.940 --> 00:46:05.990 Well I didn't exactly specify just how big that square should be, let alone 00:46:05.990 --> 00:46:07.640 where it should be on the page. 00:46:07.640 --> 00:46:10.970 And you might have quite reasonably drawn it right in the center-- 00:46:10.970 --> 00:46:12.950 maybe the top left or the top right. 00:46:12.950 --> 00:46:15.110 But if you drew in a place that I didn't intend, 00:46:15.110 --> 00:46:18.170 you might not have had enough room for that actual square 00:46:18.170 --> 00:46:20.862 unless you flipped perhaps the paper around. 00:46:20.862 --> 00:46:22.820 As for the circle, I said draw it to the right, 00:46:22.820 --> 00:46:26.330 but I didn't technically say that it should be just as wide or just as high 00:46:26.330 --> 00:46:29.570 as that square, so there might have been a disparity there. 00:46:29.570 --> 00:46:32.900 As for that straight line, I said from bottom left to top right. 00:46:32.900 --> 00:46:35.450 I knew that I meant from the bottom of the circle 00:46:35.450 --> 00:46:37.940 to the top right of what would then be the triangle, 00:46:37.940 --> 00:46:41.870 but maybe you started from here and all the way up to here. 00:46:41.870 --> 00:46:44.570 I was making an assumption, and that, perhaps, 00:46:44.570 --> 00:46:46.790 was not necessarily precise enough. 00:46:46.790 --> 00:46:48.530 And then lastly, the triangle. 00:46:48.530 --> 00:46:50.840 Pretty sure that I learned growing up that there's 00:46:50.840 --> 00:46:52.310 all sorts of different triangles. 00:46:52.310 --> 00:46:55.640 Some have right angles, some have acute angles or obtuse angles, 00:46:55.640 --> 00:46:57.740 or some triangles or even isosceles. 00:46:57.740 --> 00:47:01.190 Now I happen to intend this one and you might have drawn just that, 00:47:01.190 --> 00:47:04.070 but if you did, you probably got a bit lucky. 00:47:04.070 --> 00:47:06.290 And unfortunately when it comes to computing, 00:47:06.290 --> 00:47:09.200 you don't want to just get lucky when programming your computer, 00:47:09.200 --> 00:47:13.020 you want to actually ensure that what you write is what it does. 00:47:13.020 --> 00:47:15.410 And in fact, if you've ever seen on your Mac or PC 00:47:15.410 --> 00:47:18.620 a spinning beach ball or hourglass indicating 00:47:18.620 --> 00:47:22.190 that something is taking quite long, or the computer freezes or reboots, 00:47:22.190 --> 00:47:25.490 odds are that's because some programmer, now like myself, 00:47:25.490 --> 00:47:28.760 might not have been specific enough to the computer 00:47:28.760 --> 00:47:32.940 as to what to do in all circumstances, and so sometimes unforeseen behavior 00:47:32.940 --> 00:47:33.440 happens. 00:47:33.440 --> 00:47:35.750 The computer starts thinking forever. 00:47:35.750 --> 00:47:38.510 The computer reboots or crashes or freezes, 00:47:38.510 --> 00:47:41.420 which is simply the result of one or more lines of code-- 00:47:41.420 --> 00:47:44.990 not in pseudocode, but in Java or C++ or something else-- 00:47:44.990 --> 00:47:49.970 not having anticipated some user's input or some particular direction. 00:47:49.970 --> 00:47:52.460 So maybe it would help to operate not quite 00:47:52.460 --> 00:47:54.980 at this high of a level of abstraction. 00:47:54.980 --> 00:47:57.350 And indeed, all of these shapes are abstractions. 00:47:57.350 --> 00:48:01.040 A square, a circle, a line, and a triangle are abstractions in the sense 00:48:01.040 --> 00:48:05.900 that we've ascribed words to them that have some semantic meaning to us, 00:48:05.900 --> 00:48:07.520 but what really is a square? 00:48:07.520 --> 00:48:09.350 Well again, if we go back to grade school, 00:48:09.350 --> 00:48:13.340 a square is a rectangle, all of whose sides are of equal length 00:48:13.340 --> 00:48:15.810 and whose angles are all right angles. 00:48:15.810 --> 00:48:17.857 But very quickly, my own eyes start to glaze over 00:48:17.857 --> 00:48:20.690 when you get into the weeds of that implementation, and so all of us 00:48:20.690 --> 00:48:23.900 have agreed since to just call it a square. 00:48:23.900 --> 00:48:26.260 And same for circle and line and triangle, 00:48:26.260 --> 00:48:28.440 but even then, there are variations. 00:48:28.440 --> 00:48:30.770 So let's get a bit more into the weeds this time 00:48:30.770 --> 00:48:34.070 and let me take an approach with the second of two pictures, 00:48:34.070 --> 00:48:37.385 programming you this time at a much lower level of detail. 00:48:40.740 --> 00:48:43.800 Go ahead and take out another sheet of paper or flip over the one 00:48:43.800 --> 00:48:45.570 that you already have. 00:48:45.570 --> 00:48:50.580 Toward the top middle of that sheet of paper, roughly one inch from the top, 00:48:50.580 --> 00:48:55.560 go ahead and put down the tip of your pen or pencil. 00:48:55.560 --> 00:48:59.010 Keeping your pen or pencil applied to the paper, 00:48:59.010 --> 00:49:02.400 start to draw from the top middle of the paper 00:49:02.400 --> 00:49:08.940 down toward the left at roughly a 45 degree angle for two or so inches 00:49:08.940 --> 00:49:10.800 and then stop. 00:49:10.800 --> 00:49:13.350 Keeping the tip of your pen or pencil on the paper, 00:49:13.350 --> 00:49:16.920 go ahead and draw another line perhaps three inches straight 00:49:16.920 --> 00:49:21.960 down toward the bottom of the paper, stopping two or so inches 00:49:21.960 --> 00:49:25.390 shy of the bottom of the paper. 00:49:25.390 --> 00:49:28.570 Then, if you would, hook a right, this time 00:49:28.570 --> 00:49:33.970 moving at a 45-degree angle toward the bottom-middle of the paper, 00:49:33.970 --> 00:49:40.850 stopping ultimately one or so inches from the bottom of the paper. 00:49:40.850 --> 00:49:46.550 Then bear right yet again, this time going up at a 45-degree angle 00:49:46.550 --> 00:49:51.890 upward toward the middle of the paper, this time extending a couple of inches, 00:49:51.890 --> 00:49:58.550 and then stopping at the same height your previous line started at. 00:49:58.550 --> 00:50:02.840 Now draw a vertical line about three inches high, 00:50:02.840 --> 00:50:09.140 stopping exactly where two lines ago started. 00:50:09.140 --> 00:50:13.290 And if you're on the same page, no pun intended, go ahead 00:50:13.290 --> 00:50:18.990 and hook a left this time, going back a 45-degree angle toward the top-middle 00:50:18.990 --> 00:50:23.730 of the page, hopefully closing the loop, if you will, 00:50:23.730 --> 00:50:30.330 and connecting your very first dot to the last place you stopped. 00:50:30.330 --> 00:50:34.140 At this point, you hopefully have a shape on your page 00:50:34.140 --> 00:50:37.260 that has six total sides. 00:50:37.260 --> 00:50:38.940 What comes next? 00:50:38.940 --> 00:50:44.670 Go ahead and from the top-middle of the page follow the line you already drew 00:50:44.670 --> 00:50:49.110 down to the left at a 45-degree angle and stop where you made a corner 00:50:49.110 --> 00:50:49.930 before-- 00:50:49.930 --> 00:50:52.460 before you went straight down on the page. 00:50:52.460 --> 00:50:55.380 And instead of following that vertical line, 00:50:55.380 --> 00:51:02.070 go ahead and go down 45 degrees to the right a couple of inches, 00:51:02.070 --> 00:51:07.440 stopping once you're directly below the top-middle of the dot you 00:51:07.440 --> 00:51:09.450 initially drew. 00:51:09.450 --> 00:51:13.140 Then go ahead and do two things from the point you're now at. 00:51:13.140 --> 00:51:18.390 Go ahead and draw the opposite line up and to the right at a 45-degree angle, 00:51:18.390 --> 00:51:23.260 connecting that line to one of the corners you previously made. 00:51:23.260 --> 00:51:28.000 And then from that same initial point, draw a vertical line 00:51:28.000 --> 00:51:33.910 down to the bottom-middle of the page where you had another angle still. 00:51:33.910 --> 00:51:38.080 Lift up your pen or pencil and take pride in what you've just drawn, 00:51:38.080 --> 00:51:41.830 because it is most surely exactly this. 00:51:41.830 --> 00:51:42.550 Was it? 00:51:42.550 --> 00:51:46.390 I don't know, because that was quite painful for me to say in this program 00:51:46.390 --> 00:51:48.910 because I was operating at such a low level 00:51:48.910 --> 00:51:53.890 really with no abstractions other than line and point and angle. 00:51:53.890 --> 00:51:59.260 I was instead directing you much like a paintbrush on a page to go up and down 00:51:59.260 --> 00:52:01.870 and left and right, collectively creating 00:52:01.870 --> 00:52:06.760 what will be an abstraction that I would dare say call a cube, but a cube 00:52:06.760 --> 00:52:08.920 that I did not name by name. 00:52:08.920 --> 00:52:12.070 Had I said draw a cube, frankly we learned from last time 00:52:12.070 --> 00:52:14.770 that that could have opened up multiple possibilities. 00:52:14.770 --> 00:52:15.920 What should the angles be? 00:52:15.920 --> 00:52:17.150 What should the size be? 00:52:17.150 --> 00:52:19.000 What should the rotation there of it be? 00:52:19.000 --> 00:52:21.490 And so an abstraction alone might not have been enough 00:52:21.490 --> 00:52:23.980 if I wanted you to draw precisely this cube. 00:52:23.980 --> 00:52:28.540 But if I do want you to be ever so correct and consistent with what 00:52:28.540 --> 00:52:31.210 I had in mind on the screen here, I really 00:52:31.210 --> 00:52:34.840 did need to go down to such a low level, so to speak, 00:52:34.840 --> 00:52:38.770 that I was talking in terms of edges' length and angles therein. 00:52:38.770 --> 00:52:40.870 And even then, I might not have been as clear 00:52:40.870 --> 00:52:43.690 as I might have been-- more precise measurements and angles 00:52:43.690 --> 00:52:46.450 and such might have been ideal so that you ultimately 00:52:46.450 --> 00:52:48.410 end up precisely with the same thing. 00:52:48.410 --> 00:52:52.060 So if you veered off-track, not a problem, my fault more so than yours. 00:52:52.060 --> 00:52:53.890 But what's the takeaway here? 00:52:53.890 --> 00:52:56.200 Well at some point it would be nice not to have 00:52:56.200 --> 00:53:00.850 to write programs at such a low level again and again and again. 00:53:00.850 --> 00:53:04.360 Wouldn't it be nice if just one of us, the best artist among us 00:53:04.360 --> 00:53:05.800 could implement code-- 00:53:05.800 --> 00:53:08.470 write code-- that implements a cube, that 00:53:08.470 --> 00:53:12.850 implements a square, a circle, a line, and a triangle? 00:53:12.850 --> 00:53:17.150 But when using those drawing functions, if you will, 00:53:17.150 --> 00:53:19.780 that someone else has implemented, you should probably 00:53:19.780 --> 00:53:22.540 get into the habit of asking me additional questions. 00:53:22.540 --> 00:53:23.710 You want a square. 00:53:23.710 --> 00:53:27.250 Well how long should each edge be and where should its position 00:53:27.250 --> 00:53:29.530 be on the page or the canvas? 00:53:29.530 --> 00:53:32.470 Same goes for circle or line or triangle-- 00:53:32.470 --> 00:53:35.820 what are the angles and lengths and positioning be? 00:53:35.820 --> 00:53:39.490 And if you can parametrize your functions in that way-- 00:53:39.490 --> 00:53:43.240 in other words, write your functions in such a way that they themselves 00:53:43.240 --> 00:53:48.070 take input so that what a function does is at the end of the day produce output 00:53:48.070 --> 00:53:52.160 subject to those inputs, we have then solved a problem. 00:53:52.160 --> 00:53:54.340 Not necessarily the one problem at hand, but we've 00:53:54.340 --> 00:53:56.080 solved other people's problems. 00:53:56.080 --> 00:53:59.860 And indeed, that's what the world of programming ultimately is-- 00:53:59.860 --> 00:54:02.680 writing code to solve problems, and ideally 00:54:02.680 --> 00:54:05.830 solving those problems once and only once. 00:54:05.830 --> 00:54:09.440 And whether it's internally within your firm or your company, 00:54:09.440 --> 00:54:12.252 writing code in such a way that other people-- maybe yourself 00:54:12.252 --> 00:54:15.460 and your colleagues can then use it-- or in the case of open source software, 00:54:15.460 --> 00:54:17.230 anyone in the world can use it. 00:54:17.230 --> 00:54:19.870 So that in an ideal world, only one of us humans 00:54:19.870 --> 00:54:25.030 ever need write code in some language to draw a circle or cube or square or line 00:54:25.030 --> 00:54:27.580 or triangle, and everyone else in the world 00:54:27.580 --> 00:54:30.610 can stand on his or her shoulders, use that code 00:54:30.610 --> 00:54:34.090 to build their tool or product on top it. 00:54:34.090 --> 00:54:35.980 This, then, was computational thinking. 00:54:35.980 --> 00:54:39.190 You have inputs, you want outputs, and in between, you have algorithms. 00:54:39.190 --> 00:54:42.950 You just first need to decide how to represent those inputs and outputs, 00:54:42.950 --> 00:54:47.640 and you have to decide for yourself at what level of abstractions to work.