[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 relationship between

those two lines and those two formulas. But that third algorithm. Super, super fancy I’ll wager. And the shape of its line

is fundamentally different. If you remember your

logarithms, you’ll see here this green curved line, otherwise

depicted here as log of n, or really log base 2 of

n, but we’ll just keep it abstracted away as just log of n. This is a fundamentally different shape. And it still goes forever

up and up and up and up. Even though it looks

like it’s flattening out, it’s not perfectly flattening out, it’s

just growing and growing very slowly. And that’s key, because what’s powerful

about that third and final algorithm, is that Verizon, for instance, doubles

the number of pages in the phone book next year, because a whole lot of people

move into town, or maybe two towns merge or whatever. Then how many more steps will

it take me to find someone like Mike Smith in that phone book? Well just one additional page turn. One additional tear of the phone book. Because with each tear can I

take a bite out of that problem. That’s 50% of it. I can literally tear it in half. Meanwhile, Verizon doubled the

number of pages in the phone book with my first algorithm, as per this

straight linear relationship, aka n, it would double the amount of time

necessary, or double the number of page turns necessary, to find

Mike Smith in that case. So again, in the case

of the first algorithm, would double the amount of time taken. The case of the third algorithm

would increase by one step. One step. So if that phone book went ridiculously

from four billion to eight billion, no big deal. But that third algorithm, just

need one additional page turn. One additional tear of the phone book. Not in the case of the first algorithm. I would need an additional 4 billion

page turns to find who I’m looking for. OK. But a phone book is a physical problem. And searching for phone numbers in

a phone book is a physical solution. But what can computers

do electronically? Like what is the analog in

our computer to the problems we’ve been solving thus far? Well what about our own iPhones,

or Android phones, or the like, where you have contacts these days? Sort of a digital

version of a phone book. And those contacts are

typically sorted alphabetically. But even then, you might know

a lot of people, and most of us probably don’t scroll, scroll,

scroll, scroll, scroll. And if you do, you’re doing it wrong. You can instead search by keyword,

or by first name, or by last name, to actually find someone

much more efficiently. And typically their name

jumps to the top of the list. So that’s an algorithm. The Google, and Apple,

and other companies have implemented algorithms

for searching, or even sorting your list of contacts so that they

can find people for you quickly, so that you can just send them a

text message or make that call. But let’s simplify further. Rather than even get into the sorting

of names, and alphabetical phrases, let’s keep things simple for a moment. And just assume that we want

to store things like numbers. A list of numbers for instance. So if we want to store a list

of numbers, how can we do it? Well let me propose that the screen

here, or if you will a piece of paper in front of you, really just

represents your computer’s memory. Now you may know that

inside of your computer there’s different types of memory. Something called the hard disk,

or maybe a solid state disk, or something called ram, or random

access memory, something called Rom or read only memory, something

called l-1 cache, l-2 cache, sometimes l-3 cache and the like. So there’s different types of memory. But the one we’re going to think about

right now is ram, random access memory. And this is the type of

memory that you might have a gigabyte of, four gigabytes of,

16 gigabytes of, depending on how fancy your laptop or desktop computer

is, or your phone for that matter. So inside of your computer, or

phone, is a whole bunch of memory. A whole bunch of RAM. And if you have, for

instance, 4 gigabytes of RAM, that is four billion bytes. Because what that means

is giga means billion, so four giga means for billion, four

gigabytes means four billion bytes. Mega, meanwhile means

million, give or take. And in fact, earlier

when we talked about rgb, And four megabytes then

would be four million bytes. So 4 gigabytes is even bigger. And if you want to count

higher still, four terabytes would be a huge amount of memory. So if you have four

gigabytes of memory, that’s four billion bytes of memory, and a

byte meanwhile, is just eight bits. So why talk in terms of bytes? Well it’s just easier to

talk in terms of eight bits, rather than individual bits. Because with one bit, you

can’t really do all that much. You can only count from zero to one. So with 8 bits at least we can count

a bit higher and express a bit more. so if we have 4 billion bytes of

memory inside of our computer, you know it stands to reason that

we could number each of those bytes. And maybe the top most byte up

here represents byte number zero, and maybe the bottom most byte over

here represents the number four billion, give or take. In fact it’s not exactly 4 billion,

it’s a little more than that. But for our purposes, let’s just

assume that if this screen here represents all of my computer’s

memory, and you know for that matter, let’s think of my memory as being

divisible into rows and columns, just to kind of keep things orderly. This is not actually what it

looks like underneath the hood. And it’s definitely not as wavy

as I making it out to be here. But you can think of it

really, as rows and columns, that you can address each

of the cells in this table. So kind of sort of like a spreadsheet

with a whole lot of room for values. So this might be byte zero one,

two, three, dot dot dot if you will. Four billion or so in the

bottom right hand corner. But where these things are laid out

doesn’t really matter for our purposes right now. So that’s how you might address memory. But how might you use memory? So suppose I want to store

a whole bunch of values inside of my computer’s memory. I don’t really care where

it is for the moment. And therefore, I don’t care

what those addresses are. But let’s suppose that I do care that

the numbers are close by to each other. They are contiguous in memory. Back to back to back to back. And we’ll see that that has

some advantages for efficiency. So suppose that I want to store

one number in my computer’s memory, and suppose that this memory

and this memory and this memory here, those are all being used

already by other programs, or other things going on in my program. And so the first available slot,

for instance, say is this one here. And the number I want to

store is the number one. And the next number that I want to

store is going to be the number 50. And the next number I want to

store is going to be the number 51. And the next one 61. And then the next one 109. And then the next one 121. And so forth. Which is to say, if I’m storing not

people’s phone numbers or names, just more simply for

the sake of discussion, all I care about for whatever

reason is storing a list of numbers. I might store them in my computer’s

memory in exactly this way. Each of these squares represents

a byte, or eight bits. We know that we can abstract

above bits, and actually represent things like decimal numbers. So I’m just stipulating

that inside of these boxes really is eight bits, or some

pattern of eight zeros and ones. But that’s too low level. We’re going to abstract away from

that and just talk in terms, for now, in decimal digits. So this thing here might

be how I store something underneath the hood in my computer. And what’s nice about this, is that

it’s super, super easy to find values. In fact, let me just highlight this

range of values, and slap a name on it. This boxed in region here

in a computer program, would very often be called an array. It’s a list of sorts, of

values, but what’s key here is that this list of

values is back to back to back to back all contiguous in memory. When that is the case, when you have

this property inside of a computer, you can do things pretty darned fast. Because there’s a mathematical

relationship among the locations of all of these values. For instance, if you are

the computer, and you find yourself looking at

the number 50, how do you find the next number in the list? Well, you just add one to your location. Not one to your value,

one to your location. How do you go from the number 51 to 61? You just add one to your location. Again, because if this is byte

zero, one. two, three, and I don’t know where we are here. Maybe this is byte 100, 101, 102, 103. Because all of these values are

back to back to back to back, you can very quickly access them

just by looking to the left, looking to the right, by

a fixed number of bits. This is advantageous,

because you can jump around. In fact, this is where the name

random access memory comes from. You have random access, not in the sense

that you just go anywhere randomly, but you can go anywhere you

want in the same amount of time. Even though this byte four billion looks

really far away from everything else, doesn’t matter. Because arithmetically the computer can

say, give me byte number four billion. And that’s a constant time

operation, it’s not linear. Doesn’t take more and more steps the

farther away it is, because all of this is electricity and

electronic, not moving parts. You can just instantly jump to any of

the cells in your computer’s memory like that. The catch is, me the human, can

look at these values and just see, oh I see a whole bunch of values. Six values inside of that

array of memory there. But a computer can’t do that. In fact a computer can really

only see one value at a time. And so when I say the computer can go

get value four billion, it can do that. But it can only go get that one value. If it wants another, it has to go

get that value and another value. And indeed, inside of a computer, inside

of a CPU that a company like Intel might make, there’s

an instruction that’s often called load, which

refers to exactly this process. Go load a value, maybe one byte,

maybe four bytes, maybe eight bytes, from memory, and bring it back to me. And put it in something

called a register, typically. But that load operation is kind of like,

if you’ve ever seen those fancy soda machines where it doesn’t just

drop your soda on the ground, instead there’s that fancy little

robotic arm that for whatever reason goes left and then goes right

and then goes up and then goes down, and then finally decides

where your soda is. Then it moves it over the

dispenser and drops it out. Well that kind of robotic arm is

kind of like a physical incarnation of a computer, in that it can’t

just take a look back and figure out where the coca-cola is, it has

to go to that particular location and actually drop it for you. But computers, when there aren’t moving

parts, can just jump there instantly. You don’t have to wait for

that robotic arm to move. And so in this case, the computer can

get one of these values instantly, but it doesn’t know what value

is there until it arrives. Right It’s kind of like being– another analogy might be

a whole bunch of lockers in a train station or the like. Where the only way you can see what’s

inside of a locker is by renting it or by putting in a key and opening

it up and seeing what’s inside. Similarly, can you think of

there being tiny little doors, occluding these numbers so that

the computer has to open it up before it sees what’s there. Speaking of doors, let’s suppose

that the computer’s memory actually has some doors in front of it. Depicted here, is just

these simple rectangles. And behind each of these

doors is some random numbers, among which is one number

I do know and care about. In fact, I want to find

myself the number 50, but I don’t know where it is. So I’m going to take a pretty naive,

but correct approach, of just starting from the left. Just as we did with a phone book,

starting from the first page. And I’m going to go ahead and knock

on, and then open the first door. And I see the number 15, that

of course is not the number 50. So I’m going to proceed further. To go and knock on and touch

the second door, and I see 23. Still not the number I’m looking

for, so I knock and touch again. 16. Knock and touch again. Knock and touch again. Still no number, but I have

found the meaning of life. And let’s try one more door here and

touch the number 50 behind this door. So here too is a very linear

algorithm, but these numbers are kind of all over the place, right. It starts at 15, gets a little bigger,

then gets smaller, then smaller still, then bigger then bigger again. So it doesn’t seem that

these numbers are sorted. And in fact, if the analog

then in my phone might be, my contacts might be

just randomly ordered. Maybe ordered in the

order in which I inputted them, which probably isn’t ideal

when I want to find someone. I don’t really care in what

order they were put in, I care that I find them quickly. And so maybe I should do

a little work up front, or maybe Apple or Google should

do a little work upfront, and actually maintain my

contacts in sorted order. Which indeed they do. Or in this case here, why don’t

I at least maintain my numbers in sorted order. So let me go ahead and reset all

of the doors, and start again. This time with an assumption. This time with a feature, if you

will, that the numbers are now sorted behind these doors. So they go from smallest to biggest, and

there might be some gaps in the middle, but in so far as they’re

now sorted, I can leverage some of that old school

phone book intuition and divide and conquer this problem. Let me go ahead into the middle

of the problem now, not the left, and let me go ahead and knock

on and open the middle door. And there’s 16. Now 16 is kind of a

small number, but I now know that none of the

numbers to the left are going to be the one I’m looking for. Because I’m still looking for 50. So I can sort of throw

that half of the problem away, or really just

turn a blind eye to it. And now go to the right

half of the problem, identify the middle door here, knock on

and open this one, there again is 42. But now, again, I can apply

some of that intuition and know that 50 is

bigger than 42, so must be that 50 is right here at the last door. And in this case, have I gotten

away with opening fewer doors? It’s not a frightening number of fewer

doors, it’s still relatively small, but that’s only because we could fit

some seven doors or so on the screen here. But if the number of doors were four

billion, or if the number of doors were even larger, surely with

this divide and conquer approach, could I find my number super fast. But there’s kind of a

trade off here, right. Like yes, I can now find

numbers faster, or equivalently I can find people presumably

in my address book in my phone faster, if they are maintained in

sorted order, but what price did I pay? In fact, a theme in computer science,

and in programming specifically, is this theme of trade offs. Yes, you can speed up searches, but

you’re going to have to pay a price. What is that price in this context? Well it took someone some amount of

work to sort those contacts, right. Before class I had actually come up

with the sorted order of those doors, and then put the right numbers

behind the right doors. There was a non-zero amount of work. Not a huge amount of

work, but it’s non-zero. So really, by speeding

things up during search, I have to first incur an up front,

one time cost, of sorting things before I even begin to search. Or equivalently, someone at

Google, or someone at Microsoft, or someone at Facebook, or any of

these big companies with big data, if they want to use

searching efficiently, they need to pay a price upfront

of sorting the data first. And indeed, that’s what Android

and iOS and other devices too, must be doing underneath the hood. Someone at some point in time,

probably long ago at this point, implemented a sorting routine. But how quickly can we sort numbers? How quickly can we actually achieve

that result of sorted values so that we can then do

search more efficiently? So for this, let’s try

something a little visual, a little old school, in fact. We’re here in this beautiful theater. And in fact we have a whole bunch

of music stands from the musicians. Let’s go ahead and use

a few music stands, each of which will represent a

location in my computer’s memory, and then I’m just going to

have some numbers that I want to put inside of those locations. And let’s see how expensive it is

for me to actually sort those values. So I have here in my hand the

numbers one through eight, and I have here eight memory locations

as represented here by music stands. And let me go ahead and just put these

numbers in pretty much random order. I’ve got my little cheat

sheet there up on the screen, so that we reset each

time to the same location. And I’m just kind of putting

these in some random order. Where four’s going to be

over here, and the numbers are going to sometimes

get bigger, sometimes get smaller from left to right. The key, though, is that

they’re not actually sorted. And so I start now with

these values as such. All right. So suppose I wanted to find

now, maybe the number 50. Well 50 is not among these numbers,

so we better think a little smaller. Suppose I want to find

myself the number seven. Well again, as in the case

of a computer, or the doors, I can only find seven not just

by kind of cheating like a human and say, oh there it is over there. I have to get to that

point more methodically. And define the number seven linearly,

using linear search, so to speak. I have to check is this it, nope. Is this it, nope. Is this it? Nope. Is this it? Nope. Is this it? Nope. Is this it? Nope. Is this it? Yes. And now I found it, coincidentally,

some seven steps later. But seven could have been

anywhere, but in the worst case, it’s all the way over here. Now could I use binary search on this? Let’s actually slap a label on that

algorithm we’ve leveraged with a phone book. Dividing and conquering. If you do it half and half and half

and half, looking for some value, it’s actually more technically

called binary search. Bi meaning two, and so it’s

two because you’re splitting the problem in half each time. Could I use binary search here? Well there’s one minor

problem, which is that I don’t have an odd number

of music stands, which means the middle element is

like between eight and one. But that’s fine. We can deal with that arithmetically

by just rounding up or down, depending on how we want

to implement it ultimately. But even then, that’s

not the biggest problem. If I look at eight here, and

I’m looking for seven, well based on my previous divide

and conquer strategy, I should be looking to the left

because seven is smaller than eight. Of course I’m not going to

find it to the left of eight, because it’s not there, it’s over there. And that’s because the

numbers aren’t sorted. So as in the case with my

hypothetical address book, if I want to be able to

search this efficiently, or search a database sufficiently,

or search most anything efficiently, I need to know something about the data. And ideally that it’s sorted. So how do I get to the

point of sorting this data? Well, you know what, I could

take a fairly localized approach. Like four and two, I’m

looking at them right here. And technically, I’m looking

at them one at a time. I see four, I see two, and

I know they’re out of order. Well, as the computer, I could do this. I could, using my load and

store instruction, essentially, or a move instruction, do that. And now I’ve improved

the sorting of this list. Now four and six, those look OK. Six and eight, those look OK. One and eight, Mm-mm, not OK. So let me just make a quick fix. Let me just swap one and eight. It’s not perfect yet, but it’s better. Eight and three, let

me make a quick fix. Well, that’s better. Eight and seven, a quick

fix, that’s better. Eight and five, quick

fix, that’s better. So this is great. Eight is all the way to

the right as intended, and one is not yet all

the way to the left. So I haven’t solved the

problem, but I have improved it. I’ve gotten a step closer to the

correct solution of sorted numbers, because some of the values

moved at least one step closer to their intended location. But of course, I’ve

got to do this again. So two and four their good. Four and six they’re good. Oh six and one, now that’s out of order. And so I can transpose these two. So this algorithm has a name, whereby

I am transposing pairwise elements that are out of order, such that the biggest

numbers are bubbling their way up to the top. eight already made its way

there, seven just made its way there. And so if I keep doing

this, these bigger values are going to continue

to bubble their way up. Two and four those or fine. Four and one, ooh notice, four is

starting to bubble to the right. Four and three, it’s

continuing to bubble. Four and six is OK. Six and five, mm-mm. Six bubbled its way up, and

now I got a good one there. I really fixed a lot of those values. I just need to do this once more. One and two, fixed that. Two and three, three and four, four and

five, six and seven, seven and eight. Let me do another spot

check just to make sure. One and two, three and four,

five,six, seven, eight. I’m good. But I did a lot of walking, and

I did a lot of transpositions. And it turns out this

algorithm is correct, does have a formal name

called bubble sort. But it’s not very efficient. In fact, if you actually do the math

out, this takes as many as like n times n steps in the worst case. So if you have n elements,

that’s eight in this case. N times n, that’s 64. It’s not actually 64, but it starts

to approach 64 asymptotically, so to speak. So if we did a formal

analysis, long story short, it would start to feel like

something quadratic, so to speak. Not a fast algorithm. But there’s other ones. So let’s actually try

out another algorithm. Let me go ahead and restore the

original, seemingly random order here. And indeed it is random

in so far as I’m just putting it in some non-sorted order

that I thought through initially. One’s going to go here, three is

going to go here, seven and five. So now we’re back to the

original unsorted order. You know what, I can do another

algorithm altogether here. Let me not look at them pairwise,

let me just go even simpler. Let me just find the smallest

number, and deal with it. All right, four is pretty small indeed

it’s the smallest I’ve seen thus far, I’m going to hang on to this. Oh wait a minute, two a smaller. Let me hang on to that. Six not smaller. One, eight not smaller. One is smaller, let me go

ahead and hang on to this. Three, not smaller. Seven, five. OK so here’s the smallest element. I found it I’ve selected

the smallest element. You know what, this belongs

all the way to the left. I’m going to put it there. I’m going to do that. Of course, this is cheating. Like this music stand, even

though it’s kind of wide, should only be storing one value. There’s only enough room for one

byte for instance of information. So where do I put four? Like four can’t stay on

the same music stand. You know I can’t cheat and do that. So I could move eight over,

move six over, move two over, that’s a lot of work. Or I could just, fine, four was already

out of order in the first place. Let’s just put four over here. It’s not made the problem

any fundamentally worse, because they started in random order. I randomly put four there. The key is, one is in

really good shape now. Let me repeat this process of

selecting the smallest element. Let me look for the next smallest. Two is pretty small. Small, smallest, yep. OK I found it. Two is the smallest. Let’s put him co-incidentally

right where he goes. So that was kind of a waste of time,

but verification that it’s correct. Let’s keep looking. Six is pretty small now. Eight is not, oh four is smaller. Let’s grab four. Oh Three is even better. Let’s grab that. Seven, five. OK 3 needs to be put in its place. I don’t want to touch one and

two, because those are good. Six, sorry you don’t belong there. Let’s go ahead and evict

you and put six over there. So if I repeat this process of just

continually iterating, or looping, if you will, through the list,

looking for the smallest element, and evicting whatever is in

the place that it belongs, notice that I’ve sorted

it seemingly faster. But I actually got a little lucky there. It turns out that this algorithm, which

also has a name called selection sort, is also quadratic in nature. If you’ve got n elements, it’s going

to take roughly n times n total steps in order to achieve that. Not in every case. But in the worst case, so to speak. So it turns out this is just

two ways now to sort elements. And there are dozens, if not more,

other ways to actually sort elements, with each one getting maybe a

little better, maybe a little worse, maybe a little better

depending on the inputs. So sometimes it really depends. But these are all examples

then of algorithms. And algorithms have performance

associated with them. Algorithms have a running

time associated with them. And one of the things that

theoretical computer scientists do, is not only design

algorithms like these, or really even way more

sophisticated algorithms than these, but also analyze them. So that we can make arguments,

mathematical arguments, sometimes that state as a proof,

this algorithm is correct. No matter what, this will

sort your elements correctly, if implemented correctly

in a computer, and this is how much time it will take in

general in order to achieve that. But the takeaway here, is that

it was a lot of work, right. I had the luxury with

that phone book, long ago, of just opening it up to the

middle and looking for Mike Smith, and da da da da da, found Mike

Smith pretty darn efficiently, because Verizon, or whoever

made the phone book, actually did all of the

upfront work for me. So here’s a question then. Suppose that you have a

whole bunch of random values, and you want to search for something

specific among those values. Mike Smith, number 50, whatever

it is you’re looking for, should you sort those values

first before searching? Should you sort the values first? Well, I would wager you

should sort them if you’re going to be searching over

them pretty darn often. Right. Because it might be

painful, might be boring, might be tedious to actually sort

those values either manually, or algorithmically with a

computer, and a computer program. But it’ll probably pay off over time. So there’s this notion of amortization

of the cost over time, whereby yeah, it might take you a decent amount of steps. Quadratic, seconds, minutes,

whatever you want to measure it in. But, it’s going to pay

off in the long run. Of Course, if you add data,

you’re going to need to keep that new data sorted as well. But again, it’s this trade off. However, consider a scenario where

you just have a whole bunch of data, it’s in random order

for whatever reason, and you just want to find Mike Smith. Or you just want to find the number 50. And after that, you do

not care about the data. You’re never going to

look up someone else. You’re never going to

look up another value. Maybe then, in that case,

you should just blindly go through it brute force, so to speak. Left or right, in some sense,

or linearly, as opposed to trying to do anything clever

like we did with the phone book. Because it’s faster to just brute

force your way through the solution, than doing some upfront sophistication

just to improve the subsequent result. So again, it’s a trade off. It’s a cost benefit analysis that

you need to decide, ultimately, on what is most important. Which resource, time, space, money,

people, is most important to you. So in all of these

examples thus far have we assumed that the data is contiguous. Back to back to back with other values. And indeed, that’s exactly what

the music stands represented, were these fixed locations in memory. Bytes in your computer’s ram, so

to speak, that could have values. But you had to physically move those

values from one location to another if you wanted to sort

the values therein. you couldn’t just kind of

insert a new music stand, and push the others aside,

because that’s simply not allowed. That’s not the metaphor in question. Those music stands were

fixed just as the locations in memory of your computer are as well. And as it turns out, just as we drew

a picture before wherein we had some sequence of back to back values in

memory, turns out that in programming, actually using languages that aren’t

just pseudo code, but actual code, Java and c++ and others. Still, there is very often something

called an array, or a list. A data structure that gives you

the appearance of having values back to back to back to back. And in some languages,

these values are indeed next to each other in terms of their

bits inside of your computer’s memory. But there’s a problem

with a world like this. Because if you put in a whole bunch

of values up front, as I did earlier, and you want to actually

insert some new value, where do you actually put that value? For instance, earlier we had one and

50 and 51 and 61 and 109 and 121. Suppose I want to put the number

55 in this sequence of numbers. And better still, I want to

keep the whole list sorted. Well dammit. There’s really not room for 55 in there. I know where it should go numerically,

it should go right here, of course, between the 51 and the 61. But there’s no room. Or I could put it arbitrarily over

here, but then it’s not sorted. I could put it, well

I can’t put it there because the dot dot dot

remember from earlier, suggested that something else was there. Something else from

your program or computer was already using that location. Now I could put it maybe below,

but that’s kind of weird. The whole point here

is this contiguousness. And indeed, with the

music stands a moment ago, was it advantageous for me

to be able to take one step and be at another music stand? One more step be at another music stand. I didn’t have to walk all around

stage looking for my values, because they were indeed

back to back to back and that made things very efficient

and predictably close to one another. So what are my options? Like surely a computer can do this. It’s not the case that computers are

so dumb that once you write your values you can’t solve any new problems. So what are my options? I could put the 55 here

at the end, but then I’m going to have to reshuffle

all of the numbers. Or maybe I ask the computer

for more memory altogether, and you know what, I re

do this, and I say let me put one here, 50 here, 51 here,

55 here, then 61, 109, and 121. In other words, why don’t I

just use different memory? Different bytes in my computer’s

memory, but that feels kind of lame, because now I need twice as much

memory, at least temporarily. So I can kind of copy the

old values into the new, but leave room for that new value. So that seems a little time

consuming, and tedious certainly. And indeed, it would be

for a computer as well. But maybe there’s another

solution altogether. And here too, we’re experiencing

yet another trade off. The contiguousness of my memory

has thus far been an advantage. Because again, each of my music

stands just one step away. In the case of actual ram, each

number is just one byte away, and that lends itself to again, random

access, ergo random access memory. But it’s kind of painting

me into a corner, because I’m finding that

now I can no longer really add new values without

incurring significant cost. And by significant cost I mean having

to duplicate the entire array of memory into a new location, leaving one

additional space for that new value, which is going to take as many steps as

there are values in the original array. So you know what, maybe I take

an even older school approach, and maybe I do something proactive. A little defensive. I’ll put one there, and 50 here,

and 51 here, and 61 and then 109, and then 121 and so forth. And wow, this was clever

of me, because now I left myself little gaps in my values. So that I still get the predictability

of every value is now two steps away, but now I can fit 55 in here. Well, clever as you might

initially think that, now we’ve created kind of a problem. Because most values are two

bytes away from each other. But now there’s this weirdness

where 55 is only one byte away from its neighbors. So that’s really just

complicating things now. I can no longer predictably

take just one step at a time. Sometimes I take two,

sometimes I take one, and that just feels like it’s devolving

into a very confusing bug prone situation already. And in fact, if you ever saw, or maybe

grew up with the basic programming language, back in the day,

you didn’t number your lines of code zero, one, two, three, four. If you numbered of them

at all, you instead did something like line ten,

line 20, line 30, line 40. Which wonderfully left your room for

like nine more additions later on, without having to renumber everything. Of course now, programs just number

or lines automatically for us. And they’re not even strictly

necessary, those line numbers. So we’ve tried this, and it’s just,

it’s not really a good solution. Better would be I’ll

claim some dynamism. What if instead I consider

my computer’s memory still to be this grid of locations. But let me do this. Let me propose that the first number. I’m going to put in, maybe is here, and

just to keep things prettier I’m not going to draw the whole grid again. But let’s assume that one

byte I’m using is right there, and I put the number one in there. And then eventually, I decide

to add that second number. And I go ahead and add the number 50. And the number 50 just so happens to

end up, oh I don’t know, over here. And it’s farther away in memory. Maybe enough time has

passed that the bunch of memory in between those two values

is being used for some other purpose. And that’s OK. But the 50 and the one

are no longer next to each other, or therefore

pictorially, or really related, unless I somehow interconnect them. So for now, let me go

ahead and draw an arrow. And let me kind of weave

together my values. Much like popcorn on a thread,

or any number of other metaphors where you’re linking things together. Like with a chain, for instance,

can you make a list like this? Because my other numbers,

suppose that more time passes. I insert a third value like 51, just

happens to be over there, whatever. It’s not contiguous,

which is unfortunate. But that’s OK, so long as I somehow

link these together like this. And then maybe that next number here,

61, get lucky and it’s pretty close. So it’s over here. But we still need an

arrow to this one here. And then maybe we have maybe

121 and 109, each of which is in some different locations. So we might need this arrow here. And this arrow there. So it’s kind of all over the place. And if you ever play

the game growing up, it’s kind of like

chutes and ladders now, you kind of have to like follow

the chutes to get from one number to another. But that’s OK. In fact, it’s actually quite

beautiful, my handwriting aside. It’s not quite as efficient though. Because it turns out that if you’re

at one of the numbers in this list, and you want to jump to another, you

can get to the next number pretty fast. If I’m at one, I can get

to 50 pretty quickly. I just follow that arrow somehow. I don’t know how it works in

memory, and we don’t really need to know how it works. We can kind of abstract that away for

the sake of discussion at the moment. But I can get to 50 based on this

picture alone pretty darn directly. But I can’t really get to

like 109 pretty quickly. If I’m starting at one,

I want to get to 109. previously, I could just take one two,

three, four steps away, four bytes away and I could just take a step that’s

like four times as big as usual and I’m instantly there. But these arrows seem to suggest

that the memory could be anywhere. And so it’s almost like following a map. If I’m at one, all

right let me go find 50. Once I found 50, I can

pick up another map, and now I can follow another arrow

to 51, which is maybe over here. Now I pick up another map. Oh here’s 61. OK now this leads me to, Ah here is 109. It wasn’t as simple as

just one big step that’s four times as big as was possible

in the case of contiguous memory. Now, I kind of have to

weave my way through. That actually kind of hurt. Weave my way through my computer’s

memory to get where I’m going. So it’s a trade off, right. Because now I have perfect dynamism. No matter where there is

available memory in my computer, over there, over here, over

here, over here, I can use it. And I can just kind of stitch

together this data structure, the structure for my data. I have eliminated the gotcha that

my data structure is a fixed size. So now if I want to add another

value, suppose I want to add 55. OK, suppose that 55 happens to

have some available space here. You know what I can do here, I

can just get rid of this arrow, and then I can go ahead and

stitch this in like this. No big deal. I don’t have to touch any

of the other elements. But think back to the array. The array being the

rectangular example where everybody was back to back to back. That I had to make room for

things, or duplicate all of it. Had to do more work here, just

to allocate space for your 55, and then go ahead and just

update two of these arrows, or pointers, or references as that

might be called in different languages. So that’s pretty powerful. But again I’ve lost the

random access, which means I can’t do things

like binary search anymore. Which we’re predicated

on simple arithmetic. Divide by two, divide by two,

divide by two, Maybe round, but divide by two each time. And these arrows. Kind of abstracting maybe

too generously here. These arrows are going to

cost me some memory too. Now I’ve drawn them prettily

as arrows on the screen, but those actually themselves

are some kind of value. And it turns out that those arrows

themselves take up space, take up bits. So I’ve kind of doubled,

let’s say, the amount of space necessary to store this data. Because I need to somehow

store and memory those arrows. Underneath the hood those

arrows are effectively stored as numbers themselves. Which is to say, they take

up at least a byte or more. In fact, on most systems, they

take up four or eight bytes still. So it depends on what’s

important to you. Do you want to be able to search

the data super efficiently and actually have random access,

and do something like binary search and get that divide and conquer upside? Or do you want to have dynamism,

and be able to grow and shrink the data structure super fast, but pay

a price in terms of memory as well. And use more of those bits. It really quite depends. Now these aren’t the only data

structures at our disposal. We can use not just arrays,

not just linked lists, as we’ll call that last

one, whereby we have links tying these lists items together. But we have maybe tree structures too. In fact, we think back to

like your family tree that you might have made in grade school. You might have drawn a

little something that might have grandma or grandpa

at the top of the tree, and then their children

might be down here, and then these children might

be down here, and so forth. Well if we generalize away from a fam– OK ignore that one. If we generalize away

from a family tree, it turns out that this tree

data structure is another kind of incarnation of that previous idea. A linked list doesn’t have to just be

linked from left to right, so to speak, even if it’s kind of

swooping all over the screen. It doesn’t have to have

a start and an end. It can be a tree structure,

whereby your arrows actually, much like a branch and a program,

can go in different directions. So each of these edges in this

graph actually are directional. They take you from one place to another. You can imagine using a data structure

like this to store values as well. For instance, suppose that I wanted to

store numbers in this data structure. Instead of using squares,

I’m just doing circles now just because it’s conventional. Doesn’t mean anything else. Anything special. These are still just bytes underneath

the hood, or ultimately bits. Now suppose I want to store the number

two here, and one here, and three here, and five here, and

six here, and seven here. This is all very deliberate. Because notice the pattern

that I’ve kind of adopted. Four is at the top, in the

so-called root of the tree. What do you notice about all of

the values to the left of the four? All of its left descendants so to

speak, to borrow that family tree nomenclature. One, and two, and three. Curiously, all three of those

are smaller than the number four. What about all of its right

descendants, down this branch? Six and five and six and seven. Those are all bigger than four. That’s kind of neat. How about here? Two, this is kind of a

mini tree, if you will. This is a new route, if you

ignore everything above it. Two has two children, left and right. Notice that the one is less

than the two, and the three is more than the two. So this is not a coincidence

that I drew it like this. Similarly, if you think of this as a

tree, just those three nodes below it, six is bigger than five,

six is less than seven. So there’s a pattern. So we can actually reclaim some

of the capabilities of divide and conquer by laying

out our data, still with these arrows, these pointers

or references if you will. But not just doing it linearly,

or swiveling all over the screen, but from one start node to an end node. Where node is a fancy word for

these squares or these circles. What if we instead allow the user

to go in two different directions when searching for data? And suppose we leverage that

same phone book principle where the smaller values are this way,

and the bigger values are that way. What does that afford us? Well, this binary search tree, if

you will, to give it a fancy name, actually gives us back a

logarithmic running time. Much like dividing and

conquering a phone book. Because indeed, if I start at the

four and I’m looking for seven, and I immediately realize four is here,

which means seven must be to the right if it’s present at all, I can pretty

much chop off the half of the problem that I know seven is not in. So it’s like throwing away the

left half of the phone book. I can ignore almost half

of the nodes in the tree by just snipping off that left branch. Can’t be that easy. Got to be a trade off. What it that trade off here? Well, from the looks

of this picture, pretty though it is, relatively speaking,

it looks like now each of my nodes, each of my values has not just one

arrow associated with it potentially, but as many as two. And that means we’re spending

twice as much space as before. So whereas in our array, we

use just one byte per value, or four bytes per value, or some

fixed number of bytes per value, in my linked list

example I had to double that because I had to also store– using bytes in some form– those arrows. Those pointers, or

references as they’re called. But now in this darn tree, I

need three times as much data, because each of my nodes might

have a left child so to speak, or a right child. So again it’s a trade off. And the prevailing trade off here, thus

far, seems to be if you want less time, you’re going to have

to spend more space. Or rather, less time, I’m getting

the visual metaphor wrong here. If you want to spend less time, you’re

going to have to spend more space. And if you want to save space, you might

have to tolerate a little more time. But can we do better? Indeed, can we combine some of the best

features of multiple data structures in order to achieve

something better still? Well, sort of. It turns out that there

exists a very popular data structure called a hash table. And a hash table is a data

structure that a computer scientist will use when he or she really wants

to store a dynamic amount of data. It might grow or might shrink. But they also want to search

that data pretty efficiently, and ideally be able to find data

instantly, in constant time, so to speak. So you’ll often see a hash

table implemented, really with an array something like this,

and I’ve drawn it vertically just to make the picture prettier. But again, these are

just artists depictions. Bad artists depictions of

what’s going on in memory. It’s still just an array

of back to back values. But the values now in

the array are not going to be the numbers I care about,

or the words, or whatever. It’s actually going to be arrows, which

again we’ve stipulated take space. And each of these

arrows is going to point to what we described as a linked list. So it turns out that a

hash table will often look a little something like this. A combination of an

array, and a linked list where those linked lists might be

not present at all, might be short, might be long, totally depends. But we decide where to put our values

based on some property of the value. So for instance, if this array

weren’t this big, but maybe had 26 different locations in it. And suppose that we’re no longer

storing numbers, we’re storing names. Well every name in the English

alphabet starts with an A or B or C or dot dot dot a Z. One

of 26 possibilities. So if my hash table has

an array of size 26, then maybe, if I’m storing

names that start with A, I could just put them in this

linked list here, the first one. And if they start with B,

they’ll go in the second one. And if they start with C, the third. D the fourth, Z the very last. And what you’ll find in this

case is partial optimization. It’s not instantaneous to find

someone with a given name. If there’s a lot of people

who’s names start with A, you might still have to look

through all of the A names linearly through that list. But at least you only

have to look through 126th of the possible values

in your data structure, assuming a uniform distribution. Of course, that’s not fair, there’s

probably fewer names that start with Z, fewer names that start

with Q, maybe a lot that start with A or D

or other such letters. So your chains might

be of variable length, and maybe that’s not the best design. So maybe we should think a

little harder about this. So this principle of bucketizing things,

and putting values in their place, and using that as a

stepping stone to getting to a complete solution– in

this case of sorted order– is really useful not just in these

increasingly complex examples, but even in the real world. So for instance, if you’re

a fan of playing cards, you might have a deck of cards at home. And those cards of course, have

different values or numbers on them, and also different suits. Clubs and spades and

diamonds and hearts. And you know, sometimes you might

want to either shuffle the deck, or really un-shuffle it

and actually sort it. And if you did want to,

sort of obsessively like me, want to sort your deck

of cards, well you could just go through

it one card at a time. And then try to find or select

or maybe bubble up the values, like our algorithms before. But most of us probably

use a bit of intuition. So if I see a spade here,

I might put it in one pile, and a heart, I’m going to

put that in a different pile. A diamond, different pile still. A spade will go up here. A club now goes over here. And as I continue this pattern,

I’m kind of dividing the problem, albeit in a different way. I now have, instead

of a 52 card problem, I’m eventually going to

have four 13-card problems. But how am I getting to that point? Well, I’m bucketizing things. Not physical buckets, but there’s

like four piles here of cards. But what really am I doing? I’m really hashing these values. I am looking at each card as input. I am passing it through a sort of mental

function, a mental black box if you will, that outputs a value. Either bucket one, or two, or three,

or four, or more specifically spade, or diamond, or heart, or club. That’s kind of my hash function. So if you’ve ever done

something like that, where you’re trying to clean up a mess,

or you’re trying to sort some data, or organize your cards. Once you start bucketizing in

this way, you are hashing values. You’re taking as input

some value, maybe a card, and producing as output some identifier. Similarly, with our

example of names, if I’ve got a whole bunch of names, each of

which might start with A through Z, each time you hand me

a name, I’m looking at the very first letter

in that person’s name, and I’m deciding A bucket, Z bucket,

D bucket, C bucket or so forth. C should be over there. And deciding, based on the

input, what the output should be. So again, here to, this

sort of intuitive principle can very quickly be applied to

something much more sophisticated. Again, compare and contrast

the sort of sophistication of the before and the after. This is odds are pretty darn intuitive,

if not something very familiar to you. This might still look a bit like Greek. Certainly pretty arcane versus

some simple playing cards. But to the overarching point, that while

computing and technology all around us might seem especially

sophisticated, and complicated, and well beyond one’s

understanding, that’s just because it might be

presently beyond your familiarity with some of those building blocks. Indeed, we started so low

level with just zeros and ones, and then we got to letters,

and then maybe words and paragraphs, and graphics

and videos, and eventually so many more forms of media. And at the end of the day,

it’s useful to understand what’s going on underneath the

hood, but it’s also very empowering. Because you realize that

even once we’re at the point as we are literally right now, of

talking it this degree of complexity and sophistication for how you might

store data inside of her computer’s memory, and very efficiently

get at it, all of this was the result of these stepping stones. These abstractions. And along the way, in building

up these abstractions, and in solving problems

more effectively by standing on the shoulders of

problems solved past, similarly we have to

make some trade offs. And so at the end of the day, this

is what computational thinking is all about. This is what computer science

and engineering and programming is all about. It’s solving problems using

solutions to problems past, and along the way making very

conscious, calculated, and hopefully correct decisions, as to

what resources and what objectives are most important to you.

SIR DAVID J.MALAN A GREAT PROFESSOR EVER

You know it's a lecture for businesses when he breaks out the shirt and tie.

help a lot

great lecture; I learn a lot about foundation of computational thinking.

nice tie sir! respect, for you are the best teacher, ever!!!11!!

Thank you !

Thank you Professor Malan! CS50 has helped me finally understand how the computer works! Now, it even influences my views and thinking about the world. I really enjoy and appreciate the courses!

Very good lectures, well-developed. 😀

great production from a good instructor

Great series. Question, are the videos designed to play in sequence or we can take each vid out of sequence.

major professor of computer science go a head again

He's a legend