[MUSIC PLAYING] DAVID J. MALAN: So odds are you

use a computer most every day, but you might not necessarily think

of yourself as a computer person. Something goes wrong, you don’t

necessarily know how to fix it. And if you actually want to solve

some problem using technology, the whole world of

technology, and computing, and algorithms and all of that

might seem all quite foreign. So much so that you can’t

necessarily feel like you’re making an informed decision. Well, that’s just because the

technology that we all use around us is kind of working at this level. Whereby there’s so many

people who have come before us that have invented this

level, and this level, and this level, and this level. And so what we’ll do here is try

to start from that ground level up. And indeed, at the base of all

computing, do we really have, as we’ll see, just zeros and ones? And that’s probably something you

know, at least, generally speaking. But it turns out once you

go have zeros and ones, can you very quickly go to text? Can you go to graphics? Can you go to videos? Can you go to spreadsheets? Can you go to so much more? But again, that’s the

world we now inhabit. But let’s now build

ourselves up to that point, so that you actually begin

to look around yourselves and realize, oh, I understand

now, what’s going on. And to do that, let’s consider this,

computational thinking, which really refers to thinking computationally. Thinking more methodically,

thinking more carefully, and somehow framing all problems in

the world as a sequence of steps. And those steps are quite simply,

input comes in, and output goes out. And what’s in between

those inputs and outputs we’ll eventually describe as

something called algorithms, but for now, let’s just consider

it to be this black box. We don’t know, we don’t care

what’s going on inside there. All that we care is that we get

back a correct output or a solution to a problem. But how do we go about representing

those inputs and outputs? If our problem at hand is to analyze

a whole bunch of financial data, a whole bunch of numbers

in a spreadsheet, how can we actually sum

all of those numbers together, or perform some other

arithmetic calculation on them? If we instead have a really big

document, a contract of some sort. And we want to make sure that

it is properly spellchecked? Well, the input there

isn’t numbers, but is all of the words and

letters in that document. And the output, we hope,

is a document without all of those little red squigglies. We want a correctly spelled document. So those are just some of the problems

that you might experience most any day, but underneath the hood, there’s

quite a bit of complexity going on. But that complexity,

it turns out, is just the result of layering, pretty

simple ideas, one on top of another. But in order to get to that

point in the discussion, we need to somehow represent these

inputs, these numbers, these letters, whatever it is that we have at hand. And to do that, we’re

going to use binary. Now odds are you’ve probably heard

that computers indeed only speak or understand zeros and ones. But how can that possibly be, when they

can do so much today, whether they’re on our desktops, or laptops or even

our mobile phones in our pockets, if all you have at the end

of the day is zeros and ones? How could you possibly count to two, let

alone three, or four, or four billion, let alone representing any

number of other types of media that computers today understand? Well, odds are you

recognize in this word here, this prefix, bi, bi meaning two,

and indeed that hints at the fact that you only have two letters

in your alphabet, so to speak. Two digits, zero and one. Now we humans have typically

grown up using the decimal system, dec meaning 10. And of course we have 0,1, 2,3,

4,5, 6, 7, 8, 9, 10 possible digits that we can permute and arrange

to count even higher than that. But with just zeros and ones, how do

you get to two, how do you get to three? Well, you’re thinking still in base

10, so to speak, base 10 being decimal. But we want to think now in

base 2, so to speak, binary, where we have just two of these inputs. And let me propose

that if you’re like me, you probably grew up understanding

numbers as really just this pattern of symbols like this, where each

symbol was in a column of sorts, a placeholder, if you will. And this, if you recall, was generally

called the ones place, and then the tens place, and then

with the hundreds place. And so at the moment, what we

really just have on the screen is a pattern of symbols, a pattern

of digits, one, two, three. But why is this pattern of

symbols, one, two, three, the number you and I think

of immediately as 123? Well, that’s because by way of these

columns or places do we implicitly, in our own mind, quickly

do a bit of arithmetic? Of course, if we have one, two, three,

that’s really like 100 times 1 plus 10 times 2 plus 1 times 3, and

of course that gives us 123. So it turns out that the binary system

is actually fundamentally the same. So if you get decimal, if you’ve been

counting like that since grade school, you are good to go now with

binary, because in fact and arguably, binary is even

simpler, because you don’t even have to keep track of so many digits. In fact, if we consider

this pattern of symbols, this of course, in our

human world, would generally be immediately recognized by

us humans as the number zero. Of course, it’s a little

silly to have those left most zeros, those

leading zeros, so to speak, because they don’t really

add much mathematically. But that’s OK. You can put as many zeros to the

left of a number in our real world and it doesn’t really affect the value. Now instead of using one and 10 and

100, let me just use one, two, and four. Now why those values? Well before, 1, 10, 100, and again

a thousand, 10,000, 100,000, and so forth. Those are powers of 10, 10 to the

zero is 1, 10 to the one is 10, 10 to the two is 100, and so forth. So what pattern do you perhaps see here? These aren’t powers of 10

anymore, 1, 2, 4, an 8, 16, 32. Now you really hear the pattern? These are instead powers of two. Two to the zero is one, two to

the one is two, two to the two is four, and so forth. So that’s the only change. By using base 10, just

two digits, zero and one, can we still count using

the same arithmetic system. So for instance, this of course

is still the number zero, because we have zero fours,

and zero twos, and zero ones. But if we instead change

this pattern to 0 0 1, well what value does this now represent? In the world of decimal, this

would represent the number one. And that’s true in the world of binary,

because we have 4 times 0 plus 2 times 0 plus 1 times 1, which

of course is just 1. So how do we get to two? You might be inclined to just

change this zero to a one, but that would be incorrect. That’s like carrying

the one, but then not wrapping around on the rightmost digit. Rather, if we want to

represent the number two, we need to come up with a

pattern that represents that. So let me propose instead that we

don’t just change that zero to a one, but we also change that one to zero. Because now we have 4

times 0 plus 2 times 1 plus times 0 which of course

is the number we know as 2. And now you can perhaps

grok the pattern at hand. If we want to count up to

the number we know as three, let’s just change that

rightmost one to a one. So that’s four times 0 plus

2 times 1 plus 1 times 1. That of course is three. Four is perhaps jumping out at you now. We just change that zero to a one, and

then the other two digits to zeros. And now if we want to count up to

five, or to six, or to seven, or to– dang it, what’s supposed to come next? It would seem that in the binary

system, we can only count as high as– what, seven? And that’s a little strange, because

of course, we started at zero, we counted here up to seven, but surely

computers can count higher than that. And that’s fine, just

need another digit. Much like if we wanted to count from

999, in our human decimal world, up to a thousand, which has four digits. Similarly here, do we

need another digit? We need an eights place,

and so we could represent the number we know as eight

with one, zero, zero, zero. But the key here is that

we needed another digit. To put it more mechanically,

we needed more hardware. We needed another physical place,

at least in this depiction, to actually store that one. And now we begin already to hint at a

connection between this digital world of zeros and ones, and the hardware

world in which it’s typically incarnated. And by that, I mean, we

need to decide, ultimately, how and where to store

patterns like this. And you know the nice thing about

binary only having two values, is that that effectively,

means you have just two states. And you might think of these two

states as something being on, or something being off. And maybe we might think of something

being on as a one, and something being off as a zero. And so just with two states,

can we have these two extremes. And maybe it’s not on or off, maybe

it’s true, or false, or black, or white, or red, or blue. It doesn’t even matter what

we call the two states, the key is that we have two of them. And you know In the physical

world, the simplest thing I can think of to turn on and off,

is perhaps something like this. Just a light bulb. This here’s a little

desk lamp, and in fact, if I go ahead and clip

this on here, and let me plug this into an

electrical outlet so that I’m getting some additional input if

you will, electricity or electrons, this lamp right now I claim is

representing the number zero. It’s completely off, and I’m just going

to agree, to agree with you, that this shall represent zero. But you know what, if I want to

represent a one in the physical world, just going to turn it on. And so now we have something that’s

on, or true, we’ll call that a one. Zero, one. Of course, we’re not really

counting all that high just yet. If I want to count higher than

zero to one, to something higher, I’m going to need another light bulb. I’m going to need more hardware,

more memory, if you will, in the world of computers. So let’s actually now give

myself a second zero or one. Plug this thing in here. Give it some electricity as

well, which again, is really one of the few physical

resources we have in a computer, whether it’s coming from

a power cord or a battery. And so now, if I want to represent

the number zero, here we are. But I’m doing it really with zero zero. This now is going to be one, this now

is going to be two, and this, of course, is going to be three. And let’s not stop there. Why have two desk lamps when

you can have three desk lamps. If we instead make a little

more room for here, and we want to instead now count

not just as high as three. Let me go ahead and plug-in

this third and final desk lamp, and go ahead and turn this on. And of course, we instantly

go from three to– not quite instantly because

you have the hands– to the number four. And so forth. So what’s now the connection

between the digital and the sort of analog

world of light bulbs, and the physical world of computers? Well inside of a computer is a whole

bunch of tiny, tiny little bulbs, so to speak. In fact, you can think of what’s inside

of your computer is exactly this. So many little light bulbs

that are either on or off. And thanks to those little light bulbs,

can your computer represent numbers? Zero, one, two, three, four, as many– as high of a number as it wants so

long as it has enough little lights. Now of course I’m oversimplifying. It’s not actually lights that you

have inside of your computer, rather, you have just the switches. These switches being called in

the computing world transistors, as you may have heard. Indeed, one of the things that companies

like Intel are increasingly doing, is packing more and more transistors

into their CPUs, central processing units. The brains of computers. And with those additional transistors,

can they store even more values, or equivalently can

they count even higher? And so now, even though we

began the discussion down here with just zeros and

ones in the abstract, now we’ve made it a little

more physical, in so far as we can represent those zeros

and ones with something physical, drawing electricity to power

these kinds of light bulbs. Of course, we can now

miniaturize that and consider these light bulbs to really be, what

we’ll call in the computer world, transistors. But at the end of the

day, even though we have now a way of

representing information, the zeros and ones, even

though we have a way now of representing even bigger numbers

by using even more transistors inside of our computer, we’re still

talking only about numbers. And with my computer I want to

do more than just use something like Microsoft Excel. I want to do more than

just do math on my data. I want to actually store

things like letters, and words. Let alone, colors, and

images, and videos, and more. So we need to abstract higher. So again zeros and ones, we know

how to represent it, now let’s build on top of the zeros and

ones and start to represent something more interesting. Something more

alphabetical, if you will. And so this gives us ASCII,

the American Standard Code for Information

Interchange, or more modernly referred to as a superset of Unicode. Turns out, human some time

ago, decided on a mapping between letters and numbers. Somewhat arbitrarily,

but in a way that’s convenient when it comes to actually

programming, things like this. And this is to say that

humans time ago decided, you know what, we are going to represent

the letter A using the decimal number 65. Now what does that mean? Well, this means that if your computer

is to store the letter A, or the letter B, or the letter C, it simply

has to store ultimately the number 65, or 66, or 67. What does it mean to store

number like 65, 66, or 67? Well that just means to store some

pattern of bits, some pattern of bulbs as we did a moment ago, and turn

them on and off in such a way that you’re representing in binary,

the decimal number 65, 66, 67. So if you think about something like

Microsoft Word or Google documents, or any program in which you

type text, what you’re really doing by typing on the keyboard,

is sending some pattern of signals that’s telling the computer to store

not just the letter ABC per se, but really to store the

number 65 or 66 or 67, or really, to store the

pattern of zeros and ones that ultimately represent

those same values. So again, this spirit

of layering binary now becomes ASCII, or Unicode,

something higher still. And so with this can

we represent messages? For instance, if I wanted to represent

a message like this, a familiar message, there say, I might store

these three values. 72, 73, and 33. Now what is that? Well turns out if I look back at

this pattern here, where 65 is A, and in tens 72 is H, and 73 is I, well

what are we really representing here? It would seem we’re

representing the pattern H I, and then you wouldn’t

know this from that chart, but if you look at

another online reference you’ll see a 33 is an exclamation point. So now we have the word

Hi or the exclamation Hi. But that’s in the context of a text

editor, or word processor like word. Suppose, instead, you

were using not a text editor, but something like

Photoshop, or MS Paint, or some other graphical program. Well instead, you might have

that same pattern of numbers, or really bits at the end of

the day, but in this context, something like Photoshop,

these numbers are meant to be values between 0 and 255. Turns out, long story short, that

if you have eight zeros or ones, where zero or one, you

know what, let’s just start calling them by their formal

name bits for binary digits. If you have eight bits, you can

count from 0 all the way up to 255. And the quick math there

is 2 to the 8, means you have 256 possible

permutations of zeros and ones. So therefore, if you start counting at

zero you can count as high up as 255. And so in the context of a graphics

program, you can think of 72 in so far as it’s not quite halfway between zero

and 255, it’s a medium amount of red and a medium amount of green. Not too much blue. Where zero means none of this color,

and 255 means a lot of this color. So if you had a pattern of bits,

and in-turn numbers, stored inside of your computer for the

purposes of a graphics program, it’s really like telling the computer

give me a medium amount of red, give me a minimum amount of green

and just a little bit of blue, and combine those like paint,

or like frequencies of light., until you get the

summation of those, really, are the combination

really of those, which is this murky shade here of yellow. So again, using the

same patterns of bits, can we represent either letters

and words and paragraphs, or in another context all together,

could that same pattern of bits still represent numbers, but be

interpreted not as letters and words and paragraphs, but as colors. If you treat each trio of 8 bits

as representing some amount of red, some amount of green,

some amount of blue, otherwise known as, if you’ve heard

the term, RGB, for red, green, blue. So this principle of starting

simple, and gradually making things more and more

and more complicated, is really a principle of abstraction. Because at this point

in the story, when we’re talking about words and paragraphs

and essays and documents, or in another context we’re

talking about images, or maybe even movies and more, we no longer

really need to care about, or even need to know

about, or understand, what’s underneath the

hood those zeros and ones, because we’ve abstracted

away from that lower level. And this principle of

abstraction, layering idea on idea on idea on idea such

that you no longer need to worry about how the lower

level ideas are implemented is nice, because it allows

us humans to focus only on the problems we

really care about, which in theory are those top most problems. The ones that are immediately at hand,

that we’re building solutions to, on the shoulders of, computer

scientists, and engineers, and just colleagues that

have come before us. And we don’t have to

get lost in the weeds, so to speak, of the earlier complexity. And so this is a powerful

problem solving technique, and indeed it’s a principle that

we’ll see applied ultimately in the world of programming as well. Now let’s try something. Speaking of abstractions,

let me encourage you at this point to take out a piece

of paper if you have one there. And surely, if you don’t

have one right there, surely you could pause this

video and actually go dig one up. Grab a pencil too, or pen. Yeah, Ill wait. Now you could just pause this,

I can’t wait all that long. Let’s assume at this point in the

story you’ve got that piece of paper, and a pencil or a pen, and

let’s play a little game. I of course can’t really

see what you’re doing. But I’m going to hope that you

either do or don’t do what I do, because either way it

will be instructive. And I’m going to leverage

some abstractions here, for better or for worse. I want you to go ahead, and please

don’t be one of those people like me who’s just following along

pretending like all right, I have the piece of paper, I have the

pencil, this is what I would be doing. Actually do this. This will be kind of fun for one of

us in the end, if this works out. Go ahead now, on that piece of paper,

with your pen or pencil, and go ahead and just draw a circle. OK. All right. And below that circle draw a square. All set. All right, and below that

square draw a triangle. Now odds are, you know exactly what

I meant when I said draw a circle, and perhaps you did a

little something like this. Or a little more perfect

than my circle there. And then beneath that

I said draw a square. And you just intuitively

know what a square is, so you might have

drawn a square like this. And then the third thing I

said was draw a triangle. And so you might have drawn a

triangle that looks like this. But immediately, ant that looks

curiously like part of a jack-o-lantern now. But curiously, there’s

some ambiguity there. Right, a circle is kind of a circle,

but I didn’t specify the radius or diameter, so maybe yours is

bigger, maybe yours a smaller, maybe it’s over here on your paper,

maybe it’s over there on your paper. So already, these abstractions

are useful in that you immediately knew what to draw, but you didn’t

really know how to draw it. Similarly, this square, I don’t know

why I drew it a little smaller here, but it’s indeed smaller,

and it’s barely a square. But it’s meant to be a square. But there’s a gap between it and the

circle, but I didn’t really specify. So there, too, the

abstraction is valuable in that you immediately knew how to

draw a square, but not where to draw it. Or in what size to draw it. And lastly, the triangle,

perhaps the most, the juiciest opportunity

for ambiguity, I didn’t tell you how to

orient that triangle. Maybe you, instead, did

something a little different, where your triangle

wasn’t drawn like that, with the pointy part at the bottom. Maybe you, instead, did

something like this. Or maybe it was somewhere

else on the paper altogether. So now at this point in the story, you

could have followed my instructions exactly as I described, but

we could still somehow come up with different solutions. And in fact, if I can now spoil

what the actual task at hand was, this was the picture I was describing. This picture here has

a circle, below which is a square, below which is a triangle. But that leaves out some key details. And the curious thing here, is that

even though abstraction is a useful mechanism, once you start to move away

from those implementation details, if you will, you very quickly

realize that I don’t really know what you’re telling me to do, necessarily. And the challenge is, that computers,

as complicated or intimidating as they might seem to you, they’re

really not all that bright. Right. They can only do what they

are explicitly told to do. And so if you, the human,

or you eventually perhaps, the programmer, don’t

actually specify absolutely precisely what you want the computer– or the human in this

case– to do, you might not get the output, or the correctness of

a solution, that you’re hoping for. In fact, let’s try one

other, and let’s see what the other extreme might feel like. So on that same piece of

paper, maybe on the flip side or another sheet of paper, let’s

play this game just one more time. And this one’s going

to be a little harder. I’m going to try to tell

you exactly what to do. So lesson learned,

that was too abstract. Let’s now drill down on

the implementation details. OK. So let me think like a computer

might, or I think a computer might, go ahead and put your pen or

pencil down on the piece of paper toward the top middle of the page. Now from that point, move say Southwest

to halfway down the piece of paper. So really at a 45 degree downward angle. And then go ahead and move south

east, or a different 45 degree angle, toward the bottom of the page. So you’ve kind of sort of made

the left half of a triangle, or not really that, 2/3 of a

triangle, two sides of a triangle. But stay where you are. At this point in the story your pen

is probably below your original dot. But you’ve drawn two

lines that form an angle. From where your pen now

is, draw a line Northeast, or in an upward and

to the right 45 degree angle, to the same height

as your previous line. And then double back and go say

Northwest, or a different 45 degree angle, still back to the original point. And at this point in the story, you

have really either nothing at all, or you have a diamond. And therein lies a curiosity too. I could have just said diamond,

draw a diamond, or draw a kite. Which would be an equivalent shape. But that too lends itself to same

ambiguity, so I drill down deeper. But my God, it’s taken us just a minute

or more just to get to this point. And we’re not done yet. We’re not drawing a diamond or a kite. Now you have a diamond or a kite, with

a top vertex or point, a bottom one, a left and a right. Move your pen to the left one,

and draw a vertical line down. Now go back to the diamond or the

kite, and on the right vertex or point, draw similarly a vertical line down. And now, in that original diameter kite,

at the bottom most vertex or point, draw a vertical line down. And now, if you followed along

with these very precise machine instructions, you’ve got three vertical

lines that are just kind of dangling. I don’t even want to mislead you with

any hand gestures, three vertical lines that are dangling, go ahead

and draw two lines that connect the ends of those three lines. Oh my God. Like it’s so complex to do what we just

did, and I would put money on the fact that you did not draw correctly,

what I was trying to get you to draw, which is just a cube. Right, a cube is a wonderfully

simple abstraction. A shape with which you and I

are probably long familiar, and it’s so easy to say draw a cube. But as we saw before with the circle

and the square and the triangle, just saying draw a cube is ambiguous. At what angle should it be oriented? How big should it be? Where on the piece of

paper should it be? And so I was trying to

be so much more precise this time by having you put

your pen down at the top, go down to the southwest

and draw this line, then go down to the southernmost point

here, then another Northeasternly line, and then a north westerly line. And that just got us to the kite. But the takeaway here,

is that when it comes to making a computer

do what you want to do, you can’t just speak these abstractions. You actually have to implement

them, or program them, or code them at least once. In fact, some of the earliest graphical

programs in the world of computing, were kind of as low level as this. There was an old programming

language called logo, in fact, that allowed you to

program by moving a cursor, like a turtle of sorts, up and down

and left and right on the screen. And putting either down

or up a marker of sorts, and that you could draw shapes like this

by just moving around on the screen. But to draw things like this clearly,

as in our verbal example here, you have to be so darn precise. And it just gets so tedious so quickly. It certainly would take all of

the fun out of using a computer, or all the fun out of using

programming a computer, if you had to do this every time. But that’s where there’s an

ingredient here to be leveraged. One of the things that a computer

scientist, and a programmer, and engineers, more

generally, very often do, is they absolutely implement these

kinds of low level details once. They go through those very

methodical, if mundane, steps of getting something just right. And then they save the

instructions they wrote. They save the programs

they wrote, if you will, so that they can reuse them later. And the fancy words for these

things will eventually see are called libraries. Or functions. Or other names still. So once one human in the world has

implemented a program, if you will, with which to draw a cube, similarly

can we stand on his or her shoulders and reuse that same routine. And hopefully, they were clever

enough to allow us to parameterize it. To customize it, by maybe changing

the angle and the size and the depth and so forth. So it doesn’t just have

to be that one cube. And so here we have a wonderfully

powerful problem solving technique. Abstraction. Which allows us to say what we mean,

and the rest of the humans in the room just immediately understand– at

least after some instruction– what it is we’re talking about. But with computers being these

very little literal devices, we can only talk at those

levels of abstraction once we’ve actually built up software,

implemented solutions to get us to that point in the conversation. And this is why, at first glance,

using a phone in your pocket or a computer on your desk might

actually seem super, super complicated. There’s so many moving parts. And absolutely there are. Windows and Mac OS are

literally the result of millions of lines of programming code these days,

having been written over the years. And so of course it’s to be expected

that you might be a little daunted or overwhelmed by the

apparent complexity. But one of the goals

here for this lesson, is to really help you appreciate

that beneath all that complexity, is a simpler idea. And then an even simpler idea. And then a very simple

idea, and so forth. And so once you sort of bottom out

and understand those first principles, zeros and ones, binary on top of which

might be Ascii or Unicode, on top of which might be some

other encoding still, can you resume the current

conversation and understand that what might have looked

completely complex at first glance, is really just the result

of assembling, if you will, a whole bunch of pretty

simple puzzle pieces. So at this point in the story, we now

have a way of representing information. But now let’s just stipulate. We know how to represent information. At the end of the day, Yeah it’s

binary, And at the end of the day you can think about it as decimal, and

maybe you’re using Ascii in Unicode, or maybe you’re using

graphics, or whatever is going on underneath the hood. All we need to know and care

about now is that you can do it. And we don’t really have to think

too much more at that level. Now we can resume our look

at the overarching model at hand, which is problem solving. We now have a way to represent

our inputs and outputs. What then is inside that black box? Well the buzzword du jour

these days is perhaps algorithms, where even if you

don’t necessarily know what it is or how to make one, or how to use one

in the context of a computer program, algorithms seem to be increasingly

the solution to all of our problems. Well an algorithm isn’t

all that complex, fancy though the word might

sound, it’s really just step by step instructions

for solving a problem. And those steps can be in English, or

they can be in something we’ll call pseudo code, sort of code like but

it’s not really an actual language, or can be in Java, or C,

or c++, or JavaScript, or any number of other

programming languages. Algorithms are, again, just sets of

instructions for solving a problem. Well what’s one such problem

we might want to solve? Well in the real world we might have– the real old world shall we say– we might have a problem that once

upon a time looked like this. A phone book with a whole lot

of pieces of paper inside of it, on which were a whole bunch of names

and a whole bunch of telephone numbers. And the phone book was

alphabetized from A to Z typically. And maybe there were some other sections

like the yellow pages, or apparently the red pages, whatever this is here. But we’ll just assume that

these are the white pages, so to speak, with just a whole

bunch of humans names and numbers. So suppose I want to

find one such human, a human whom we’ll call Mike Smith. How do you go about finding

Mike Smith in this phone book? Well I could, somewhat stupidly,

but arguably quite correctly, start at the beginning of the book. And I see here instructions

for calling 911. If I move on to page two, I now

see someone’s names and numbers. But these people’s

names all start with A. And so I continue going

through the A section. And the A section. And then eventually I

get to the B section. And the B section. And the B section. And then the Cs, and the Ds

and the Es and Fs and so forth. And eventually, tediously but correctly,

I’ll get to the Ss in the phone book. And if I see Mike Smith here, I can now

pick up the phone and call Mike Smith. Now no one out there, if you’ve

been still use this technology, is going to have looked

up Mike Smith in that way. You’re going to fly through this

phone book far faster than I, right, you learned probably in grade

school why count by ones when you can count by twos? So two, four, six, eight, ten, twelve. Sounds faster, is faster. It’s going to get me to Mike faster,

but is it going to get to me to Mike correctly? I’m going twice as fast by

doing two pages at a time. So I’m going to have

flip half as many times. But there’s actually a bug, so to

speak, a potential mistake here. What is that? Well in my cleverness

to get to Mike’s name twice as fast, what if I

go ever so slightly too far, just because by bad luck, Mike

is sandwiched between two of the pages that I so cleverly was

skimming two at a time? Of course I’m looking at

this side, maybe this side, but maybe Mike is in the middle. And so it turns out with that

algorithm, that twosie approach, am I going to have to have a

little bit of a check at the end? Such that if I hit like the T section,

and see a name starting with T, I better wait a minute,

let me double back, I might need to go back at

most one page to make sure that I didn’t actually miss Mike Smith. So at the end of the

day, it’s not correct if you naively just do

two pages at a time, but it is correct if you

do two pages at a time, with one final reversal by

a page, just to make sure once you go past SMITH

in the phone book, that you didn’t accidentally

miss Mike just one page prior. So it’s still super fast, you

just need that one little check. But still, no one out there, is going

to look up Mike Smith one page at a time, two pages at a time. You’re going to open in the

middle of the damn phone book, look down and see, oh, not in the S

section yet, I’m in the M section. And so what you intuitively know

how to do since growing up perhaps, is that you know Mike is not

in this half of the phone book. Mike is clearly in this

half of the phone book. And so at this point you can

figuratively– but in our case literally– tear the problem in half. Throw half of the problem

away, and be left with, we single use phone book, and half at

that, but half the size of the problem. So if we had 1,000 pages originally,

now maybe I’ve got only 500 pages. And so I can repeat this intuition. Jump roughly to the middle. Darn, I’m a little too far

now, I’m in the T section. Again, let’s tear half the problem

away, throw it away as well, and now be left with a 250 page problem,

which can now be 125 page problem. Which is getting easier and easier

and easier, until we repeat, repeat, repeat, repeat. Until theoretically, we’re left

with just one page in the end. Maybe Mike’s on it, maybe Mike’s

not, but if he’s in the phone book, he will be on this page. So how efficient was that. Well if that phone book had 1,000

pages, in my first algorithm it might have taken me what, like

700 plus steps to get to Mike? Or in the worst case 1,000

steps, right, it’s alphabetical. But maybe it’s not

Smith, maybe it’s someone with the last name that starts with Z.

In the worst case in that first phone book, maybe it would take me 1,000

steps maximally to find Mike Smith. Pretty slow. What about that second algorithm

where I was going two pages at a time? Well, with that algorithm, it’s

going to take me like 500 steps maximally to find Mike Smith. That’s twice as fast,

that’s pretty good. It’s not nearly as amazing as

the algorithm we settled on. The intuitive one, arguably,

where I divided and conquered. I have the problem again

and again and again. Because if I start at 1,000, and I go

to 500, then 250, then 125 and so forth, rounding as needed, I actually

get to one page much faster. Put another way, how many times

can you divide 1,000 in half before you’re left with

just the number one? Well if you do the math, either

in one direction or the other, you’ll see that it’s roughly ten. In fact, if you want to pause even and

grab a calculator, or a piece of paper, or pencil, or just think through it

in your head, you can start with 1,000 and go to 500, 125, and so forth. And you’ll eventually

hit one, after just 10– give or take, depending

on how you round– steps. That’s pretty powerful. But not that big of a deal. Right. Ten still is like a lot of page turns. But what about an even bigger problem. The types of problems that Google,

and Microsoft, and Facebook, and Oracle, and really big

companies deal with that have lots and lots of data. Suppose, for instance, that I’m

searching through not a phone book, but a database. A big program that stores

lots and lots of data. And suppose the data that’s being

stored is still names and numbers. How much time might it take to

find someone like Mike Smith, in a database that’s got like 4 billion

names and numbers in it somehow? Well, four billion names and numbers. Well if we use that

first algorithm, might take as many as four

billion steps to find Mike Smith in a really big database. In a really big computer

program, that’s not too smart. But if I instead use

the twosie approach, flipping through two

database records at once, maybe it’s not 4 billion operations,

maybe it’s just 2 billion. That’s good. That’s half as many operations. But what if I use this

super clever intuition that I kind of grew up with here, with

that divide and conquer algorithm. Well, I can start with 4 billion

database records, go to 2 billion, then 1 billion, then 500 million, 250

million, 125 million, and so forth. I’m getting to one much, much faster. In fact, I can only divide

the number 4 billion in half, roughly 32 times total. Again, depending kind of sort of

on how you round, but 32 times. 32 is so much smaller

than 2 billion steps. And 32 is certainly smaller than

the original starting point, 4 billion steps. So this is a really powerful

problem solving technique to divide and conquer. And here, too, even though what

computers might seem to be doing these days is super complicated

and sophisticated– and it is in many ways– but some of the ideas that those

computers and the programmers who program them are leveraging, are

actually pretty familiar to us already. Inside of this black box might not

be something super fancy, but just a clever adaptation of

some of your grade school human intuition to the

context of a computer program. Now it’s one thing to talk

about algorithms, especially if we’re just spit balling it verbally. But computers, of course,

need us to be more precise. And they need us to state our

thoughts more methodically. So what does this mean? Well, let me propose that we write

some code, or really pseudocode, for this same algorithm, where

we’re looking for someone like Mike Smith in a phone book. And it’s pseudocode because it’s

not going to be Java, or c++, or JavaScript, or anything else. It’s going to be English like syntax,

that’s kind of sort of like code. And before long, we’ll see

some actual code as well. But step zero, and just

to be playful here, I’m not going to start counting at one,

I’m going to start counting at zero, just because with any

number of bits, or digits, the lowest number that I could

count with is of course zero. Pick up phone book is the

first thing that I did. One, open to the middle

of the phone book is the second thing I did in

that third and final algorithm. Look at the names was the next thing I

did, looking down at that phone book. And then if Smith is

among names, and notice, this is semantically different

from those first three steps, because this expression starts with if. So this is kind of like the

proverbial fork in the road, if Smith is among the

names, let’s do this. What do we want to do? Call Mike, that’s great. Otherwise, or else if Mike

is earlier in the book, let’s go a different direction instead. Let’s instead open to the middle of

the left half of the book, all right. So that would be the left half

that I threw away earlier, and then go back to step two. Because once I have opened to the

middle of the left half of the book, I don’t have to actually

dramatically tear it. I now need to look for Mike’s

name again, as per step two. Else if Mike is later

in the book, I actually want to open to the middle of

the right half of the book, and then go back to step two as well. Now you might think that’s

everything to this program. But there’s actually a remaining step. Indeed I’ve got room left on the

screen for a remaining step or two, but there are more than

three possibilities. One of them is that Mike is

among the names, one of them is that Mike is to the left, the

other is that Mike is to the right. What’s the fourth? If I don’t consider the fourth,

and indeed if in a program I don’t implement the fourth,

my program might crash. My computer might hang. My computer might behave

in an unpredictable way, because if the programmer wasn’t

so precise as to anticipate something that might happen, who

knows what the computer might do. And indeed, that’s often

why your own computer might have a little spinning

beachball, or icon, or it might crash outright or freeze. It’s because something

unanticipated happened. So let’s be precise. There’s a fourth and final

scenario I can think of, which perhaps on your

mind too, just quit. Because in the fourth scenario,

if Mike’s not among the names, and he’s not to the left, and

he’s not to the right in the book, he must not be there. And so let’s avoid just hanging

infinitely somehow or other, by actually proactively

deciding to quit. But now let’s tease apart what some

of these terms actually are now. So in yellow are some things that

really just look like verbs, or actions. And we’re going to call those

statements, or more specifically functions, or procedures would

be a reasonable synonym too. And each of these yellow

terms is really a call to action for the computer to

just do something unconditionally. But sometimes, we want that computer

to do something conditionally, as evinced by these yellow terms now. If, and else if, and else and else,

kind of paints the picture of a four-way fork in the road. Where each of these

branches, or conditions, leads us to take different action. And you’ll see that I’ve indented lines

four and six and seven and nine and ten and twelve, because

they are meant to happen only if lines three and five

and eight and eleven, or eleven, actually applies. So those indentation kind of

captures the logic of this program. Lastly, or second to last there is this. This is what we call a little more

fancily, a Boolean expression. These yellow phrases here

are kind of like questions. There are either yes no, or

true false, or one and zero or any number of other binary terms. But these are questions we’re asking. The answer to which is

going to be true or false. Smith is among the names, true or false? Smith is earlier in the

book, true or false? Smith is later in the

book, true or false? And so these Boolean

expressions, named after someone who the last name of

Bool, long ago, is a way of having conditions take you

in a different direction based on whether something is true or false. Three such examples there. And then, lastly,

there’s these two lines. On seven and ten there’s

this expression go back to step two, which is to induce

a bit of cyclicity, right. You can sort of think about it

visually if you go from step seven, or ten for that matter,

back up to step two. This might happen again,

and again, and again, if Mike is still to the

left half, the left half, the left, as you’re whittling

down the phone book. And so we’re going to induce, and

induce, and induce potentially, this cycling or looping behavior. So these lines here

now in yellow represent what a computer program

might call a loop. Now these same English phrases we’ll

eventually see can be translated into Java, and c++, and

JavaScript, and Python, and Ruby, and other languages still. But the key takeaway

for us here today is one, the precision with which

we specified these steps, two, the fact that there’s this ordering,

what happens after the other. The fact that there is

these conditions, some only happen if something is true,

and the fact that some of them can happen again, and again, and

again, based on some kind of looping. But is this good? Like this is correct, and that

of course, was one of our goals with the phone book, initially,

was let’s get it correct, and better still, let’s get

it correct and efficient. correct and fast. But how fast now is this? In fact, how do I put a

number, of really a formula, on the performance of

the algorithm so that I can claim that I am a good programmer,

or I am a good problem solver? I’ve not only solved your problem

correctly, but really, really well. Well let me propose that we

analyze these three functions. Kind of in the abstract. We don’t need actual arithmetic

expressions here, per se. We’ll just do things

variably as follows. So here’s a nice little Cartesian plane,

with an x-axis of size of problem, and a y-axis of time to solve. And the farther out you go on size

of problem, from left to right, means bigger, bigger, bigger, bigger,

bigger, bigger, bigger bigger problem. And by bigger problem I

mean more and more pages. More and more input, whatever

the problem actually is. And then time to solve, is not

very much time, lots of time. So on the y-axis too, the

higher you go, the more time it takes to solve a

problem, or really the slower it is to solve the problem. So let’s now draw this red line here

as a depiction of the first algorithms performance, or running time. Whereby, there is a one to one

relationship between size and time. A one to one relationship

between number of pages, and maybe number of page

turns, or seconds, or whatever your unit of measure happens to be. So that if I have a phone book of this

size, this dot here on the red line is how many seconds, or page

turns it takes me to find it. And there’s a linear relationship

there, as implied by this variable– as we’ll call it– as in algebra. n for number of pages, for instance. It’s linear in so far as Verizon,

if the phone company like Verizon increases the number of pages in the

phone book just buy one next year, a few more people move into town so they

add one more page to the phone book. That might take one additional page

turn to find someone like Mike, or anyone else in that phone

book if Verizon just adds a page. Or if they doubled the

number of pages, it might double the amount of

time it takes to find someone. There’s a linear

relationship between the two. Now with the second algorithm, where

I was flying through the phone book two pages at a time, there’s

still a linear relationship, but it’s not quite as bad so to speak. For instance, if I have this

many pages in my phone book, my first algorithm might take this

many seconds in the first algorithm, but because I’m flying through

the phone book two at a time, it will take me half as much time. Half as many page turns

with that second algorithm. So we’ll describe it

algebraically as n over two. Where n, again, is just

the number of pages. So there is a relations