CS50 Video Player
    • 🧁
      • 🍪
      • 🍊
      • 🍿
    • 0:00:00Introduction
    • 0:00:15Computational Thinking
    • 0:01:54Representation
    • 0:05:13Binary
    • 0:14:36Representing Letters
    • 0:16:37Unicode
    • 0:19:33Abstraction
    • 0:22:09RGB
    • 0:24:22Representing Images and Videos
    • 0:29:54Finding Mike Smith
    • 0:31:38Solving Problems Effectively
    • 0:40:59Pseudocode
    • 0:41:56Functions
    • 0:42:25Conditions
    • 0:42:40Boolean Expressions
    • 0:43:11Loops
    • 0:44:17Abstraction (continued)
    • 0:00:00[MUSIC PLAYING]
    • 0:00:17DAVID MALAN: So odds are you know someone who is or perhaps are
    • 0:00:20yourself a computer person.
    • 0:00:22But what does that mean?
    • 0:00:23Well I propose that a computer person is simply
    • 0:00:25someone who's really good at computational thinking.
    • 0:00:28Thinking methodically, or more formally, thinking algorithmically,
    • 0:00:32whereby you take inputs to some problem, you solve that problem
    • 0:00:35and produce output, but you do so step by step by step, along the way
    • 0:00:39defining any of the terms or ideas that you
    • 0:00:42need to use so that anyone else following along
    • 0:00:44can understand exactly what it is you're doing.
    • 0:00:46Computer science itself is really about computational thinking, then.
    • 0:00:50It's not about programming, with which it's
    • 0:00:51often conflated, although programming is a wonderfully useful tool with which
    • 0:00:55you can solve problems, but computer science itself
    • 0:00:58is about solving problems themselves.
    • 0:01:00And it can be in any number of domains, whether it's
    • 0:01:02software or hardware or artificial intelligence or machine learning
    • 0:01:05or data science or beyond.
    • 0:01:07That's the wonderful thing about computer science--
    • 0:01:09it's just so wonderfully applicable to other fields.
    • 0:01:11It's all about equipping you with a mental model,
    • 0:01:14so to speak, a set of concepts, as well as
    • 0:01:16some practical skills via which you can bring to bear solutions
    • 0:01:19to problems in other domains entirely.
    • 0:01:22Now what, though, does it mean to solve a problem?
    • 0:01:24I propose that we think about problem-solving quite simply as this.
    • 0:01:28If you've got some problem to be solved, you have an input.
    • 0:01:31And the goal is to solve that problem and come up with some solution, which
    • 0:01:34we'll call simply our output.
    • 0:01:36And in between those inputs and outputs hopefully
    • 0:01:38are the step-by-step instructions via which we can solve that problem.
    • 0:01:42Now how we're going to solve that problem we'll have to come back to.
    • 0:01:45For now we'll consider it to be the proverbial black box.
    • 0:01:48So we don't quite know or need to know right now just how it works,
    • 0:01:51but that it can work, and we'll come back to this soon.
    • 0:01:54But for now, we do need a way to represent these inputs,
    • 0:01:57and we do need a way to represent our outputs.
    • 0:02:00Right now I happen to be speaking English
    • 0:02:02and you happen to be hearing English, and so we've sort of
    • 0:02:04tacitly agreed that we'll represent our words using this particular language.
    • 0:02:08Now computers tend not to use English, they have their own system,
    • 0:02:12if you will, with what you might be familiar even if you don't quite
    • 0:02:14speak it yourself, and indeed, there are different ways
    • 0:02:17you can represent information.
    • 0:02:19For instance, let's consider the simplest of problems-- for instance,
    • 0:02:22counting the number of people in a room.
    • 0:02:24I could do this old-school.
    • 0:02:25I don't need computers or English, I can simply use my physical hand and say,
    • 0:02:29I'm starting with zero people and now I'll
    • 0:02:30count one, and then two, and then three, and then four, and then five,
    • 0:02:35and then--
    • 0:02:35I'm out of fingers, but I can at least employ my other hand, maybe
    • 0:02:38a couple of feet and get as high as 10, maybe even
    • 0:02:4020 using this physical system.
    • 0:02:42This is pretty equivalent, actually, to just keeping
    • 0:02:45score counting the old-school way with hash marks.
    • 0:02:47Right now we've not counted anything, but as soon
    • 0:02:49as I start drawing some lines, I might represent the number 1,
    • 0:02:53or 2 people in the room, or 3, or 4.
    • 0:02:56Or by convention I can draw a slash just to make super clear that this is now
    • 0:02:59representing 5, and then I can do another five of those
    • 0:03:01to count up the 10 and beyond.
    • 0:03:04Now these systems of hashes, as well as this system of counting on my fingers,
    • 0:03:07actually has a name.
    • 0:03:08That of unary notation.
    • 0:03:10Uno implying one, simply signifying that I only have one digit--
    • 0:03:14pun not intended-- via which I can count things.
    • 0:03:16This takes the form of my fingers on my hand or these hash marks on the screen.
    • 0:03:20But it doesn't get me very far, because of course
    • 0:03:22on my one hand with five fingers, I can only count up to five total.
    • 0:03:26And even on the board it feels pretty inefficient, because for every number
    • 0:03:29I want to count higher, I have to draw yet
    • 0:03:31another line on the screen, which just continue to accumulate.
    • 0:03:34But suppose we were a little more clever about this
    • 0:03:37and we thought about this problem from a different angle.
    • 0:03:40Maybe I could take into account not just the number of fingers
    • 0:03:43that I've raised, but the order in which I've raised them
    • 0:03:46or the pattern via which I've permuted them rather than just taking
    • 0:03:50into account how many of them are up.
    • 0:03:52If I take that approach, maybe I can actually count even higher than five
    • 0:03:56on just one hand before resorting to another hand or feet.
    • 0:03:59Now how could I do that?
    • 0:04:00Well instead of counting up 0 to 1 to 2 to 3 to 4
    • 0:04:05to 5, why do I instead start with some patterns instead?
    • 0:04:09So I'll still start with 0, I'll still start with 1, but now for 2,
    • 0:04:13I'm not just going to raise the second finger,
    • 0:04:15I'm instead going to go from 0 to 1 to 2,
    • 0:04:19putting down that first finger or thumb, simply representing 2
    • 0:04:22with this one finger.
    • 0:04:24And when I'm ready to represent the number 3,
    • 0:04:26I'll bring that finger back up.
    • 0:04:28And so using just two fingers now have I represented four possible values--
    • 0:04:320, 1, 2, and 3.
    • 0:04:36From 0 to 3, of course, is four total values,
    • 0:04:38and so I've counted as high as 3 now using not three fingers, but only two.
    • 0:04:43How, though, can I count higher than 3?
    • 0:04:46Well, I just need to raise an additional finger.
    • 0:04:48And so let's start at 0, to 1, to 2, to 3, to 4-- whoops--
    • 0:04:53to 5, to 6, and now to 7.
    • 0:04:56And if it didn't hurt so much, I could continue counting as high as 8 and 9
    • 0:05:00and 10 and beyond by simply permuting my fingers in different ways.
    • 0:05:05So how high can I now count on this one hand?
    • 0:05:07Using unary notation with fingers just up or down, I can count as high as 5--
    • 0:05:11from 0 to 5.
    • 0:05:13But with these same five fingers, if I instead use not unary,
    • 0:05:17but let's call it binary notation where we're actually
    • 0:05:19taking into account whether the fingers are up or down and the pattern thereof,
    • 0:05:24well now it would seem that each of these fingers
    • 0:05:26can be in one of two possible states or configurations.
    • 0:05:29They can either be up or they can be down, or just one of them can be up
    • 0:05:33or can be down, or just one other can be up or down.
    • 0:05:36So if there's two possible states or configurations for each of these five
    • 0:05:40fingers, that's like 2 times 2 times 2 times 2 times 2,
    • 0:05:44or 2 to the power of 5 for five fingers, which is actually 32 possible patterns.
    • 0:05:50Which is to say with my one human hand, now can I
    • 0:05:52count using not unary, but binary from 0 to 31, which is 32 possible values.
    • 0:05:59Now what's the goal at hand?
    • 0:06:00It's quite simply to represent information.
    • 0:06:02Because if we have inputs and outputs, we
    • 0:06:04need to decide a priori how we're going to represent those values.
    • 0:06:07Now it turns out in computers, binary is wonderfully well-suited.
    • 0:06:11Because after all, what's the one physical input to any computer
    • 0:06:14you have, whether it's your laptop or desktop or these days,
    • 0:06:17even a phone in your pocket?
    • 0:06:19Well odds are, at the end of the day-- or even perhaps earlier in the day--
    • 0:06:22you need to physically plug that device into the wall and actually recharge it.
    • 0:06:26And somehow or other there's electricity or electrons
    • 0:06:28flowing from the wall that are stored in the battery in your device
    • 0:06:31if it has a battery, and that is the input that drives your entire machine's
    • 0:06:36operation.
    • 0:06:37And so if that's the only possible input,
    • 0:06:39it's pretty straightforward to imagine that you might have your computer
    • 0:06:42plugged in or not, power is flowing or not,
    • 0:06:46you've got a charge in your battery or you don't.
    • 0:06:48And so this binary world where something can be in two possible states--
    • 0:06:53on or off, plugged in or not--
    • 0:06:56is wonderfully conducive to now using binary in the context of computers
    • 0:07:00to represent information.
    • 0:07:02After all, if I want to represent a number,
    • 0:07:04I might simply turn on the lights.
    • 0:07:06And so my phone here has a light built in, and right now that light is off,
    • 0:07:09but if I consider this then to be off, we'll call it a 0.
    • 0:07:13And if I turn this flashlight now on, I can be said to be representing a 1.
    • 0:07:17And so simply with a simple light bulb can I represent two possible values
    • 0:07:21just like my finger can be up and down.
    • 0:07:22But computers don't necessarily use lots of little light bulbs,
    • 0:07:25they use something else that's called a transistor.
    • 0:07:28A transistor is a tiny little switch, and that switch, of course,
    • 0:07:31can be either on or off-- letting electricity in or not.
    • 0:07:35And so when you have a computer, inside of which
    • 0:07:37is a motherboard and CPU and bunches of other pieces of hardware,
    • 0:07:40one of the underlying components ultimately
    • 0:07:42are these things called transistors.
    • 0:07:44And computers today have millions of them inside, each of which
    • 0:07:47can be on or off-- so far more than my five fingers,
    • 0:07:50and that's ultimately how a computer can go about representing information.
    • 0:07:54So long as it has access to some physical supply of electricity can
    • 0:07:58it use that electricity to turn these switches
    • 0:08:00on or off in distinct patterns, thereby representing 0, 1, 2, 3, 4,
    • 0:08:05all the way up to 31 or even millions or billions or beyond.
    • 0:08:09And so computers use binary.
    • 0:08:11Computers speak binary-- only 0's and 1's or off and on,
    • 0:08:16because it's so wonderfully well-conducive to the physical world
    • 0:08:19on which they're ultimately based.
    • 0:08:21We humans, meanwhile, tend to communicate
    • 0:08:23not only in English and other spoken languages,
    • 0:08:25but in a numeric system called decimal.
    • 0:08:28So decimal, dec meaning 10, has 10 digits at its disposal--
    • 0:08:310, 1, 2, 3, 4, 5, 6, 7, 8, 9, whereas binary has just two--
    • 0:08:360 and 1-- and unary, you might say, has just one--
    • 0:08:391, the hash mark that I drew on the board.
    • 0:08:43But if I only have 0's and 1's at my disposal, how can
    • 0:08:46I possibly count to 2 or 3 or beyond?
    • 0:08:49Well, we need some way of mapping these 0's and 1's to the more familiar
    • 0:08:53numbers that we ourselves know.
    • 0:08:54So how can we go about doing this?
    • 0:08:56It's one thing to describe it in terms of patterns on your fingers,
    • 0:08:59but again, a device just has switches that it can turn on and off.
    • 0:09:02Well it turns out even if you don't yet speak binary
    • 0:09:05or have never really thought about doing so,
    • 0:09:07turns out that it's not all that dissimilar to the system of numbers
    • 0:09:10with which we grew up.
    • 0:09:12In fact, in grade school, you and I probably
    • 0:09:14grew up learning how to represent numbers in rather the same way.
    • 0:09:17For instance, consider this--
    • 0:09:18clearly the number 123.
    • 0:09:21But why is that?
    • 0:09:22It's not inherently the number 123.
    • 0:09:24Really, this is just three symbols on the screen.
    • 0:09:27We of course immediately recognize them as 1 and 2 and 3,
    • 0:09:31and we infer from that, oh, this is the number 123, but why is that exactly?
    • 0:09:35Well if you're like me, you probably grew up
    • 0:09:37representing numbers in the following way,
    • 0:09:39even if it's been quite some time since you thought about it like this.
    • 0:09:42With the symbol here, 1, 2, and 3, if you're like me,
    • 0:09:46you probably grew up thinking of this rightmost digit
    • 0:09:48as being in the ones place, and this middle digit
    • 0:09:50is being in the tens place, and this leftmost digit
    • 0:09:53as being in the one hundredths place.
    • 0:09:55And if it were a longer number, you'd have
    • 0:09:56the one thousandths place and ten thousandths place and beyond.
    • 0:09:59Now how do we get from 1, 2, 3 to 123?
    • 0:10:02Well, the arithmetic we were taught says to do 100 times 1, and then 10 times
    • 0:10:092, and then 1 times 3, and then add all three of those products
    • 0:10:14together, giving us, of course, 100 plus 20 plus 3, which of course is 123.
    • 0:10:21Now that actually doesn't feel like much progress, because we started at 123
    • 0:10:25and we got to 123, but that's not quite that.
    • 0:10:27We actually started with the pattern of symbols--
    • 0:10:301, 2, 3, like a pattern of fingers, and ultimately ascribe mathematical meaning
    • 0:10:34to those symbols as 123.
    • 0:10:37And it turns out computers, even though they speak binary and therefore only
    • 0:10:40have 0's and 1's at their disposal-- no 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9,
    • 0:10:46they count in exactly the same way, and they represent inputs and outputs
    • 0:10:50in fundamentally the same way.
    • 0:10:52Consider this.
    • 0:10:53Suppose that I have 3 bits at my disposal, 3 switches or light bulbs,
    • 0:10:57if you will.
    • 0:10:58And those light bulbs or switches are all initially off.
    • 0:11:01I claim that I'll represent those states as 0, 0, 0.
    • 0:11:05And together, those three 0's represent the decimal number we ourselves know
    • 0:11:08is 0.
    • 0:11:09Now why is that?
    • 0:11:10Well, if here if we consider this to be the ones place as before,
    • 0:11:14but the middle digit we won't consider being in the tens place,
    • 0:11:16we're going to consider this as being in the twos place,
    • 0:11:19and this leftmost digit as being in the fours place.
    • 0:11:22Now why?
    • 0:11:23Well in our decimal system, there's a reason
    • 0:11:25that we have the ones place, the tens place, the hundredths place,
    • 0:11:28and beyond--
    • 0:11:29those are actually all powers of 10.
    • 0:11:3110 to the 0, 10 to the 1, 10 to the 2, and beyond.
    • 0:11:35Now in binary, bi meaning two, you only have two digits at your disposal, 0
    • 0:11:39and 1, and so instead of using powers of 10, we're going to use powers of 2.
    • 0:11:43And indeed we have.
    • 0:11:442 to the 0 is 1; 2 to the 1 is 2, 2 to the 2 is 4, and if we kept going,
    • 0:11:50we'd get 8, 16, 32, 64, and beyond.
    • 0:11:54And so this pattern of symbols or this pattern of light bulbs
    • 0:11:57or this pattern of switches, all of which I'm proposing are off,
    • 0:12:00simply represents now the number we humans know as 0.
    • 0:12:03Why?
    • 0:12:04Well we have 4 times 0 plus 2 times 0 plus 1 times 0,
    • 0:12:10which of course gives me 0 plus 0 plus 0, for a total numeric value of 0.
    • 0:12:17So in binary, 0, 0, 0 or all three switches off represents 0,
    • 0:12:21and indeed, that's what we would expect.
    • 0:12:23But we've instead we did this.
    • 0:12:25Suppose that using binary, and therefore these same three places--
    • 0:12:28ones place, twos place, and fours place and beyond,
    • 0:12:31we had a different pattern of symbols.
    • 0:12:33How, for instance, might we represent 1?
    • 0:12:35Well, if we had a pattern that's 0, 0, and 1 in binary, that's
    • 0:12:40going to translate, of course, to the decimal number we all know and agree
    • 0:12:43is the number 1.
    • 0:12:44How do I represent the number 2?
    • 0:12:46Well, if I start from scratch again, I'm going
    • 0:12:48to represent the decimal number we know as 2 as a pattern that's 0, 1, and 0.
    • 0:12:54A switch that's off, another that's on, another that's off.
    • 0:12:57Why?
    • 0:12:574 times 0 is 0, 2 times 1 is 2, 1 times 0 is 0,
    • 0:13:03and so we're left with total of 2.
    • 0:13:05And if we want to represent 3, I don't even
    • 0:13:06need to change the value or state of those switches,
    • 0:13:09I can simply turn this one from off to on,
    • 0:13:12and now I'm representing the number 3.
    • 0:13:14If I want to count up to 4, I can simply start fresh in the fours place,
    • 0:13:18in the twos place, in the ones place here--
    • 0:13:201, 0, and 0.
    • 0:13:22And then lastly, suppose that I want to count up even higher.
    • 0:13:257 can simply be 1, 1, and 1, because that gives me a 4, a 2, and a 1.
    • 0:13:314 plus 2 is 6, plus 1 is 7.
    • 0:13:34But what if I want to represent the number 8?
    • 0:13:36To represent the number 8, it would seem that I need a little more space.
    • 0:13:40And so I might need to introduce the eights place so that I
    • 0:13:44can have a 1, a 0, a 0, and a 0, eighth place being 2 to the 3, but to do this,
    • 0:13:50I do indeed need more hardware.
    • 0:13:52I need another switch, another light bulb, and another physical device
    • 0:13:55inside of my computer.
    • 0:13:56Now fortunately, our computers today have millions of these tiny transistors
    • 0:14:00and switches, so it's not all that problematic to count as high as 8,
    • 0:14:03but the implication is, that in order to represent larger and larger values,
    • 0:14:07do we need more physical storage?
    • 0:14:09And indeed, thematic and computer science is exactly that constraint.
    • 0:14:12You can only do so much computationally, perhaps,
    • 0:14:15if you have a finite amount of memory or a finite amount of hardware
    • 0:14:20or switches.
    • 0:14:20And we'll see, then, that there is non-trivial implications for how
    • 0:14:23much data you can represent, and how many problems, therefore,
    • 0:14:27you can solve.
    • 0:14:28So that's it for numbers.
    • 0:14:29Using just 0's and 1's can we count as high as we want and represent
    • 0:14:33any number of values so long as we have enough bits at our disposal.
    • 0:14:36But numbers only get us so far in computing.
    • 0:14:38After all, it's not just Excel and calculators
    • 0:14:41with which we use computers.
    • 0:14:42It's of course to send information textually,
    • 0:14:44and to use letters of the alphabet, and compose text messages and emails
    • 0:14:48and documents and more, but how, then, do you represent letters
    • 0:14:52if all you have at the end of the day are these 0's and 1's
    • 0:14:54underneath the hood, so to speak?
    • 0:14:56Well to do that, we all simply need to agree,
    • 0:14:59just like we've agreed to speak in here English for now,
    • 0:15:02on a particular system by which to represent letters of the alphabet.
    • 0:15:06Now we don't have all that many choices at hand because if we only have
    • 0:15:090's and 1's-- switches that can be turned on and off--
    • 0:15:12that doesn't give us terribly many options.
    • 0:15:14But what we could do as humans is just collectively agree that you know what?
    • 0:15:18We are going to use a certain pattern of 0's and 1's to represent capital A.
    • 0:15:22And we're going to use a different pattern of 0's and 1's to represent
    • 0:15:25capital B. A different pattern of 0's and 1's
    • 0:15:27to represent C and D and all the way through Z. And you know what?
    • 0:15:30If we care about lowercase letters, we'll
    • 0:15:32use slightly different patterns of 0's and 1's to represent those as well.
    • 0:15:37And this is exactly what humans did decades ago.
    • 0:15:39We standardized on something called ASCII--
    • 0:15:41the American Standard Code for Information Interchange,
    • 0:15:44which was the result of people agreeing that we are going to use--
    • 0:15:48you know what?
    • 0:15:49The number 65 in decimal to represent capital A,
    • 0:15:52and the number 66 to represent capital B,
    • 0:15:56and the number 97 to represent lowercase a,
    • 0:15:59and 98 to represent lowercase b, and everything before and beyond.
    • 0:16:04And so this system, this code, ASCII, is simply a collective agreement
    • 0:16:08that whenever you're in the context of a text-based program and not
    • 0:16:11a numeric-based program, any patterns of bits,
    • 0:16:14such as those that might represent 65 in a calculator,
    • 0:16:18should instead be interpreted in the context of Microsoft Word
    • 0:16:22or an SMS message or iMessage as actually representing a letter.
    • 0:16:26So how bits are interpreted is entirely context-dependent.
    • 0:16:29Depending on the program you have opened, the same pattern of bits
    • 0:16:32might be interpreted in different ways--
    • 0:16:34as numbers or letters or even something else.
    • 0:16:37So how, then, do we represent so many other symbols
    • 0:16:42that aren't just A through Z?
    • 0:16:44Well it turns out that the American Standard
    • 0:16:46Code for Information Interchange was indeed
    • 0:16:48fairly skewed toward American representation of letters,
    • 0:16:51particularly English.
    • 0:16:52But there are so many more characters with accents and other symbology, let
    • 0:16:56alone punctuation marks, and in foreign languages,
    • 0:16:58too, are there hundreds if not thousands of distinct characters
    • 0:17:02that you need to represent ideally in order to send that text
    • 0:17:05and write that document.
    • 0:17:06But ASCII alone couldn't handle it.
    • 0:17:08Because ASCII tended to use 7 or maybe in some contexts 8 bits total,
    • 0:17:12and with 8 bits--
    • 0:17:14or binary digits, if you will--
    • 0:17:16can you represent how many possible values--
    • 0:17:182 times 2 times 2 times 2 times 2 times 2 times 2 times
    • 0:17:222 for 8 possible bits, each of which can be a 0 or 1.
    • 0:17:25That only gives you 256 possible letters.
    • 0:17:28Now that's more than enough for 26 letters of the English alphabet, A
    • 0:17:32through Z, both uppercase and lowercase, but once you
    • 0:17:35start adding in punctuation and accents and other characters,
    • 0:17:38you very quickly run out.
    • 0:17:39And so the world produced Unicode instead,
    • 0:17:42which doesn't just use 8 bits or 1 byte, if you will--
    • 0:17:451 byte simply meaning quite simply a bit,
    • 0:17:47but instead introduced a variable length encoding of letters.
    • 0:17:51And so some letters might use 8 bits or 1 byte.
    • 0:17:54Other letters might use 2 bytes or 16 bits.
    • 0:17:57Other letters might use 3 bytes or even 4.
    • 0:18:00And via 4 possible bytes maximally--
    • 0:18:032 to the 32 bits-- can you actually represent 4 billion possible values,
    • 0:18:07which is a huge number of values.
    • 0:18:08But how does the system of encoding actually work?
    • 0:18:11Let's consider by way of an example.
    • 0:18:13In both ASCII and Unicode, ASCII now being
    • 0:18:15a subset of Unicode insofar as it only uses 1 byte per letter,
    • 0:18:19you might represent A with--
    • 0:18:21capital A with 65, capital B with 66, and so forth.
    • 0:18:25And dot-dot-dot implies we've handled the rest as well and they all happen
    • 0:18:28to be back-to-back-to-back.
    • 0:18:29So suppose in the context of a text message
    • 0:18:32you happen to receive a pattern of 0's and 1's that if you actually
    • 0:18:36did the math in the ones place and the twos place
    • 0:18:38and so forth, actually worked out to be the decimal number 72, 73, 33.
    • 0:18:45Well what text message have you just received?
    • 0:18:47Of course at the end of the day, computers only understand binary,
    • 0:18:50and that information is sent from phone to phone
    • 0:18:53over the internet-- more on that another time.
    • 0:18:56But those 0's and 1's interpreted in the context of a text messaging program
    • 0:19:00will be interpreted not as binary, not as decimal,
    • 0:19:03but probably as ASCII or more generally Unicode.
    • 0:19:06And so if you've received a text message that says, 72, 73, 33, well what might
    • 0:19:11that spell?
    • 0:19:12Well if we consider our excerpt of a chart here,
    • 0:19:14that's 72 and 73, of course, translates to H and an I,
    • 0:19:18and you wouldn't know it from that preceding chart, but 33 it turns out--
    • 0:19:21just represents a very excited exclamation point,
    • 0:19:24because that, too, has a representation in ASCII and Unicode.
    • 0:19:28Now underneath the hood are patterns of 0's and 1's, but we don't need
    • 0:19:31to think about things at that level.
    • 0:19:33Indeed, what we've done here by introducing ASCII,
    • 0:19:35and in turn, Unicode, is introduce what's
    • 0:19:37called an abstraction, which is a technique in computer science via which
    • 0:19:41we can think about a problem more usefully at a higher level as opposed
    • 0:19:45to the lowest level in which it's actually implemented.
    • 0:19:48After all, it'd be much easier to receive a message that you view
    • 0:19:51as H-I-!
    • 0:19:53than actually as a pattern of 0's and 1's that you then
    • 0:19:55have to think about and translate in your head
    • 0:19:58to the actual message that was intended.
    • 0:20:00So an abstraction is just a way of taking a fairly low level if not very
    • 0:20:03complicated representation and thinking about it
    • 0:20:06in a higher, more useful level that lends itself
    • 0:20:08more readily to communication, or more generally to problem-solving.
    • 0:20:12Now what about all of those other characters on the screen?
    • 0:20:15After all, on a typical board might you have
    • 0:20:17letters and numbers and punctuation, but also these accented characters, too.
    • 0:20:20Well thanks to Unicode, you indeed have as many as 4 billion possibilities,
    • 0:20:24and it's no surprise, perhaps, that proliferating on the internet
    • 0:20:28these days are a little friendly faces called emojis
    • 0:20:32that you might have received yourself in text messages, emails,
    • 0:20:35or some other form.
    • 0:20:36Now these emojis here, though they might look like smiley faces,
    • 0:20:40are actually characters that companies like Google and Microsoft and Apple
    • 0:20:44have simply decided to represent pictorially.
    • 0:20:47Underneath the hood, anytime you receive one of these emojis,
    • 0:20:50you're actually receiving a pattern of bits--
    • 0:20:520's and 1's that in the context of an email or text
    • 0:20:56message or some other program, are being interpreted as
    • 0:20:59and therefore displayed as a corresponding picture
    • 0:21:02that Google and Microsoft and Apple and others
    • 0:21:04have decided how to present visually.
    • 0:21:06And indeed, different platforms present these same patterns of 0's and 1's
    • 0:21:10differently depending on how the artist at those companies
    • 0:21:13have decided to draw these emoji.
    • 0:21:15Consider this one, for instance-- face with tears of joy is its formal name,
    • 0:21:20but more technically, this is encoded by a very specific decimal number.
    • 0:21:25Capital A is a 65, capital B is 66, what is this face with tears of joy?
    • 0:21:32Well it is the number 128,514.
    • 0:21:36After all, if you've got four billion possibilities,
    • 0:21:38surely we could use something within that range
    • 0:21:40to represent this face and any number of others.
    • 0:21:42But underneath the hood, if you actually looked
    • 0:21:44at a text message in which you received a face with tears of joy,
    • 0:21:48what you've actually received is this pattern of 0's and 1's somehow encoded
    • 0:21:52on your phone or your computer.
    • 0:21:55And so in the context of a calculator or Microsoft Excel
    • 0:21:58might we interpret some pattern of bits as numbers.
    • 0:22:01And in the context of a text messaging program
    • 0:22:03or Google Docs or Microsoft Word might we
    • 0:22:05interpret that same pattern of bits as instead characters or even emoji.
    • 0:22:09But what if we want to represent different types of media altogether?
    • 0:22:13After all, the world of computing is not composed of just numbers and letters.
    • 0:22:17There's also colors and images and videos and audio files and more,
    • 0:22:22but at the end of the day, if we only have at our disposal
    • 0:22:240's and 1's, how do we go about representing all of those richer media?
    • 0:22:29Well as before, we humans just need to agree collectively
    • 0:22:32to represent those media using 0's and 1's in some standard way.
    • 0:22:37Perhaps one of the most familiar acronyms, even if you've never
    • 0:22:40really thought about what it is that you might see on a computer, is this one--
    • 0:22:43RGB.
    • 0:22:44It stands for red, green, and blue.
    • 0:22:46And this refers to the process by which many computers represent
    • 0:22:50colors on the screen.
    • 0:22:51In fact, what is a color?
    • 0:22:52Well, you might represent the color black and white simply by a single bit.
    • 0:22:571 might represent black and 0 might represent white, or vice versa.
    • 0:23:02We in that case only have what's called 1-bit color, whereby
    • 0:23:05the bit is either on or off implying black or white or white or black.
    • 0:23:10But with RGB, you actually use more bits than just one.
    • 0:23:13Conventionally you would use 8 bits to represent
    • 0:23:15red, 8 bits to represent green, and 8 bits to represent blue.
    • 0:23:19So 24 bits total, the first 8 of which or first byte is red, second is green,
    • 0:23:26third is blue.
    • 0:23:27Now what does that mean?
    • 0:23:28Well in order to represent a color, you simply
    • 0:23:30decide, how much red do you want to add to the mix?
    • 0:23:33How much green and how much blue?
    • 0:23:34Combining essentially those wavelengths of light
    • 0:23:38in order to see a disparate color on the screen.
    • 0:23:41And if you think about red, green, and blue now as being single bytes each,
    • 0:23:45that means you have a possible range of values of 0 to 255.
    • 0:23:50After all, if a single byte is 8 bits, and with 8 bits, each of which
    • 0:23:54can be a 0 or 1-- so 2 times 2 times 2 times 2 times 2 times 2 times 2 times
    • 0:23:592 gives you 256 values.
    • 0:24:01So if you start from 0, you can count as high as 255.
    • 0:24:05Suppose that you had 72 as your amount of red for a color, and 73 for green,
    • 0:24:11and 33 for blue.
    • 0:24:13That is to say in the context of a text messaging
    • 0:24:15program, this same pattern of bits--
    • 0:24:1672, 73, 33 presented as decimal represented a textural message of HI!.
    • 0:24:22But suppose you were to see that same pattern of bits
    • 0:24:24instead in a photo-editing program like Photoshop, or in the context of opening
    • 0:24:29an image on the screen.
    • 0:24:30Well that same pattern of bits, or in turn, decimal numbers, just
    • 0:24:34represents some amount of red, some amount of green,
    • 0:24:36and some amount of blue.
    • 0:24:38So 72 is a decent amount-- a medium amount
    • 0:24:41of red out of 255 total values, 73 is a medium amount of green,
    • 0:24:45and 33 is a little bit of blue.
    • 0:24:47If you combine now all of these three values in your mind's eye
    • 0:24:50by overlapping them, what you get is this shade of yellow.
    • 0:24:54Which is to say that if you wanted to represent
    • 0:24:56this particular shade of yellow would you
    • 0:24:58use three bytes whose values are respectively 72, 73, and 33.
    • 0:25:03And in the context of Photoshop or some other graphical program
    • 0:25:07would that pattern be interpreted as and displayed as this color on the screen.
    • 0:25:11Now this color is deliberately presented here as just 1 square--
    • 0:25:151 dot, if you will, or more properly, 1 pixel.
    • 0:25:18Because what is an image?
    • 0:25:19Well if you've ever looked really close on your computer screen
    • 0:25:22or on your phone or even on your TV, you might actually
    • 0:25:25see all of the thousands of dots that compose it.
    • 0:25:28This is getting harder to do on today's modern hardware,
    • 0:25:31because if you have something like a retina display,
    • 0:25:33that means these dots or pixels or ever so tiny and ever so close
    • 0:25:36together that it's actually hard now for the human eye to see them,
    • 0:25:39but they are in fact there.
    • 0:25:41Any image on the screen, any photo on the screen
    • 0:25:44is really just a pattern of dots or pixels--
    • 0:25:47a grid of dots from left to right, top to bottom.
    • 0:25:50And every one of those dots or pixels on the screen
    • 0:25:54probably has 24 bits representing its particular color.
    • 0:25:59Indeed, a picture is essentially just a pattern of color so small
    • 0:26:03that you don't really see all of those dots,
    • 0:26:05but you see the net effect of a beautiful photo or image or something
    • 0:26:08else altogether.
    • 0:26:10So consider how we might see these.
    • 0:26:13When Apple or Google or Microsoft or any other company that supports emojis
    • 0:26:17presents those emojis on the screen, we of course
    • 0:26:20see them as images because Apple and Microsoft and Google
    • 0:26:22have decided what images shall be displayed when
    • 0:26:26it receives a certain pattern of bits.
    • 0:26:28But how are they storing those images and how
    • 0:26:30is your Mac or PC or phone displaying that image to you?
    • 0:26:34Well it's hard to see where those bits are let alone the pixels in it
    • 0:26:38at this particular size, but if I go ahead and zoom in and zoom in and zoom
    • 0:26:43in a little more still, you can begin to see
    • 0:26:46the individual dots or squares or pixels that compose even this one emoji.
    • 0:26:51And so just to display this smiling face, this face with tears of joy,
    • 0:26:56do you need 24 bits for this pixel, 24 bits for this pixel,
    • 0:27:0024 bits for this pixel, 24 bits for this pixel, and so on and so forth?
    • 0:27:05So if you've ever noticed that when you download an image or download a photo
    • 0:27:08or receive one in the mail, odds are it's not in the order of bytes.
    • 0:27:12It's probably kilobytes for thousands of bytes,
    • 0:27:15or megabytes for millions of bytes.
    • 0:27:17How in the world does a simple photo have so many bytes or in turn bits?
    • 0:27:21It's because every one of the dots in that image
    • 0:27:23takes up some amount of space.
    • 0:27:25So to represent yellow might we use a certain pattern of 0's and 1's or 3
    • 0:27:28bytes.
    • 0:27:29To represent black or gray or any other number--
    • 0:27:31colors on the screen might we represent those using different patterns still.
    • 0:27:36Now that's it for images, but what about videos?
    • 0:27:40A video is really just a sequence of images
    • 0:27:43being presented to you so quickly that you and your human eye
    • 0:27:46don't notice that you're really just watching image after image after image.
    • 0:27:49In fact, it's conventional in Hollywood and elsewhere
    • 0:27:52to display as many as 24 images or frames per second,
    • 0:27:55or perhaps even 30 frames or images per seconds.
    • 0:27:59And so even though they are in fact distinct images,
    • 0:28:02you are seeing them so quickly, and the characters on the screen
    • 0:28:05are moving within each frame or image ever
    • 0:28:08so slightly, that it creates ultimately the illusion of movement.
    • 0:28:12And if you think back to childhood, you might
    • 0:28:13have had one of those old-school flip books
    • 0:28:15on which was drawn some kind of cartoon one frame or image at a time.
    • 0:28:19And if you flipped through that flip book one page
    • 0:28:21ever so quickly again and again and again and again,
    • 0:28:24letting the physics of it all take its toll,
    • 0:28:27you might see a character or the picture in the book actually appearing to move,
    • 0:28:31but it's not.
    • 0:28:32All of those pages are just images and all of those images are not moving,
    • 0:28:35but when you see them so fast and so quickly in succession
    • 0:28:38does it appear to create that same movement.
    • 0:28:40So these things here, Animojis in Apple's world,
    • 0:28:43are just videos ultimately that track your facial movements and such,
    • 0:28:47but all they really are are a pattern of bits, each set of which
    • 0:28:51represents an image.
    • 0:28:52And each of those images is displayed to you on your phone
    • 0:28:55so quickly that you see the illusion of movement.
    • 0:28:58And so here again is an abstraction.
    • 0:29:00What is a video?
    • 0:29:01Well, a video is a collection of images.
    • 0:29:03Well what's an image?
    • 0:29:04An image is a collection of pixels.
    • 0:29:06Well what's a pixel?
    • 0:29:07A pixel is simply some number of bits representing some amount of red
    • 0:29:10and green and blue.
    • 0:29:11Well what is a bit?
    • 0:29:12It's simply a representation digitally of something being present,
    • 0:29:16like electricity or not.
    • 0:29:18And so it's much more powerful now to be operating
    • 0:29:20at this level of abstraction-- talking about videos for what they are, and not
    • 0:29:24getting into the weeds of the lowest level that at the end of the day,
    • 0:29:27it's really just some form of electricity
    • 0:29:29that we call bits, that we in turn call pixels,
    • 0:29:32that we in turn called images, that we in turn call videos.
    • 0:29:35And we can operate in a number of these layers of abstraction
    • 0:29:38in order to represent inputs to some problem.
    • 0:29:41To create a film, to convert a film, to display a film
    • 0:29:44might be just one of the problems to solve.
    • 0:29:48All right, so we now have a way to represent information,
    • 0:29:50whether it's binary, decimal, or some other approach altogether.
    • 0:29:53So it's time to solve problems.
    • 0:29:54But how do we go about solving problems?
    • 0:29:57What is inside of this black box?
    • 0:29:59Well that's where our so-called algorithms
    • 0:30:01are-- step-by-step instructions for solving some problem.
    • 0:30:04And to solve these problems, we simply need
    • 0:30:06to decide first what problem to solve.
    • 0:30:08Well let's consider a familiar one, like that of looking up someone's name
    • 0:30:11and number in a phone book.
    • 0:30:13Now these days, the phone book, of course, takes a more digital form,
    • 0:30:16but at the end of the day, these two formats are pretty equivalent.
    • 0:30:18After all, here in my hand is a phone book with maybe 1,000 pages,
    • 0:30:22on which are bunches of names and numbers sorted alphabetically
    • 0:30:25from A to Z.
    • 0:30:26On my phone, meanwhile, while I might have to click an icon instead,
    • 0:30:29do I have contacts that are similarly sorted
    • 0:30:31from A to Z by first name or last name, and touching any one of them
    • 0:30:34pulls up its number.
    • 0:30:36So this one, though, is a little more physical for us
    • 0:30:38to see the solution to a problem, like finding, say, Mike Smith.
    • 0:30:43Mike Smith may or may not be in this phone book, but if he is,
    • 0:30:45my goal quite simply is to find him.
    • 0:30:47So let me try this.
    • 0:30:49Let me try opening this book, and then one step
    • 0:30:51at a time looking down for Mike Smith.
    • 0:30:53And if I don't see him, move on to the next page.
    • 0:30:56If I still don't see him, move on to the next page, and next page,
    • 0:30:59and next page, and so forth, one page at a time.
    • 0:31:02I propose that we consider first-- is this algorithm correct?
    • 0:31:06Opening the phone book, looking down, turning page, and repeating.
    • 0:31:11Well, at some point, if Mike is in this phone book,
    • 0:31:13I am going to reach him, at which point I can call him.
    • 0:31:16And if Mike Smith is not in this phone book,
    • 0:31:17I'm eventually not going to reach him, but I
    • 0:31:19am going to hit the end of the phone book, at which point
    • 0:31:21I'll presumably stop.
    • 0:31:23But it doesn't feel terribly efficient, however correct it may be.
    • 0:31:27Why is it not efficient?
    • 0:31:28Well I'm starting at the beginning of the phone book.
    • 0:31:30I know it's alphabetical, and yet I'm turning one page
    • 0:31:32at a time through the A's, through the B's, through the C's and beyond,
    • 0:31:35just waiting and waiting until I finally reach Mike Smith.
    • 0:31:38Well how might I do this better?
    • 0:31:39Well, I learned in grade school not only how
    • 0:31:41to count by ones, but also an account by twos.
    • 0:31:43So instead of 1 page, 2 page, 3 page, 4, why don't instead do 2,
    • 0:31:484, 6, 8, 10, 12-- flying through the phone book.
    • 0:31:52It certainly sounds faster, and it is, but is that approach correct?
    • 0:31:56Well, I propose that there could be a problem.
    • 0:31:59I might just get unlucky, and once I do reach the S section of the phone book,
    • 0:32:03what if by bad luck Mike Smith is sandwiched between two of those pages?
    • 0:32:07And therefore I hit the T section and Z section and run out of pages?
    • 0:32:11I might conclude incorrectly that Mike Smith is not,
    • 0:32:13in fact, in this phone book.
    • 0:32:15But do I have to throw out the algorithm altogether?
    • 0:32:17Probably not, right?
    • 0:32:19I could be a little clever here and improve this algorithm,
    • 0:32:21maintaining its efficiency, but fixing its correctness.
    • 0:32:25After all, if I do see a page on which there are last names starting with T,
    • 0:32:29while I can stop and say, well we know Mike is not farther than this
    • 0:32:32because Smith starts with S, so I can double-back hopefully
    • 0:32:35just one page or few, and therefore fix what's
    • 0:32:39otherwise an incorrect approach in this algorithm.
    • 0:32:41In fact, I can be even smarter than that.
    • 0:32:43As soon as I see someone's name that starts with S-N instead of S-M,
    • 0:32:47I can similarly flip back one page and therefore ensure
    • 0:32:50that I can go twice as fast through most of the phone book,
    • 0:32:53and only once I hit that section do I have to double-back one or terribly few
    • 0:32:57pages.
    • 0:32:58So I get the overall performance gains, and I also solve the problem.
    • 0:33:02But honestly, if you even use this technology anymore,
    • 0:33:05odds are you don't start at the beginning turning one or two
    • 0:33:07pages at a time.
    • 0:33:08If you're like me, you probably more instinctively
    • 0:33:11open up roughly to say the middle.
    • 0:33:12You'll look down and you realize, oh, I haven't found Mike yet
    • 0:33:15because I'm actually here in the M section.
    • 0:33:17But what do you know about where you've just jumped?
    • 0:33:20Well Mike Smith is indeed to the right here,
    • 0:33:22because he's in the name starting with S. But if I'm in the M section,
    • 0:33:25I do know something else.
    • 0:33:27I know that Mike is not in the left-hand section of this book--
    • 0:33:30he is not among the A through M's.
    • 0:33:32And so I can both literally and figuratively tear this problem in half,
    • 0:33:37throw half of it away, thereby leaving myself with just,
    • 0:33:41say, 500 pages out of 1,000.
    • 0:33:43So whereas that first algorithm I took one byte at a time out of it--
    • 0:33:47one page at a time, the second algorithm I took two bytes at a time out of it--
    • 0:33:51two at a time.
    • 0:33:52Well with this algorithm, I just took 500 bytes out of the problem
    • 0:33:56all at once, thereby getting closer to the output to this problem
    • 0:34:00much more quickly.
    • 0:34:01What do I then do?
    • 0:34:02Well, I simply am probably going to apply that same algorithm again
    • 0:34:06and again and again-- dividing and conquering this phone book,
    • 0:34:09if you will.
    • 0:34:09Jumping roughly to the middle now, looking down-- dah, darn it!
    • 0:34:12I ended up in the T section now, so I've gone too far,
    • 0:34:15but I know Mike is not in the right-hand side of this book--
    • 0:34:17he's not among the T's through Z's.
    • 0:34:20So I can again tear the problem in half, throw that half away,
    • 0:34:23thereby leaving me with just a quarter of the original problem,
    • 0:34:27say 250 pages down, down from 1,000, finding Mike ever
    • 0:34:30so much more quickly than before.
    • 0:34:33And if I repeat and I repeat and I repeat, each time actually looking down
    • 0:34:37looking for Mike, I should hopefully find myself ultimately left
    • 0:34:40with just a single page on which Mike either is or is not, at which point
    • 0:34:45I can call him or quit.
    • 0:34:47So just how much more quickly did I find Mike Smith via this algorithm
    • 0:34:52than the first two?
    • 0:34:53Well in a 1,000-page phone book, I might get unlucky and Mike's not even there,
    • 0:34:56and so in the worst case, I might look in as many as 1,000 pages.
    • 0:35:01In the second algorithm, I might also get unlucky and not ever find Mike
    • 0:35:04because he's just not there, and therefore look at as many 500 pages.
    • 0:35:08But in this third algorithm where I'm iteratively
    • 0:35:11dividing and conquering again and again, splitting the problem in half
    • 0:35:15so I go from a very large input to a much smaller to an even smaller problem
    • 0:35:19still again and again, how many times might I split that phone in half?
    • 0:35:23Well if I start off with roughly 1,000 pages and I split it in half,
    • 0:35:27that gives me 500, 250, 125, and so forth.
    • 0:35:32Turns out that I can split 1,000 pages roughly 10 times in total
    • 0:35:36before I'm left with just that final page.
    • 0:35:38And so consider the implications of that.
    • 0:35:40First algorithm-- 1,000 steps, maybe.
    • 0:35:42Second algorithm-- 500 steps, maybe.
    • 0:35:45Third algorithm-- 10 steps, maybe, to find Mike Smith before I can call
    • 0:35:50or decide he's not there.
    • 0:35:52And that's a pretty powerful technique.
    • 0:35:53And if we extrapolate from this relatively small example or phone book
    • 0:35:57to maybe a much larger phone book, say a phone book
    • 0:35:59that a bit nonsensically has 4 billion pages in it, well,
    • 0:36:03how many steps might those three algorithms take?
    • 0:36:05The first algorithm might take 4 billion.
    • 0:36:08The second algorithm might take 2 billion.
    • 0:36:10The third algorithm might take 4 billion divided
    • 0:36:13by 2 divided by 2 divided by 2--
    • 0:36:16you can divide 4 billion and half roughly 32 times only, at which point
    • 0:36:21you're left with just that one page.
    • 0:36:23So 4 billion steps for the first algorithm, 2 billion
    • 0:36:26steps for the second algorithm, but 32 steps for the third algorithm.
    • 0:36:31And simply by harnessing this intuition that we all probably already have
    • 0:36:35in formalizing it in more methodical form-- in algorithmic form,
    • 0:36:39if you will, can we solve problems using some of the building
    • 0:36:42blocks that we already have at our disposal.
    • 0:36:45And indeed, problem-solving in computer science
    • 0:36:47is all about implementing these algorithms
    • 0:36:49and applying them to problems of interest to you.
    • 0:36:53But how do we think about just how good this algorithm is?
    • 0:36:56It sort of stands to reason that it has to be minimally correct.
    • 0:37:00But how efficient is it?
    • 0:37:01I've been talking in terms of absolute numbers.
    • 0:37:041,000, 500, or 10, or 4 billion, 2 billion, and 32.
    • 0:37:08But it would be nice to compare algorithms in a more general way
    • 0:37:12so that I can use the same searching algorithm, if you will,
    • 0:37:15to find not Mike Smith, but someone else.
    • 0:37:17Or to search not a phone book, but Google or search engine more generally.
    • 0:37:21And so computer scientists also have a more formal technique
    • 0:37:24via which to describe the efficiency of algorithms.
    • 0:37:27And we might consider these not even with numbers or formulas, per se,
    • 0:37:31but with simple visual representations thereof.
    • 0:37:34Here, for instance, is a simple plot.
    • 0:37:35On the x or horizontal axis is going to be the size of the problem.
    • 0:37:39How many pages are in the phone book, which we'll generally call n,
    • 0:37:42where n is a number for a computer scientist.
    • 0:37:44Much like a mathematician might go with x or y
    • 0:37:46or z, computer scientists might tend to start counting with n.
    • 0:37:50On the vertical or y-axis here, we'll say
    • 0:37:51this is going to be the time to solve a problem,
    • 0:37:53be it a phone book or something else.
    • 0:37:56And that might be seconds or minutes or page turns
    • 0:37:58or some other quantifiable unit of measure.
    • 0:38:02So how do I go about describing that first algorithm where
    • 0:38:06I turn one page at a time?
    • 0:38:08Well I propose that it manifests a linear relationship, or n, or a line,
    • 0:38:13a straight line on the chart.
    • 0:38:14Why is it a straight line?
    • 0:38:16Well, if Verizon or the local phone company, for instance,
    • 0:38:18next year adds just one more page to that phone book, that means for me,
    • 0:38:22it might take me one more unit of measure of time
    • 0:38:25to find someone like Mike Smith, because we've gone from 1,000 to 1001 pages.
    • 0:38:29So the slope of this line indeed can be straight or linear.
    • 0:38:33That second algorithm now where I'm flying through the phone book
    • 0:38:36twice as fast is really fundamentally the same algorithm or same shape.
    • 0:38:40It just so happens that for a given size of the problem,
    • 0:38:44it's not going to take this many seconds n,
    • 0:38:46it's going to take me n over 2 seconds because I'm
    • 0:38:49doing twice as much work at a time.
    • 0:38:51And so this line, too, is linear or straight,
    • 0:38:54but we might describe it in terms of n over 2, where n is the number of pages
    • 0:38:58but I only have to look at half of them except for maybe that very last one
    • 0:39:01if I double-back, and so its shape is fundamentally the same.
    • 0:39:05So better, but not fundamentally better, it would seem.
    • 0:39:08But that third and final algorithm has a fundamentally disparate shape,
    • 0:39:13depicted here with our green curved line which has a logarithmic slope to it.
    • 0:39:18So if n is the number of pages, and the algorithm in use
    • 0:39:21is division and conquering, it turns out that has a logarithmic slope.
    • 0:39:25Now what does that actually mean?
    • 0:39:27Well it turns out that if Verizon adds one more page to the phone book
    • 0:39:31next year, that is a drop in the bucket for that final algorithm where
    • 0:39:34I'm just tearing the problem in half.
    • 0:39:36But more powerfully, if Verizon doesn't just add one page,
    • 0:39:40perhaps to neighboring towns merged together and form one massive phone
    • 0:39:43book next year, going from 1,000 pages to 2,000 pages
    • 0:39:47all in one big, fat book, well how many more
    • 0:39:49steps does it take that third algorithm to search for anyone in it?
    • 0:39:53Just one.
    • 0:39:54Because with 2,000 pages, you can take 1,000-page byte out of that problem all
    • 0:39:58in one fell swoop even though it's twice as big as before.
    • 0:40:02And so even as the size of the problem gets bigger and bigger and bigger
    • 0:40:07and even farther away, the amount of time
    • 0:40:09it takes to solve a problem using that algorithm only
    • 0:40:12increases ever so slightly.
    • 0:40:15That's not a one-to-one or a one-to-two ratio,
    • 0:40:18it's instead said to be logarithmic.
    • 0:40:20And this, then, is a fundamentally different curve--
    • 0:40:23it's a fundamentally better algorithm in that the problem can grow exponentially
    • 0:40:27large, and the amount of time it takes to solve it itself
    • 0:40:31grows far less quickly than that.
    • 0:40:38Now it's one thing to talk about all these algorithms.
    • 0:40:40At some point we need to put them to paper,
    • 0:40:42or more technically, program them into a computer.
    • 0:40:45So how do we go about formalizing these step-by-step instructions in such a way
    • 0:40:50that all of us can agree that they are correct, all of us
    • 0:40:53can discuss their efficiency, and most importantly, all of us
    • 0:40:56can program a device to execute these steps for us?
    • 0:40:59Well let me propose that we first implement
    • 0:41:02an algorithm like that of searching a phone book in what's called pseudocode.
    • 0:41:05Pseudocode is not a formal programming language, it has no one definition.
    • 0:41:09It generally means using short, succinct phrases, often in English,
    • 0:41:12to describe your algorithm step-by-step-by-step in such a way that
    • 0:41:16you yourself understand it, and anyone reading it can also understand it.
    • 0:41:20Now along the way do you have to make certain assumptions,
    • 0:41:23because you need to decide at what layer of abstraction to actually operate.
    • 0:41:27And we'll take a look at where the opportunities there
    • 0:41:29are, but let me propose that we implement
    • 0:41:31this algorithm for searching for Mike Smith,
    • 0:41:33for instance, in the following way.
    • 0:41:36Now this is an algorithm, or really, a program, albeit written in pseudocode.
    • 0:41:40And even though written in pseudocode or English, it
    • 0:41:43manifests certain constructs that we're actually
    • 0:41:45going to see in any number of today's popular programming languages,
    • 0:41:49a programming language being an English-like language
    • 0:41:52that humans have decided can be used in a certain way
    • 0:41:54to tell a computer what to do.
    • 0:41:56Now this pseudocode is just for us humans,
    • 0:41:59but what are some of the fundamental constructs
    • 0:42:01in it that we'll see in actual programming languages?
    • 0:42:04Well first highlighted in yellow here are
    • 0:42:06all of the verbs or actions that more technically we'll call functions.
    • 0:42:10Statements that tell the computer, or in this case, human what to do.
    • 0:42:14Pickup, open to, look at, call, open or open, or quit-- all of them
    • 0:42:19calls to actions.
    • 0:42:20In the context of a computer with these same types of verbs,
    • 0:42:23we more traditionally call it functions.
    • 0:42:25What else is laying inside of this program?
    • 0:42:28Well these pictured here in yellow.
    • 0:42:29If, else if, else if, else, well these represent
    • 0:42:33what are called conditions or branches.
    • 0:42:35Forks in the road, so to speak, via which
    • 0:42:37you make a decision to go this way or this way or this way or that.
    • 0:42:41But how do you decide down which road to go?
    • 0:42:44You need what are called Boolean expressions.
    • 0:42:46Named after mathematician Boole, these Boolean expressions
    • 0:42:49are short phrases that either have yes or no answers,
    • 0:42:52or true or false answers, or if you will, 1 or 0-- on or off answers.
    • 0:42:58Smith is among names, Smith is earlier in book.
    • 0:43:01Smith is later in book-- each of them could be asked effectively
    • 0:43:04with a question mark to which the answer is
    • 0:43:06yes or no, and based on that answer can you
    • 0:43:08go down any one of those four roads.
    • 0:43:11And then lastly is this--
    • 0:43:13go back to step 2 or go back to step 2.
    • 0:43:16Highlighted in yellow here's an example of a loop, a deliberate
    • 0:43:19cycle that gets you to do something again and again
    • 0:43:23and again until some condition is no longer true
    • 0:43:27and you eventually quit or call Mike instead.
    • 0:43:30And so looping in a program allows you to write less code,
    • 0:43:33but do something again and again and again just
    • 0:43:35by referring back to some work that you've already done.
    • 0:43:39Now these constructs, though we've seen them in the context of pseudocode
    • 0:43:42and searching a phone book, can be found in any number of languages
    • 0:43:46and programs, be it Python or C++ or Java.
    • 0:43:49And so when it comes to programming a computer, or more
    • 0:43:52generally solving a problem with a computer,
    • 0:43:54we'll ultimately express ourselves in fundamentally
    • 0:43:56the same way, with functions, conditions, and Boolean expressions,
    • 0:43:59and loops, and many other constructs still,
    • 0:44:01but we'll do it in a way that's methodical, we'll do it in a way
    • 0:44:05wherein we've all agreed how to represent
    • 0:44:07the inputs to that process and the outputs thereto,
    • 0:44:10and ultimately use that representation and these layers of abstraction
    • 0:44:14in order to solve our problems.
    • 0:44:17But sometimes too much abstraction is not always a good thing.
    • 0:44:21Sometimes it's both necessary and quite helpful
    • 0:44:23to get into the weeds of the lower level implementation details, so to speak.
    • 0:44:28And let's see if we can't see this together.
    • 0:44:30Take out if you could a pen or pencil, as well as a sheet of paper,
    • 0:44:34and in just a moment allow me to program you, if you will.
    • 0:44:37I'll use a bit of verbal pseudocode to program
    • 0:44:40you to draw a particular picture on that sheet of paper.
    • 0:44:43The onus is on me to choose an appropriate level of abstraction
    • 0:44:46so that you're on the same page, if you will,
    • 0:44:48as I, so that ultimately what I program is what you implement correctly.
    • 0:44:53Let's try.
    • 0:44:56All right.
    • 0:44:57First, go ahead if you would and draw a square.
    • 0:45:05All right.
    • 0:45:06And next to that square to the right, go ahead if you could and draw a circle.
    • 0:45:14To the right of that circle, go ahead and draw a diagonal line
    • 0:45:19from bottom left to top right.
    • 0:45:26All right, and lastly, go ahead if you would
    • 0:45:29and draw a triangle to the right of that line.
    • 0:45:33All right.
    • 0:45:33Now hopefully you're quite proud of what you just drew,
    • 0:45:36and it's perfectly correct as you followed my instructions step-by-step.
    • 0:45:39So surely what you drew looks like this?
    • 0:45:44Well that's a square, to a circle to the right, a straight line from bottom
    • 0:45:48left to top right, to the right of which is a triangle.
    • 0:45:52Now with some probability, you probably didn't draw quite this.
    • 0:45:55Fortunately there's no one there to see, but where might you have gone wrong
    • 0:45:59or maybe where might I have gone wrong?
    • 0:46:01Well I didn't exactly specify just how big that square should be, let alone
    • 0:46:05where it should be on the page.
    • 0:46:07And you might have quite reasonably drawn it right in the center--
    • 0:46:10maybe the top left or the top right.
    • 0:46:12But if you drew in a place that I didn't intend,
    • 0:46:15you might not have had enough room for that actual square
    • 0:46:18unless you flipped perhaps the paper around.
    • 0:46:20As for the circle, I said draw it to the right,
    • 0:46:22but I didn't technically say that it should be just as wide or just as high
    • 0:46:26as that square, so there might have been a disparity there.
    • 0:46:29As for that straight line, I said from bottom left to top right.
    • 0:46:32I knew that I meant from the bottom of the circle
    • 0:46:35to the top right of what would then be the triangle,
    • 0:46:37but maybe you started from here and all the way up to here.
    • 0:46:41I was making an assumption, and that, perhaps,
    • 0:46:44was not necessarily precise enough.
    • 0:46:46And then lastly, the triangle.
    • 0:46:48Pretty sure that I learned growing up that there's
    • 0:46:50all sorts of different triangles.
    • 0:46:52Some have right angles, some have acute angles or obtuse angles,
    • 0:46:55or some triangles or even isosceles.
    • 0:46:57Now I happen to intend this one and you might have drawn just that,
    • 0:47:01but if you did, you probably got a bit lucky.
    • 0:47:04And unfortunately when it comes to computing,
    • 0:47:06you don't want to just get lucky when programming your computer,
    • 0:47:09you want to actually ensure that what you write is what it does.
    • 0:47:13And in fact, if you've ever seen on your Mac or PC
    • 0:47:15a spinning beach ball or hourglass indicating
    • 0:47:18that something is taking quite long, or the computer freezes or reboots,
    • 0:47:22odds are that's because some programmer, now like myself,
    • 0:47:25might not have been specific enough to the computer
    • 0:47:28as to what to do in all circumstances, and so sometimes unforeseen behavior
    • 0:47:32happens.
    • 0:47:33The computer starts thinking forever.
    • 0:47:35The computer reboots or crashes or freezes,
    • 0:47:38which is simply the result of one or more lines of code--
    • 0:47:41not in pseudocode, but in Java or C++ or something else--
    • 0:47:44not having anticipated some user's input or some particular direction.
    • 0:47:49So maybe it would help to operate not quite
    • 0:47:52at this high of a level of abstraction.
    • 0:47:54And indeed, all of these shapes are abstractions.
    • 0:47:57A square, a circle, a line, and a triangle are abstractions in the sense
    • 0:48:01that we've ascribed words to them that have some semantic meaning to us,
    • 0:48:05but what really is a square?
    • 0:48:07Well again, if we go back to grade school,
    • 0:48:09a square is a rectangle, all of whose sides are of equal length
    • 0:48:13and whose angles are all right angles.
    • 0:48:15But very quickly, my own eyes start to glaze over
    • 0:48:17when you get into the weeds of that implementation, and so all of us
    • 0:48:20have agreed since to just call it a square.
    • 0:48:23And same for circle and line and triangle,
    • 0:48:26but even then, there are variations.
    • 0:48:28So let's get a bit more into the weeds this time
    • 0:48:30and let me take an approach with the second of two pictures,
    • 0:48:34programming you this time at a much lower level of detail.
    • 0:48:40Go ahead and take out another sheet of paper or flip over the one
    • 0:48:43that you already have.
    • 0:48:45Toward the top middle of that sheet of paper, roughly one inch from the top,
    • 0:48:50go ahead and put down the tip of your pen or pencil.
    • 0:48:55Keeping your pen or pencil applied to the paper,
    • 0:48:59start to draw from the top middle of the paper
    • 0:49:02down toward the left at roughly a 45 degree angle for two or so inches
    • 0:49:08and then stop.
    • 0:49:10Keeping the tip of your pen or pencil on the paper,
    • 0:49:13go ahead and draw another line perhaps three inches straight
    • 0:49:16down toward the bottom of the paper, stopping two or so inches
    • 0:49:21shy of the bottom of the paper.
    • 0:49:25Then, if you would, hook a right, this time
    • 0:49:28moving at a 45-degree angle toward the bottom-middle of the paper,
    • 0:49:33stopping ultimately one or so inches from the bottom of the paper.
    • 0:49:40Then bear right yet again, this time going up at a 45-degree angle
    • 0:49:46upward toward the middle of the paper, this time extending a couple of inches,
    • 0:49:51and then stopping at the same height your previous line started at.
    • 0:49:58Now draw a vertical line about three inches high,
    • 0:50:02stopping exactly where two lines ago started.
    • 0:50:09And if you're on the same page, no pun intended, go ahead
    • 0:50:13and hook a left this time, going back a 45-degree angle toward the top-middle
    • 0:50:18of the page, hopefully closing the loop, if you will,
    • 0:50:23and connecting your very first dot to the last place you stopped.
    • 0:50:30At this point, you hopefully have a shape on your page
    • 0:50:34that has six total sides.
    • 0:50:37What comes next?
    • 0:50:38Go ahead and from the top-middle of the page follow the line you already drew
    • 0:50:44down to the left at a 45-degree angle and stop where you made a corner
    • 0:50:49before--
    • 0:50:49before you went straight down on the page.
    • 0:50:52And instead of following that vertical line,
    • 0:50:55go ahead and go down 45 degrees to the right a couple of inches,
    • 0:51:02stopping once you're directly below the top-middle of the dot you
    • 0:51:07initially drew.
    • 0:51:09Then go ahead and do two things from the point you're now at.
    • 0:51:13Go ahead and draw the opposite line up and to the right at a 45-degree angle,
    • 0:51:18connecting that line to one of the corners you previously made.
    • 0:51:23And then from that same initial point, draw a vertical line
    • 0:51:28down to the bottom-middle of the page where you had another angle still.
    • 0:51:33Lift up your pen or pencil and take pride in what you've just drawn,
    • 0:51:38because it is most surely exactly this.
    • 0:51:41Was it?
    • 0:51:42I don't know, because that was quite painful for me to say in this program
    • 0:51:46because I was operating at such a low level
    • 0:51:48really with no abstractions other than line and point and angle.
    • 0:51:53I was instead directing you much like a paintbrush on a page to go up and down
    • 0:51:59and left and right, collectively creating
    • 0:52:01what will be an abstraction that I would dare say call a cube, but a cube
    • 0:52:06that I did not name by name.
    • 0:52:08Had I said draw a cube, frankly we learned from last time
    • 0:52:12that that could have opened up multiple possibilities.
    • 0:52:14What should the angles be?
    • 0:52:15What should the size be?
    • 0:52:17What should the rotation there of it be?
    • 0:52:19And so an abstraction alone might not have been enough
    • 0:52:21if I wanted you to draw precisely this cube.
    • 0:52:23But if I do want you to be ever so correct and consistent with what
    • 0:52:28I had in mind on the screen here, I really
    • 0:52:31did need to go down to such a low level, so to speak,
    • 0:52:34that I was talking in terms of edges' length and angles therein.
    • 0:52:38And even then, I might not have been as clear
    • 0:52:40as I might have been-- more precise measurements and angles
    • 0:52:43and such might have been ideal so that you ultimately
    • 0:52:46end up precisely with the same thing.
    • 0:52:48So if you veered off-track, not a problem, my fault more so than yours.
    • 0:52:52But what's the takeaway here?
    • 0:52:53Well at some point it would be nice not to have
    • 0:52:56to write programs at such a low level again and again and again.
    • 0:53:00Wouldn't it be nice if just one of us, the best artist among us
    • 0:53:04could implement code--
    • 0:53:05write code-- that implements a cube, that
    • 0:53:08implements a square, a circle, a line, and a triangle?
    • 0:53:12But when using those drawing functions, if you will,
    • 0:53:17that someone else has implemented, you should probably
    • 0:53:19get into the habit of asking me additional questions.
    • 0:53:22You want a square.
    • 0:53:23Well how long should each edge be and where should its position
    • 0:53:27be on the page or the canvas?
    • 0:53:29Same goes for circle or line or triangle--
    • 0:53:32what are the angles and lengths and positioning be?
    • 0:53:35And if you can parametrize your functions in that way--
    • 0:53:39in other words, write your functions in such a way that they themselves
    • 0:53:43take input so that what a function does is at the end of the day produce output
    • 0:53:48subject to those inputs, we have then solved a problem.
    • 0:53:52Not necessarily the one problem at hand, but we've
    • 0:53:54solved other people's problems.
    • 0:53:56And indeed, that's what the world of programming ultimately is--
    • 0:53:59writing code to solve problems, and ideally
    • 0:54:02solving those problems once and only once.
    • 0:54:05And whether it's internally within your firm or your company,
    • 0:54:09writing code in such a way that other people-- maybe yourself
    • 0:54:12and your colleagues can then use it-- or in the case of open source software,
    • 0:54:15anyone in the world can use it.
    • 0:54:17So that in an ideal world, only one of us humans
    • 0:54:19ever need write code in some language to draw a circle or cube or square or line
    • 0:54:25or triangle, and everyone else in the world
    • 0:54:27can stand on his or her shoulders, use that code
    • 0:54:30to build their tool or product on top it.
    • 0:54:34This, then, was computational thinking.
    • 0:54:35You have inputs, you want outputs, and in between, you have algorithms.
    • 0:54:39You just first need to decide how to represent those inputs and outputs,
    • 0:54:42and you have to decide for yourself at what level of abstractions to work.
  • CS50.ai
Shortcuts
Before using a shortcut, click at least once on the video itself (to give it "focus") after closing this window.
Play/Pause spacebar or k
Rewind 10 seconds left arrow or j
Fast forward 10 seconds right arrow or l
Previous frame (while paused) ,
Next frame (while paused) .
Decrease playback rate <
Increase playback rate >
Toggle captions on/off c
Toggle mute m
Toggle full screen f or double-click video