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