Computational Thinking – Computer Science for Business Professionals – by CS50 at Harvard
- Articles, Blog

Computational Thinking – Computer Science for Business Professionals – by CS50 at Harvard


[MUSIC PLAYING] DAVID J. MALAN: So odds are you
use a computer most every day, but you might not necessarily think
of yourself as a computer person. Something goes wrong, you don’t
necessarily know how to fix it. And if you actually want to solve
some problem using technology, the whole world of
technology, and computing, and algorithms and all of that
might seem all quite foreign. So much so that you can’t
necessarily feel like you’re making an informed decision. Well, that’s just because the
technology that we all use around us is kind of working at this level. Whereby there’s so many
people who have come before us that have invented this
level, and this level, and this level, and this level. And so what we’ll do here is try
to start from that ground level up. And indeed, at the base of all
computing, do we really have, as we’ll see, just zeros and ones? And that’s probably something you
know, at least, generally speaking. But it turns out once you
go have zeros and ones, can you very quickly go to text? Can you go to graphics? Can you go to videos? Can you go to spreadsheets? Can you go to so much more? But again, that’s the
world we now inhabit. But let’s now build
ourselves up to that point, so that you actually begin
to look around yourselves and realize, oh, I understand
now, what’s going on. And to do that, let’s consider this,
computational thinking, which really refers to thinking computationally. Thinking more methodically,
thinking more carefully, and somehow framing all problems in
the world as a sequence of steps. And those steps are quite simply,
input comes in, and output goes out. And what’s in between
those inputs and outputs we’ll eventually describe as
something called algorithms, but for now, let’s just consider
it to be this black box. We don’t know, we don’t care
what’s going on inside there. All that we care is that we get
back a correct output or a solution to a problem. But how do we go about representing
those inputs and outputs? If our problem at hand is to analyze
a whole bunch of financial data, a whole bunch of numbers
in a spreadsheet, how can we actually sum
all of those numbers together, or perform some other
arithmetic calculation on them? If we instead have a really big
document, a contract of some sort. And we want to make sure that
it is properly spellchecked? Well, the input there
isn’t numbers, but is all of the words and
letters in that document. And the output, we hope,
is a document without all of those little red squigglies. We want a correctly spelled document. So those are just some of the problems
that you might experience most any day, but underneath the hood, there’s
quite a bit of complexity going on. But that complexity,
it turns out, is just the result of layering, pretty
simple ideas, one on top of another. But in order to get to that
point in the discussion, we need to somehow represent these
inputs, these numbers, these letters, whatever it is that we have at hand. And to do that, we’re
going to use binary. Now odds are you’ve probably heard
that computers indeed only speak or understand zeros and ones. But how can that possibly be, when they
can do so much today, whether they’re on our desktops, or laptops or even
our mobile phones in our pockets, if all you have at the end
of the day is zeros and ones? How could you possibly count to two, let
alone three, or four, or four billion, let alone representing any
number of other types of media that computers today understand? Well, odds are you
recognize in this word here, this prefix, bi, bi meaning two,
and indeed that hints at the fact that you only have two letters
in your alphabet, so to speak. Two digits, zero and one. Now we humans have typically
grown up using the decimal system, dec meaning 10. And of course we have 0,1, 2,3,
4,5, 6, 7, 8, 9, 10 possible digits that we can permute and arrange
to count even higher than that. But with just zeros and ones, how do
you get to two, how do you get to three? Well, you’re thinking still in base
10, so to speak, base 10 being decimal. But we want to think now in
base 2, so to speak, binary, where we have just two of these inputs. And let me propose
that if you’re like me, you probably grew up understanding
numbers as really just this pattern of symbols like this, where each
symbol was in a column of sorts, a placeholder, if you will. And this, if you recall, was generally
called the ones place, and then the tens place, and then
with the hundreds place. And so at the moment, what we
really just have on the screen is a pattern of symbols, a pattern
of digits, one, two, three. But why is this pattern of
symbols, one, two, three, the number you and I think
of immediately as 123? Well, that’s because by way of these
columns or places do we implicitly, in our own mind, quickly
do a bit of arithmetic? Of course, if we have one, two, three,
that’s really like 100 times 1 plus 10 times 2 plus 1 times 3, and
of course that gives us 123. So it turns out that the binary system
is actually fundamentally the same. So if you get decimal, if you’ve been
counting like that since grade school, you are good to go now with
binary, because in fact and arguably, binary is even
simpler, because you don’t even have to keep track of so many digits. In fact, if we consider
this pattern of symbols, this of course, in our
human world, would generally be immediately recognized by
us humans as the number zero. Of course, it’s a little
silly to have those left most zeros, those
leading zeros, so to speak, because they don’t really
add much mathematically. But that’s OK. You can put as many zeros to the
left of a number in our real world and it doesn’t really affect the value. Now instead of using one and 10 and
100, let me just use one, two, and four. Now why those values? Well before, 1, 10, 100, and again
a thousand, 10,000, 100,000, and so forth. Those are powers of 10, 10 to the
zero is 1, 10 to the one is 10, 10 to the two is 100, and so forth. So what pattern do you perhaps see here? These aren’t powers of 10
anymore, 1, 2, 4, an 8, 16, 32. Now you really hear the pattern? These are instead powers of two. Two to the zero is one, two to
the one is two, two to the two is four, and so forth. So that’s the only change. By using base 10, just
two digits, zero and one, can we still count using
the same arithmetic system. So for instance, this of course
is still the number zero, because we have zero fours,
and zero twos, and zero ones. But if we instead change
this pattern to 0 0 1, well what value does this now represent? In the world of decimal, this
would represent the number one. And that’s true in the world of binary,
because we have 4 times 0 plus 2 times 0 plus 1 times 1, which
of course is just 1. So how do we get to two? You might be inclined to just
change this zero to a one, but that would be incorrect. That’s like carrying
the one, but then not wrapping around on the rightmost digit. Rather, if we want to
represent the number two, we need to come up with a
pattern that represents that. So let me propose instead that we
don’t just change that zero to a one, but we also change that one to zero. Because now we have 4
times 0 plus 2 times 1 plus times 0 which of course
is the number we know as 2. And now you can perhaps
grok the pattern at hand. If we want to count up to
the number we know as three, let’s just change that
rightmost one to a one. So that’s four times 0 plus
2 times 1 plus 1 times 1. That of course is three. Four is perhaps jumping out at you now. We just change that zero to a one, and
then the other two digits to zeros. And now if we want to count up to
five, or to six, or to seven, or to– dang it, what’s supposed to come next? It would seem that in the binary
system, we can only count as high as– what, seven? And that’s a little strange, because
of course, we started at zero, we counted here up to seven, but surely
computers can count higher than that. And that’s fine, just
need another digit. Much like if we wanted to count from
999, in our human decimal world, up to a thousand, which has four digits. Similarly here, do we
need another digit? We need an eights place,
and so we could represent the number we know as eight
with one, zero, zero, zero. But the key here is that
we needed another digit. To put it more mechanically,
we needed more hardware. We needed another physical place,
at least in this depiction, to actually store that one. And now we begin already to hint at a
connection between this digital world of zeros and ones, and the hardware
world in which it’s typically incarnated. And by that, I mean, we
need to decide, ultimately, how and where to store
patterns like this. And you know the nice thing about
binary only having two values, is that that effectively,
means you have just two states. And you might think of these two
states as something being on, or something being off. And maybe we might think of something
being on as a one, and something being off as a zero. And so just with two states,
can we have these two extremes. And maybe it’s not on or off, maybe
it’s true, or false, or black, or white, or red, or blue. It doesn’t even matter what
we call the two states, the key is that we have two of them. And you know In the physical
world, the simplest thing I can think of to turn on and off,
is perhaps something like this. Just a light bulb. This here’s a little
desk lamp, and in fact, if I go ahead and clip
this on here, and let me plug this into an
electrical outlet so that I’m getting some additional input if
you will, electricity or electrons, this lamp right now I claim is
representing the number zero. It’s completely off, and I’m just going
to agree, to agree with you, that this shall represent zero. But you know what, if I want to
represent a one in the physical world, just going to turn it on. And so now we have something that’s
on, or true, we’ll call that a one. Zero, one. Of course, we’re not really
counting all that high just yet. If I want to count higher than
zero to one, to something higher, I’m going to need another light bulb. I’m going to need more hardware,
more memory, if you will, in the world of computers. So let’s actually now give
myself a second zero or one. Plug this thing in here. Give it some electricity as
well, which again, is really one of the few physical
resources we have in a computer, whether it’s coming from
a power cord or a battery. And so now, if I want to represent
the number zero, here we are. But I’m doing it really with zero zero. This now is going to be one, this now
is going to be two, and this, of course, is going to be three. And let’s not stop there. Why have two desk lamps when
you can have three desk lamps. If we instead make a little
more room for here, and we want to instead now count
not just as high as three. Let me go ahead and plug-in
this third and final desk lamp, and go ahead and turn this on. And of course, we instantly
go from three to– not quite instantly because
you have the hands– to the number four. And so forth. So what’s now the connection
between the digital and the sort of analog
world of light bulbs, and the physical world of computers? Well inside of a computer is a whole
bunch of tiny, tiny little bulbs, so to speak. In fact, you can think of what’s inside
of your computer is exactly this. So many little light bulbs
that are either on or off. And thanks to those little light bulbs,
can your computer represent numbers? Zero, one, two, three, four, as many– as high of a number as it wants so
long as it has enough little lights. Now of course I’m oversimplifying. It’s not actually lights that you
have inside of your computer, rather, you have just the switches. These switches being called in
the computing world transistors, as you may have heard. Indeed, one of the things that companies
like Intel are increasingly doing, is packing more and more transistors
into their CPUs, central processing units. The brains of computers. And with those additional transistors,
can they store even more values, or equivalently can
they count even higher? And so now, even though we
began the discussion down here with just zeros and
ones in the abstract, now we’ve made it a little
more physical, in so far as we can represent those zeros
and ones with something physical, drawing electricity to power
these kinds of light bulbs. Of course, we can now
miniaturize that and consider these light bulbs to really be, what
we’ll call in the computer world, transistors. But at the end of the
day, even though we have now a way of
representing information, the zeros and ones, even
though we have a way now of representing even bigger numbers
by using even more transistors inside of our computer, we’re still
talking only about numbers. And with my computer I want to
do more than just use something like Microsoft Excel. I want to do more than
just do math on my data. I want to actually store
things like letters, and words. Let alone, colors, and
images, and videos, and more. So we need to abstract higher. So again zeros and ones, we know
how to represent it, now let’s build on top of the zeros and
ones and start to represent something more interesting. Something more
alphabetical, if you will. And so this gives us ASCII,
the American Standard Code for Information
Interchange, or more modernly referred to as a superset of Unicode. Turns out, human some time
ago, decided on a mapping between letters and numbers. Somewhat arbitrarily,
but in a way that’s convenient when it comes to actually
programming, things like this. And this is to say that
humans time ago decided, you know what, we are going to represent
the letter A using the decimal number 65. Now what does that mean? Well, this means that if your computer
is to store the letter A, or the letter B, or the letter C, it simply
has to store ultimately the number 65, or 66, or 67. What does it mean to store
number like 65, 66, or 67? Well that just means to store some
pattern of bits, some pattern of bulbs as we did a moment ago, and turn
them on and off in such a way that you’re representing in binary,
the decimal number 65, 66, 67. So if you think about something like
Microsoft Word or Google documents, or any program in which you
type text, what you’re really doing by typing on the keyboard,
is sending some pattern of signals that’s telling the computer to store
not just the letter ABC per se, but really to store the
number 65 or 66 or 67, or really, to store the
pattern of zeros and ones that ultimately represent
those same values. So again, this spirit
of layering binary now becomes ASCII, or Unicode,
something higher still. And so with this can
we represent messages? For instance, if I wanted to represent
a message like this, a familiar message, there say, I might store
these three values. 72, 73, and 33. Now what is that? Well turns out if I look back at
this pattern here, where 65 is A, and in tens 72 is H, and 73 is I, well
what are we really representing here? It would seem we’re
representing the pattern H I, and then you wouldn’t
know this from that chart, but if you look at
another online reference you’ll see a 33 is an exclamation point. So now we have the word
Hi or the exclamation Hi. But that’s in the context of a text
editor, or word processor like word. Suppose, instead, you
were using not a text editor, but something like
Photoshop, or MS Paint, or some other graphical program. Well instead, you might have
that same pattern of numbers, or really bits at the end of
the day, but in this context, something like Photoshop,
these numbers are meant to be values between 0 and 255. Turns out, long story short, that
if you have eight zeros or ones, where zero or one, you
know what, let’s just start calling them by their formal
name bits for binary digits. If you have eight bits, you can
count from 0 all the way up to 255. And the quick math there
is 2 to the 8, means you have 256 possible
permutations of zeros and ones. So therefore, if you start counting at
zero you can count as high up as 255. And so in the context of a graphics
program, you can think of 72 in so far as it’s not quite halfway between zero
and 255, it’s a medium amount of red and a medium amount of green. Not too much blue. Where zero means none of this color,
and 255 means a lot of this color. So if you had a pattern of bits,
and in-turn numbers, stored inside of your computer for the
purposes of a graphics program, it’s really like telling the computer
give me a medium amount of red, give me a minimum amount of green
and just a little bit of blue, and combine those like paint,
or like frequencies of light., until you get the
summation of those, really, are the combination
really of those, which is this murky shade here of yellow. So again, using the
same patterns of bits, can we represent either letters
and words and paragraphs, or in another context all together,
could that same pattern of bits still represent numbers, but be
interpreted not as letters and words and paragraphs, but as colors. If you treat each trio of 8 bits
as representing some amount of red, some amount of green,
some amount of blue, otherwise known as, if you’ve heard
the term, RGB, for red, green, blue. So this principle of starting
simple, and gradually making things more and more
and more complicated, is really a principle of abstraction. Because at this point
in the story, when we’re talking about words and paragraphs
and essays and documents, or in another context we’re
talking about images, or maybe even movies and more, we no longer
really need to care about, or even need to know
about, or understand, what’s underneath the
hood those zeros and ones, because we’ve abstracted
away from that lower level. And this principle of
abstraction, layering idea on idea on idea on idea such
that you no longer need to worry about how the lower
level ideas are implemented is nice, because it allows
us humans to focus only on the problems we
really care about, which in theory are those top most problems. The ones that are immediately at hand,
that we’re building solutions to, on the shoulders of, computer
scientists, and engineers, and just colleagues that
have come before us. And we don’t have to
get lost in the weeds, so to speak, of the earlier complexity. And so this is a powerful
problem solving technique, and indeed it’s a principle that
we’ll see applied ultimately in the world of programming as well. Now let’s try something. Speaking of abstractions,
let me encourage you at this point to take out a piece
of paper if you have one there. And surely, if you don’t
have one right there, surely you could pause this
video and actually go dig one up. Grab a pencil too, or pen. Yeah, Ill wait. Now you could just pause this,
I can’t wait all that long. Let’s assume at this point in the
story you’ve got that piece of paper, and a pencil or a pen, and
let’s play a little game. I of course can’t really
see what you’re doing. But I’m going to hope that you
either do or don’t do what I do, because either way it
will be instructive. And I’m going to leverage
some abstractions here, for better or for worse. I want you to go ahead, and please
don’t be one of those people like me who’s just following along
pretending like all right, I have the piece of paper, I have the
pencil, this is what I would be doing. Actually do this. This will be kind of fun for one of
us in the end, if this works out. Go ahead now, on that piece of paper,
with your pen or pencil, and go ahead and just draw a circle. OK. All right. And below that circle draw a square. All set. All right, and below that
square draw a triangle. Now odds are, you know exactly what
I meant when I said draw a circle, and perhaps you did a
little something like this. Or a little more perfect
than my circle there. And then beneath that
I said draw a square. And you just intuitively
know what a square is, so you might have
drawn a square like this. And then the third thing I
said was draw a triangle. And so you might have drawn a
triangle that looks like this. But immediately, ant that looks
curiously like part of a jack-o-lantern now. But curiously, there’s
some ambiguity there. Right, a circle is kind of a circle,
but I didn’t specify the radius or diameter, so maybe yours is
bigger, maybe yours a smaller, maybe it’s over here on your paper,
maybe it’s over there on your paper. So already, these abstractions
are useful in that you immediately knew what to draw, but you didn’t
really know how to draw it. Similarly, this square, I don’t know
why I drew it a little smaller here, but it’s indeed smaller,
and it’s barely a square. But it’s meant to be a square. But there’s a gap between it and the
circle, but I didn’t really specify. So there, too, the
abstraction is valuable in that you immediately knew how to
draw a square, but not where to draw it. Or in what size to draw it. And lastly, the triangle,
perhaps the most, the juiciest opportunity
for ambiguity, I didn’t tell you how to
orient that triangle. Maybe you, instead, did
something a little different, where your triangle
wasn’t drawn like that, with the pointy part at the bottom. Maybe you, instead, did
something like this. Or maybe it was somewhere
else on the paper altogether. So now at this point in the story, you
could have followed my instructions exactly as I described, but
we could still somehow come up with different solutions. And in fact, if I can now spoil
what the actual task at hand was, this was the picture I was describing. This picture here has
a circle, below which is a square, below which is a triangle. But that leaves out some key details. And the curious thing here, is that
even though abstraction is a useful mechanism, once you start to move away
from those implementation details, if you will, you very quickly
realize that I don’t really know what you’re telling me to do, necessarily. And the challenge is, that computers,
as complicated or intimidating as they might seem to you, they’re
really not all that bright. Right. They can only do what they
are explicitly told to do. And so if you, the human,
or you eventually perhaps, the programmer, don’t
actually specify absolutely precisely what you want the computer– or the human in this
case– to do, you might not get the output, or the correctness of
a solution, that you’re hoping for. In fact, let’s try one
other, and let’s see what the other extreme might feel like. So on that same piece of
paper, maybe on the flip side or another sheet of paper, let’s
play this game just one more time. And this one’s going
to be a little harder. I’m going to try to tell
you exactly what to do. So lesson learned,
that was too abstract. Let’s now drill down on
the implementation details. OK. So let me think like a computer
might, or I think a computer might, go ahead and put your pen or
pencil down on the piece of paper toward the top middle of the page. Now from that point, move say Southwest
to halfway down the piece of paper. So really at a 45 degree downward angle. And then go ahead and move south
east, or a different 45 degree angle, toward the bottom of the page. So you’ve kind of sort of made
the left half of a triangle, or not really that, 2/3 of a
triangle, two sides of a triangle. But stay where you are. At this point in the story your pen
is probably below your original dot. But you’ve drawn two
lines that form an angle. From where your pen now
is, draw a line Northeast, or in an upward and
to the right 45 degree angle, to the same height
as your previous line. And then double back and go say
Northwest, or a different 45 degree angle, still back to the original point. And at this point in the story, you
have really either nothing at all, or you have a diamond. And therein lies a curiosity too. I could have just said diamond,
draw a diamond, or draw a kite. Which would be an equivalent shape. But that too lends itself to same
ambiguity, so I drill down deeper. But my God, it’s taken us just a minute
or more just to get to this point. And we’re not done yet. We’re not drawing a diamond or a kite. Now you have a diamond or a kite, with
a top vertex or point, a bottom one, a left and a right. Move your pen to the left one,
and draw a vertical line down. Now go back to the diamond or the
kite, and on the right vertex or point, draw similarly a vertical line down. And now, in that original diameter kite,
at the bottom most vertex or point, draw a vertical line down. And now, if you followed along
with these very precise machine instructions, you’ve got three vertical
lines that are just kind of dangling. I don’t even want to mislead you with
any hand gestures, three vertical lines that are dangling, go ahead
and draw two lines that connect the ends of those three lines. Oh my God. Like it’s so complex to do what we just
did, and I would put money on the fact that you did not draw correctly,
what I was trying to get you to draw, which is just a cube. Right, a cube is a wonderfully
simple abstraction. A shape with which you and I
are probably long familiar, and it’s so easy to say draw a cube. But as we saw before with the circle
and the square and the triangle, just saying draw a cube is ambiguous. At what angle should it be oriented? How big should it be? Where on the piece of
paper should it be? And so I was trying to
be so much more precise this time by having you put
your pen down at the top, go down to the southwest
and draw this line, then go down to the southernmost point
here, then another Northeasternly line, and then a north westerly line. And that just got us to the kite. But the takeaway here,
is that when it comes to making a computer
do what you want to do, you can’t just speak these abstractions. You actually have to implement
them, or program them, or code them at least once. In fact, some of the earliest graphical
programs in the world of computing, were kind of as low level as this. There was an old programming
language called logo, in fact, that allowed you to
program by moving a cursor, like a turtle of sorts, up and down
and left and right on the screen. And putting either down
or up a marker of sorts, and that you could draw shapes like this
by just moving around on the screen. But to draw things like this clearly,
as in our verbal example here, you have to be so darn precise. And it just gets so tedious so quickly. It certainly would take all of
the fun out of using a computer, or all the fun out of using
programming a computer, if you had to do this every time. But that’s where there’s an
ingredient here to be leveraged. One of the things that a computer
scientist, and a programmer, and engineers, more
generally, very often do, is they absolutely implement these
kinds of low level details once. They go through those very
methodical, if mundane, steps of getting something just right. And then they save the
instructions they wrote. They save the programs
they wrote, if you will, so that they can reuse them later. And the fancy words for these
things will eventually see are called libraries. Or functions. Or other names still. So once one human in the world has
implemented a program, if you will, with which to draw a cube, similarly
can we stand on his or her shoulders and reuse that same routine. And hopefully, they were clever
enough to allow us to parameterize it. To customize it, by maybe changing
the angle and the size and the depth and so forth. So it doesn’t just have
to be that one cube. And so here we have a wonderfully
powerful problem solving technique. Abstraction. Which allows us to say what we mean,
and the rest of the humans in the room just immediately understand– at
least after some instruction– what it is we’re talking about. But with computers being these
very little literal devices, we can only talk at those
levels of abstraction once we’ve actually built up software,
implemented solutions to get us to that point in the conversation. And this is why, at first glance,
using a phone in your pocket or a computer on your desk might
actually seem super, super complicated. There’s so many moving parts. And absolutely there are. Windows and Mac OS are
literally the result of millions of lines of programming code these days,
having been written over the years. And so of course it’s to be expected
that you might be a little daunted or overwhelmed by the
apparent complexity. But one of the goals
here for this lesson, is to really help you appreciate
that beneath all that complexity, is a simpler idea. And then an even simpler idea. And then a very simple
idea, and so forth. And so once you sort of bottom out
and understand those first principles, zeros and ones, binary on top of which
might be Ascii or Unicode, on top of which might be some
other encoding still, can you resume the current
conversation and understand that what might have looked
completely complex at first glance, is really just the result
of assembling, if you will, a whole bunch of pretty
simple puzzle pieces. So at this point in the story, we now
have a way of representing information. But now let’s just stipulate. We know how to represent information. At the end of the day, Yeah it’s
binary, And at the end of the day you can think about it as decimal, and
maybe you’re using Ascii in Unicode, or maybe you’re using
graphics, or whatever is going on underneath the hood. All we need to know and care
about now is that you can do it. And we don’t really have to think
too much more at that level. Now we can resume our look
at the overarching model at hand, which is problem solving. We now have a way to represent
our inputs and outputs. What then is inside that black box? Well the buzzword du jour
these days is perhaps algorithms, where even if you
don’t necessarily know what it is or how to make one, or how to use one
in the context of a computer program, algorithms seem to be increasingly
the solution to all of our problems. Well an algorithm isn’t
all that complex, fancy though the word might
sound, it’s really just step by step instructions
for solving a problem. And those steps can be in English, or
they can be in something we’ll call pseudo code, sort of code like but
it’s not really an actual language, or can be in Java, or C,
or c++, or JavaScript, or any number of other
programming languages. Algorithms are, again, just sets of
instructions for solving a problem. Well what’s one such problem
we might want to solve? Well in the real world we might have– the real old world shall we say– we might have a problem that once
upon a time looked like this. A phone book with a whole lot
of pieces of paper inside of it, on which were a whole bunch of names
and a whole bunch of telephone numbers. And the phone book was
alphabetized from A to Z typically. And maybe there were some other sections
like the yellow pages, or apparently the red pages, whatever this is here. But we’ll just assume that
these are the white pages, so to speak, with just a whole
bunch of humans names and numbers. So suppose I want to
find one such human, a human whom we’ll call Mike Smith. How do you go about finding
Mike Smith in this phone book? Well I could, somewhat stupidly,
but arguably quite correctly, start at the beginning of the book. And I see here instructions
for calling 911. If I move on to page two, I now
see someone’s names and numbers. But these people’s
names all start with A. And so I continue going
through the A section. And the A section. And then eventually I
get to the B section. And the B section. And the B section. And then the Cs, and the Ds
and the Es and Fs and so forth. And eventually, tediously but correctly,
I’ll get to the Ss in the phone book. And if I see Mike Smith here, I can now
pick up the phone and call Mike Smith. Now no one out there, if you’ve
been still use this technology, is going to have looked
up Mike Smith in that way. You’re going to fly through this
phone book far faster than I, right, you learned probably in grade
school why count by ones when you can count by twos? So two, four, six, eight, ten, twelve. Sounds faster, is faster. It’s going to get me to Mike faster,
but is it going to get to me to Mike correctly? I’m going twice as fast by
doing two pages at a time. So I’m going to have
flip half as many times. But there’s actually a bug, so to
speak, a potential mistake here. What is that? Well in my cleverness
to get to Mike’s name twice as fast, what if I
go ever so slightly too far, just because by bad luck, Mike
is sandwiched between two of the pages that I so cleverly was
skimming two at a time? Of course I’m looking at
this side, maybe this side, but maybe Mike is in the middle. And so it turns out with that
algorithm, that twosie approach, am I going to have to have a
little bit of a check at the end? Such that if I hit like the T section,
and see a name starting with T, I better wait a minute,
let me double back, I might need to go back at
most one page to make sure that I didn’t actually miss Mike Smith. So at the end of the
day, it’s not correct if you naively just do
two pages at a time, but it is correct if you
do two pages at a time, with one final reversal by
a page, just to make sure once you go past SMITH
in the phone book, that you didn’t accidentally
miss Mike just one page prior. So it’s still super fast, you
just need that one little check. But still, no one out there, is going
to look up Mike Smith one page at a time, two pages at a time. You’re going to open in the
middle of the damn phone book, look down and see, oh, not in the S
section yet, I’m in the M section. And so what you intuitively know
how to do since growing up perhaps, is that you know Mike is not
in this half of the phone book. Mike is clearly in this
half of the phone book. And so at this point you can
figuratively– but in our case literally– tear the problem in half. Throw half of the problem
away, and be left with, we single use phone book, and half at
that, but half the size of the problem. So if we had 1,000 pages originally,
now maybe I’ve got only 500 pages. And so I can repeat this intuition. Jump roughly to the middle. Darn, I’m a little too far
now, I’m in the T section. Again, let’s tear half the problem
away, throw it away as well, and now be left with a 250 page problem,
which can now be 125 page problem. Which is getting easier and easier
and easier, until we repeat, repeat, repeat, repeat. Until theoretically, we’re left
with just one page in the end. Maybe Mike’s on it, maybe Mike’s
not, but if he’s in the phone book, he will be on this page. So how efficient was that. Well if that phone book had 1,000
pages, in my first algorithm it might have taken me what, like
700 plus steps to get to Mike? Or in the worst case 1,000
steps, right, it’s alphabetical. But maybe it’s not
Smith, maybe it’s someone with the last name that starts with Z.
In the worst case in that first phone book, maybe it would take me 1,000
steps maximally to find Mike Smith. Pretty slow. What about that second algorithm
where I was going two pages at a time? Well, with that algorithm, it’s
going to take me like 500 steps maximally to find Mike Smith. That’s twice as fast,
that’s pretty good. It’s not nearly as amazing as
the algorithm we settled on. The intuitive one, arguably,
where I divided and conquered. I have the problem again
and again and again. Because if I start at 1,000, and I go
to 500, then 250, then 125 and so forth, rounding as needed, I actually
get to one page much faster. Put another way, how many times
can you divide 1,000 in half before you’re left with
just the number one? Well if you do the math, either
in one direction or the other, you’ll see that it’s roughly ten. In fact, if you want to pause even and
grab a calculator, or a piece of paper, or pencil, or just think through it
in your head, you can start with 1,000 and go to 500, 125, and so forth. And you’ll eventually
hit one, after just 10– give or take, depending
on how you round– steps. That’s pretty powerful. But not that big of a deal. Right. Ten still is like a lot of page turns. But what about an even bigger problem. The types of problems that Google,
and Microsoft, and Facebook, and Oracle, and really big
companies deal with that have lots and lots of data. Suppose, for instance, that I’m
searching through not a phone book, but a database. A big program that stores
lots and lots of data. And suppose the data that’s being
stored is still names and numbers. How much time might it take to
find someone like Mike Smith, in a database that’s got like 4 billion
names and numbers in it somehow? Well, four billion names and numbers. Well if we use that
first algorithm, might take as many as four
billion steps to find Mike Smith in a really big database. In a really big computer
program, that’s not too smart. But if I instead use
the twosie approach, flipping through two
database records at once, maybe it’s not 4 billion operations,
maybe it’s just 2 billion. That’s good. That’s half as many operations. But what if I use this
super clever intuition that I kind of grew up with here, with
that divide and conquer algorithm. Well, I can start with 4 billion
database records, go to 2 billion, then 1 billion, then 500 million, 250
million, 125 million, and so forth. I’m getting to one much, much faster. In fact, I can only divide
the number 4 billion in half, roughly 32 times total. Again, depending kind of sort of
on how you round, but 32 times. 32 is so much smaller
than 2 billion steps. And 32 is certainly smaller than
the original starting point, 4 billion steps. So this is a really powerful
problem solving technique to divide and conquer. And here, too, even though what
computers might seem to be doing these days is super complicated
and sophisticated– and it is in many ways– but some of the ideas that those
computers and the programmers who program them are leveraging, are
actually pretty familiar to us already. Inside of this black box might not
be something super fancy, but just a clever adaptation of
some of your grade school human intuition to the
context of a computer program. Now it’s one thing to talk
about algorithms, especially if we’re just spit balling it verbally. But computers, of course,
need us to be more precise. And they need us to state our
thoughts more methodically. So what does this mean? Well, let me propose that we write
some code, or really pseudocode, for this same algorithm, where
we’re looking for someone like Mike Smith in a phone book. And it’s pseudocode because it’s
not going to be Java, or c++, or JavaScript, or anything else. It’s going to be English like syntax,
that’s kind of sort of like code. And before long, we’ll see
some actual code as well. But step zero, and just
to be playful here, I’m not going to start counting at one,
I’m going to start counting at zero, just because with any
number of bits, or digits, the lowest number that I could
count with is of course zero. Pick up phone book is the
first thing that I did. One, open to the middle
of the phone book is the second thing I did in
that third and final algorithm. Look at the names was the next thing I
did, looking down at that phone book. And then if Smith is
among names, and notice, this is semantically different
from those first three steps, because this expression starts with if. So this is kind of like the
proverbial fork in the road, if Smith is among the
names, let’s do this. What do we want to do? Call Mike, that’s great. Otherwise, or else if Mike
is earlier in the book, let’s go a different direction instead. Let’s instead open to the middle of
the left half of the book, all right. So that would be the left half
that I threw away earlier, and then go back to step two. Because once I have opened to the
middle of the left half of the book, I don’t have to actually
dramatically tear it. I now need to look for Mike’s
name again, as per step two. Else if Mike is later
in the book, I actually want to open to the middle of
the right half of the book, and then go back to step two as well. Now you might think that’s
everything to this program. But there’s actually a remaining step. Indeed I’ve got room left on the
screen for a remaining step or two, but there are more than
three possibilities. One of them is that Mike is
among the names, one of them is that Mike is to the left, the
other is that Mike is to the right. What’s the fourth? If I don’t consider the fourth,
and indeed if in a program I don’t implement the fourth,
my program might crash. My computer might hang. My computer might behave
in an unpredictable way, because if the programmer wasn’t
so precise as to anticipate something that might happen, who
knows what the computer might do. And indeed, that’s often
why your own computer might have a little spinning
beachball, or icon, or it might crash outright or freeze. It’s because something
unanticipated happened. So let’s be precise. There’s a fourth and final
scenario I can think of, which perhaps on your
mind too, just quit. Because in the fourth scenario,
if Mike’s not among the names, and he’s not to the left, and
he’s not to the right in the book, he must not be there. And so let’s avoid just hanging
infinitely somehow or other, by actually proactively
deciding to quit. But now let’s tease apart what some
of these terms actually are now. So in yellow are some things that
really just look like verbs, or actions. And we’re going to call those
statements, or more specifically functions, or procedures would
be a reasonable synonym too. And each of these yellow
terms is really a call to action for the computer to
just do something unconditionally. But sometimes, we want that computer
to do something conditionally, as evinced by these yellow terms now. If, and else if, and else and else,
kind of paints the picture of a four-way fork in the road. Where each of these
branches, or conditions, leads us to take different action. And you’ll see that I’ve indented lines
four and six and seven and nine and ten and twelve, because
they are meant to happen only if lines three and five
and eight and eleven, or eleven, actually applies. So those indentation kind of
captures the logic of this program. Lastly, or second to last there is this. This is what we call a little more
fancily, a Boolean expression. These yellow phrases here
are kind of like questions. There are either yes no, or
true false, or one and zero or any number of other binary terms. But these are questions we’re asking. The answer to which is
going to be true or false. Smith is among the names, true or false? Smith is earlier in the
book, true or false? Smith is later in the
book, true or false? And so these Boolean
expressions, named after someone who the last name of
Bool, long ago, is a way of having conditions take you
in a different direction based on whether something is true or false. Three such examples there. And then, lastly,
there’s these two lines. On seven and ten there’s
this expression go back to step two, which is to induce
a bit of cyclicity, right. You can sort of think about it
visually if you go from step seven, or ten for that matter,
back up to step two. This might happen again,
and again, and again, if Mike is still to the
left half, the left half, the left, as you’re whittling
down the phone book. And so we’re going to induce, and
induce, and induce potentially, this cycling or looping behavior. So these lines here
now in yellow represent what a computer program
might call a loop. Now these same English phrases we’ll
eventually see can be translated into Java, and c++, and
JavaScript, and Python, and Ruby, and other languages still. But the key takeaway
for us here today is one, the precision with which
we specified these steps, two, the fact that there’s this ordering,
what happens after the other. The fact that there is
these conditions, some only happen if something is true,
and the fact that some of them can happen again, and again, and
again, based on some kind of looping. But is this good? Like this is correct, and that
of course, was one of our goals with the phone book, initially,
was let’s get it correct, and better still, let’s get
it correct and efficient. correct and fast. But how fast now is this? In fact, how do I put a
number, of really a formula, on the performance of
the algorithm so that I can claim that I am a good programmer,
or I am a good problem solver? I’ve not only solved your problem
correctly, but really, really well. Well let me propose that we
analyze these three functions. Kind of in the abstract. We don’t need actual arithmetic
expressions here, per se. We’ll just do things
variably as follows. So here’s a nice little Cartesian plane,
with an x-axis of size of problem, and a y-axis of time to solve. And the farther out you go on size
of problem, from left to right, means bigger, bigger, bigger, bigger,
bigger, bigger, bigger bigger problem. And by bigger problem I
mean more and more pages. More and more input, whatever
the problem actually is. And then time to solve, is not
very much time, lots of time. So on the y-axis too, the
higher you go, the more time it takes to solve a
problem, or really the slower it is to solve the problem. So let’s now draw this red line here
as a depiction of the first algorithms performance, or running time. Whereby, there is a one to one
relationship between size and time. A one to one relationship
between number of pages, and maybe number of page
turns, or seconds, or whatever your unit of measure happens to be. So that if I have a phone book of this
size, this dot here on the red line is how many seconds, or page
turns it takes me to find it. And there’s a linear relationship
there, as implied by this variable– as we’ll call it– as in algebra. n for number of pages, for instance. It’s linear in so far as Verizon,
if the phone company like Verizon increases the number of pages in the
phone book just buy one next year, a few more people move into town so they
add one more page to the phone book. That might take one additional page
turn to find someone like Mike, or anyone else in that phone
book if Verizon just adds a page. Or if they doubled the
number of pages, it might double the amount of
time it takes to find someone. There’s a linear
relationship between the two. Now with the second algorithm, where
I was flying through the phone book two pages at a time, there’s
still a linear relationship, but it’s not quite as bad so to speak. For instance, if I have this
many pages in my phone book, my first algorithm might take this
many seconds in the first algorithm, but because I’m flying through
the phone book two at a time, it will take me half as much time. Half as many page turns
with that second algorithm. So we’ll describe it
algebraically as n over two. Where n, again, is just
the number of pages. So there is a relations