DAVID MALAN: Welcome back, everyone.
So yesterday, you'll recall that we focused on these topics here.
So we had four overarching topics-- privacy, security, and society;
internet technologies; cloud computing; and ultimately, web development.
>> Did anyone have the bandwidth or the time
to watch a little John Oliver last night?
It's actually pretty amusing, if not a little frightening.
Any questions on anything we did yesterday?
Any clarifications?
Any questions that you want to make sure we touch on today in some form?
So clean slate.
>> So what's on the agenda for today?
So I thought we'd begin today with a look at what's generally
known as computational thinking-- at the risk of oversimplifying, thinking
like a computer, perhaps thinking like an engineer,
and trying to start to organize your thoughts
or to give you a better sense of what's involved in actually commanding
a computer to do something by way of programming.
And we'll keep it at a pretty high level, pretty much English,
but try to use of familiar examples to formalize how
you would go about solving problems.
>> And we will revisit some CS topics, like abstraction,
which came up a couple of times yesterday,
algorithms, and then representation.
And that's where we'll begin today in just a moment.
Then we'll take a look at programming.
We'll take a look at some fundamental constructs
with which you might be familiar and might even find quite intuitive.
>> We'll look, in fact, at a sample programming
environment that's very accessible, very playful, and indeed targeted
for ages 12 and up.
We will spend a few minutes there and then take things to a lower level
and actually talk about some of the algorithms and data structures,
so to speak, that programmers typically use
to solve problems far more efficiently than you might
be able to do without them altogether.
Then after lunch, we'll take a look at technology stacks, which is just
a fancy way of saying collections of technologies
that you might use to solve some problem.
And we'll talk about the alphabet soup of languages that exist today--
Java and Python and C++ and PHP and Ruby and all sorts of other things.
>> We'll take a look briefly at design patterns.
Programmers, over time, have adopted methodologies
that tend to help them solve problems more readily.
When you start to see yourself writing the same kind of code again and again,
people formalize those repetitions and ascribe names to them
and then use them and promote them, ultimately.
And we'll talk a little bit about mobile strategies,
like what does it mean to actually make a mobile app or a mobile website.
Do you do it for Android?
Do you do it for iOS?
Do you do it for both of those?
And what are the trade-offs?
And then finally, we'll take a look web programming, which
is a collective term really describing any time
you write software that's meant to run on the web,
whether on phones or desktops or laptops.
We'll take a brief look at databases and the design
therein, if only because almost any interesting web-based application
these days has some kind of database.
Otherwise, it would just be static content.
And a database allows you to make changes over time, whether yourself
or from users.
And we'll consider how you would go about designing
that database and the kind of jargon that might come up in an engineer's
discussion at a white board when actually implementing
an app for the first time.
>> We'll talk briefly about APIs, useful services
that you can use to stand on the shoulders of others, whether companies
or individuals, and solve your own problems more quickly.
And then we'll dabble perhaps a bit with JavaScript,
a programming language that's used both in browsers these days, but also
in servers.
And perhaps, we'll revisit, time permitting,
some of the hands-on web stuff we did yesterday and integrate the two
together before we adjourn.
>> So with that-- what's ahead-- is there anything missing that you
would like to make sure we insert and touch on at some point.
If it's springs to mind, bring it up before long.
But why don't we begin with a look at computational thinking.
>> And let me propose that computational thinking is, again,
sort of the high level description of what a computer scientist might do.
And indeed, let's start with three ingredients that
might go into computational thinking.
This is just one way of describing it.
We could certainly define this in any number of ways.
>> But let me propose, for the sake of today,
that the world's problems, all of the world's problems,
when approached by a computer scientist could
be viewed as what we'll call inputs, which
need to get fed into what we'll call algorithms, which then yield outputs.
In other words, the entire world of problem-solving I claim
can be distilled into these three ingredients.
So what do I mean by inputs?
Inputs is just what you're handed in order to solve.
>> For instance, here's an old school problem.
If I have a phone book here and I want to look something into it,
this is my input.
I have 1,000 or so pages in a phone book.
This is the input to my problem.
And I want to find something like Mike Smith, so a friend
whose name and number is hopefully in this address book.
>> This is before the days of cell phones, so I can't just search for it.
So I have to do it old school and actually search
these inputs for some answer.
And that answer is just going to be called the output.
So the input is the phone book.
The algorithm is whatever set of steps I use to find Mike Smith.
And the output is, hopefully, Mike Smith's phone number.
And this then would be just representative of most any problem
to with you are handed inputs and want to produce outputs.
>> So before we consider the process by which we can solve that problem,
finding Mike Smith and something like that,
let's consider the first and the last-- inputs and outputs.
Physically, of course, the input here is a whole bunch of paper glued together
in the form of a phone book.
But computers, of course-- laptops and desktops and even phones
these days-- those are electronic devices.
>> And at the end of the day, what's the only input to a computer?
Well, it's something like this power cord here.
I plug it into the wall, and I get a flow of electrons,
which allows me to run the machine.
Or maybe those electrons are created by way of my battery.
But at the end of the day, that's the only thing going into my laptop.
And so much interesting stuff is ultimately
coming out, whether by way of the printer
or the screen or audially or the like.
>> So if all we have as our fundamental input to a computer
is electricity, so just electrons going in and or out,
and so how can we use that input to actually represent information?
In other words, how do we get from a simple flow of electricity
to representing actual numbers or actual letters
or actual images on the screen or actual movies or e-mails
or any number of these higher level concepts,
if you will, that at the end of the day somehow
have to be stored in this electronic mechanical device
using only those simple ingredients-- electrons coming in and out?
>> So it would seem that, in the simplest form,
the only kind of states I have in my world, so
to speak-- conditions in my world-- is either
I have electrons flowing, electricity flowing, or I do not-- so on, off.
And let's formalize on and off, as a computer scientist might,
with just 1 and 0.
Let's just describe some arbitrary but consistent number to it.
1 means on, 0 means off.
Or you might also view this as true means on and false means.
You could also do black and white or red and blue.
You just need two descriptors.
And a computer scientists would generally just use 0 and 1.
>> So if that's the case, my only alphabet is consisting of 0's and 1's, how
could I possibly get to even the number 2 in a computer, let alone the number 3
or a letter of the alphabet or an image or a movie?
How do we sort of bootstrap ourselves from this basic principle
of 0's and 1's and actually represent something more interesting?
>> Well, let's put that question on hold for just a moment
and consider something hopefully familiar,
even if you haven't really thought about it in any detail for 10, 20, 30, 40, 50
more years.
This is what?
How would you pronounce that?
Not a trick question.
A number, but what is it?
1, 2, 3, or 123.
And I liked how you said 1, 2, 3, because that's one way of viewing it.
1, 2, 3, it's a sequence of three symbols.
It's pictures that we now have words for.
And if you sort of read them all together, a typical human in English
would say 123.
And that's sort of a higher level concept,
feels like a reasonably big number.
>> But how did we get there?
Well, it might be a while since you've thought about it like this,
but back in my day, I kind of learned this
as the 1's column, the 10's column, and the 100's column.
So as Lakisa says, it is 1, 2, 3, but it's also 123.
But how do we get from the former to the latter?
>> Well, you would typically do in the 100's column, I have a 1.
So that's like saying 100 times 1.
And then in 10's column, I have 2.
So that's like saying 10 times 2.
In the 1's column, I have 3.
So that's like saying 1 times 3.
>> And if I add these things together, this, of course,
is 100 plus the 10 plus 3.
And oh, that's why I get this higher level notion of 123.
It's just basic math, whereby these symbols have weights to them, if you
will, placeholder or column values.
And once I multiply everything out, I get this number.
>> So how many of you know how to speak binary-- 0's and 1's-- like a computer?
OK, perfect, no one, or none of you think you do.
But I would claim you actually know this already.
We just need to sort of tweak our mental model a little bit.
But the process is exactly the same.
>> Let me leave this one up there and instead pull this down for a moment.
In the world of computers, we only have 0's and 1's.
And so the thing that's going to change is what?
Well, in my human world, the decimal system, dec meaning 10,
I have how many digits at my disposal?
10, right?
0 through 9, of course.
>> And that's why we have the 10's place and the 100's place.
Where is that coming from?
Well, this is 10 to the power of 0.
This is 10 to the power of 1, 10 to the power of 2, and so forth.
You just keep multiplying your columns by 10, starting off with just 1
in the rightmost one here.
>> So in the world of computers, if you only
have binary-- bi meaning 2-- or 0's and 1's, we just
really need to change the base of that math.
So in other words, now we'll just have the 1's column and the--
where is this going-- the 2's column, the 4's column, and maybe beyond.
Why is that?
Well, this is 2 the 0-th power.
This is 2 the 1.
This is 2 to the 2, and so on.
>> So whereas here, we have 1, 10's, 100's, 1,000's, 10,000's, 100,000's, 1
millions, and so forth, here we have 1, 2, 4, 8, 16, 32, 64.
You just keep multiplying by 2, instead of keep multiplying by 10.
So now, if the goal at hand is to represent
numbers using only 0's and 1's, let's consider how we get there.
>> This, of course, is the pattern 0 0 0, but what number conceptually
does it represent?
Well, 4 times 0 plus 2 times 0 plus 1 times 0, let's add those together.
4 times 0 is, of course, 0, plus 2 times 0 is, of course, 0 plus 1 times 0
is, of course, 0.
So ah, this represents the number we humans know as 0.
>> Well, now, let's very quickly fast forward.
If I'm instead not representing 0 0 0, but let's do 1 0 1,
that might be how Lakisa, earlier, would just pronounce it 1 0 1.
But now, how do we take it to the higher level the number we humans might know?
So what is this number?
It's 5, the number we know as 5.
>> Well, why is that?
Well, we can really sort of walk through it methodically
4 times 1, 2 times 0, 1 times 1.
Add those together, so this is 4 plus 0 plus 1.
And that's, indeed, 5.
So it's getting a little tedious now doing the arithmetic again and again.
But the process is exactly the same.
>> The only thing that has changed in our world
is that our columns are 1, 2, 4, 8, 16, and so forth, instead of 1, 10, 100,
1,000.
And that's just because our alphabet has shrunk from 0 through 9 to just 0 to 1.
>> So as a little quiz here, how would you represent the number 7 in binary?
0?
Well, 0, you mean 0 0 0?
Say it again , Karina.
Perfect.
Why is that?
It's effectively 4 plus 2 plus 1.
So good.
>> How do we represent a little another-- how about number 2?
Close, but backwards.
So what is this?
Is 4 plus 1, so that's 5 again.
>> So what's-- I'm sorry, Karina?
0 1 0.
0 1 0 would be 2, because again, even if it sort of doesn't jump out at you,
just do the math.
4 times 0, 0, 2 times 1 is 2, 1 times 0 is 0.
So this is the number we know as 2.
>> How about the number 8?
Hm?
Good.
So we kind of need another placeholder.
We need 1 0 0 0.
And that's true of our sort of old school decimal system.
How do you represent the number 1,000?
>> Well, you would seem to be kind of in a tough spot,
if ask you to represent the number 1,000,
because even if you give yourself like 9 of these, 9 of these, 0 of these,
which is the biggest number you have, you didn't quite get to 1,000.
So if you 1,000, you just need another position, so that you can do 1 0 0 0,
ergo the number 1,000.
>> So now, let's map this sort of conceptual discussion back to hardware,
where again, the input was just this little power cable, electricity
coming in and flowing out.
And so for that to be mapped from here to there, well, what do we really need?
Well, you can think of being inside of a computer, a whole bunch of light bulbs,
if you will.
They're really called transistors.
And transistors are just switches that can either be on or off.
So you can think of a transistor that's on
is allowing electricity to flow and a transistor that's off as stopping
electricity from flowing.
And rather than take over the lights here,
why don't I do this sort of new school style.
So this might be a 1, a flashlight being on, only barely though.
And this might be a 0, and now it's off.
>> So using this physical device, I can now represent the binary system.
I just need two states.
It doesn't matter what color it is or what it is.
All that matters is that I have one state on and another state off.
So using my phone here, how do I represent the number we know as 0?
Or put equivalently, what number am I representing now?
0, because the device is off.
>> And if I do this?
And now, how do I represent the number 2?
Can I borrow your phone here, as we did yesterday?
So let's see, so if I want to represent the number 2, is this the number 2?
No.
What number am I accidentally representing here?
This is actually the number 3.
>> So which one do I want to turn off?
The black phone or-- well, if they're-- black phone or the white phone?
The white phone.
So if I turn this off and we line it up over here, we have a 1
in the 2's place and a 0 in the 1's place.
And so I'm now representing the number 2.
And this, Of course, would be the number 3, because now both of these lights
are on.
>> And I'll stop here, but it stands to reason
if I want to represent the number 4 or 8 or higher,
I'm going to need more phones.
But that's all that's going on.
So if you've ever heard that inside of a-- thank you-- computer
is millions of transistors, that's just millions of tiny little switches.
And they're not light bulbs that turn on and off,
but they do either allow electricity to flow somewhere or stop it.
And so there's your two states-- on or off, on or off.
>> So we would seem now to have this ability
to represent this concept that we'd like in actual hardware.
But all we have now is the ability to represent numbers it would seem.
So how do we go about representing letters of the alphabet, which
feels like the next sort of feature you would want to add to a modern computer
once you have numbers?
>> And indeed, if you think about it, historically, computers
were introduced really to serve as calculators numerically.
But of course, these days, they do much more.
Even when they boot up, you typically see one or more words.
So how do you represent words, if all you have is, again,
electricity at the end of the day, or equivalently 0's and 1's?
>> Yeah.
Yeah, I mean, we kind of did this yesterday in some form,
where at some point, I think I arbitrarily
said that, if we want to represent the letter A, we could just call that a 1.
It was in the context of cryptography, where we just needed some kind of code,
some kind of mapping.
>> So maybe A will be represented as a 1, and B will be represented as a 2,
and Z will be represented as a 26, for instance.
And then the only caveat is that if I'm going to encode letters in my emails
or in my text messages as numbers, you all
have to agree to use the same set of conventions.
And indeed, the world has done exactly that.
>> There is a system in the world called ASCII, American Standard
Code for Information Interchange, which is simply a decision some years
ago that the humans made that decided that A is going to equal, not
1, 2, and 26, and so forth-- it's a little different-- but 65, 66, 67.
And I'll pull up a chart in just a moment.
But it's arbitrary.
But it doesn't matter that it's arbitrary.
The world has to just be consistent.
>> Now, more recently, there's something fancier
called Unicode, because the world's kind of realized, after inventing computers,
that there's more than well 256 symbols in the world
that we might want to represent, especially when you introduce
Asian languages and other symbologies that need more expressiveness than you
can fit in the earliest version of this code, which was called ASCII.
So Unicode actually allows you to use more 0's and 2.
In particular, you keep hearing the word bytes in society and even just
yesterday.
And a byte is what again?
>> What's a byte?
It's just 8 bits.
So what does that really mean?
Well, that means, earlier, when we were talking about binary and I was using
arbitrarily three bits when we were talking about binary-- the 1's place,
the 2's place, and the 4's place-- well, a byte just means that you're talking
not in units of three but four, five, six, seven eight,
which gives us 8's place, 16's, 32's, 64's, and 128's.
>> In other words, a bit isn't all that useful a unit of measure,
because it's just like one tiny little piece of information, on or off.
So some years ago, the world just decided
it's slightly more convenient to talk in terms of bytes, eight things at a time.
And so thus was born the notion of a byte.
And so we have eight bits here.
>> And it turns out, too, for similar reasons, the world decided years
ago that to represent an ASCII letter, you're going to use units of 8 bits.
So even if you don't need that many, you're
always going to use 8 bits to represent a letter of the alphabet.
And this is convenient, because then if you
receive a message that has a 0 0 0 1 1 1 1 0 followed by another 1 1 1 0 1 0
0 1, so if you receive 16 bits, the world can just
assume that the first 8 are one letter and the second 8 are another letter.
>> Doesn't matter how many there are.
It just matters that we're all consistent
when we're interpreting these bits.
And this was just random.
That means something, but I didn't really think about what it means.
>> So it's a small white lie.
Originally, ASCII actually used only 7 bits.
And the eighth bit is called extended ASCII.
But the point is, ultimately, the same.
The world generally standardized on 8 bits.
>> So this would seem to be a little limiting, because I can only
represent capital A, capital B through capital Z.
But indeed not, if I go to-- there's a bunch of resources
online, for instance, asciitable.com, this
is going to be a little overwhelming at first.
But I'll point out what's important here.
>> This just happens to be-- and I'll walk-- let's see, if I go over here.
Here is, in the decimal column, the number 65.
And on the right hand column letter character, Chr, is the letter A.
And you can ignore, for now, everything in the middle.
This is hexadecimal, octal, and an HTML code.
To this site is just trying to throw a lot of information at you at once.
But all we care about is the decimal column and the character column.
>> So by this logic, what is the number that the world
has decided represents a lowercase a?
Yeah, 97.
And just to confuse potentially slightly,
what number has the world decided would represent the number 1?
Right, because we-- 49, it seems here, down in the bottom left.
>> Now, what do I mean by that?
So it turns out that in computer systems,
there is generally a fundamental difference
between a number and a character.
A number is the thing we learned growing up when
we were super young in grade school.
It's things you count with.
But a character is just a shape, a glyph, so to speak, on the screen.
>> Now, we humans sort of see something that looks like this.
And we say, oh, that is the number 2.
But no, that's just a symbol that looks like what we know as the number 2.
And so there's this fundamental distinction
between actual numbers and characters.
This is a number.
But generally, in the context of a computer,
if you instead see something like this quoted--
and you don't always have to see it quoted,
but for the sake of discussion-- if you see quotes around the number,
this is now a character.
So this number 2 underneath the hood inside of a computer
would be represented with a pattern of bits that represent the number
50 according to the chart online.
>> However, if a computer just sees this, this
would be represented with the pattern of bit 0 0 0 0 0 0 1 0.
Whereas, this character would actually be represented as-- and now,
I got to think a little harder-- so this character would be represented with 0
0 1-- what do I need here?
0 0 1 1 0 0 1 0.
How did I do this?
Well this is the number 50, if you multiply it out using these columns,
this is the number 2, and so that's why there is this dichotomy.
>> And this is just a teaser now for features
that exist in programming languages that we'll touch on briefly later today.
In programming languages, you have generally,
but not always, things call different data types.
In other words, a programmer-- when he or she is writing,
a programmer gets to decide in what format to store his or her data.
You can either store data as raw numbers, like the number 2.
Or you can store them as strings, or sequences of characters
that you would generally express with quotes in your programming language.
>> You can have things called-- I'll oversimplify and call them
real numbers-- so numbers that aren't integers like the number 2,
but numbers like 4.56.
So real numbers can also have decimal points,
so that's a different fundamental piece of data in a computer.
And then you can even have other data types still.
So that's just a teaser really of the simplest of design decisions
that a programmer might make underneath the hood.
>> So any questions just yet?
So let's try to make this a little more real.
This hardware is not so much in use anymore.
But most everyone in this room probably grew up with and still uses hard drives
in some way.
>> Even though most of our laptops no longer
have devices that operate like this, instead laptops today generally
have solid state drives with no moving parts.
And that tends to be more expensive, unfortunately, but a little bit faster
and a-- well, often, a lot faster, which is one of the reasons.
And also it doesn't generate as much heat.
It can be smaller, so it's generally a net positive.
>> But this allows us to map a little more concretely what
we're talking about at the 0's and 1's level now to a physical device.
It's one thing for me to talk about 0's and 1's in terms
of my phone or abstractly in terms of switches being on and off.
But what about hard drives?
In your laptops, if you have an older one, or in your desktop computer,
or certainly in servers today, where you have
hard drives that have a terabyte of space,
4 terabytes of space, well what does that mean?
>> A hard drive with 1 terabyte of space means
there's 1 trillion bytes inside of it somehow,
or equivalently 8 trillion bits inside.
1 terabyte would be 8 terabits or 1 trillion bits, which
means if you have a hard drive, you have somehow
or other a trillion 0's and 1's inside of it.
And if we just take a look at an arbitrary picture of a hard drive
representative, this is what a hard drive might typically look like inside.
>> It, too, is kind of like an old phonograph player
but generally with multiple records inside, so
to speak-- multiple platters, as they're called,
metal circular disks, and then a little reading head,
much like an old record player.
And that reading head moves back and forth and somehow reads the bits.
And what's on these platters, even though we humans can't see them,
either in reality or in this picture, there's tiny little magnetic particles.
And even if you've long forgotten how electricity works,
a magnetic particle that's charged generally
has a north end and a south end-- so north and south.
And so the world just decided some time ago
that, if a magnetic protocol essentially is aligned like this, north-south,
let's call that a 1.
If it's instead south-north, let's just call that a 0.
And so if you have at your disposal a trillion
tiny little magnetic particles-- and hopefully,
the hardware ingenuity in order to flip those around
as you see fit-- if you want to represent a whole bunch of 0's, you
just need 8 magnetic particles all aligned like this.
And if you want to represent eight 1's, you just
need 8 magnetic particles aligned back to back to back like this.
>> What do I mean by the magnetic particles?
Frankly, all these years later, the thing that still comes to my mind
is this guy, if you grew up with this thing.
This is a little-- for those unfamiliar-- a
little childhood toy that has this hairless man here
that has all these tiny little black magnetic particles that come with it.
And using that red stick, which is just a magnet,
you can sort of give him a mustache or eyebrows or hair or anything on him.
So in fact, if we zoom in, for instance, this
is the kind of game you can play with Wooly Willy.
>> And this is only to say, these are much larger magnetic particles
than are actually on a hard drive, and far fewer magnetic particles.
But let's actually see then if you do have
tiny magnetic particles in a hard drive, how you can actually
use those to represent data.
>> [VIDEO PLAYBACK]
>> -The hard drive is where your PC stores most of its permanent data.
To do that, the data travels from RAM along
with software signals that tell the hard drive how to store that data.
The hard drive circuits translate those signals into voltage fluctuations.
These, in turn, control the hard drive's moving parts-- some of the few moving
parts left in the modern computer.
>> Some of the signals control a motor, which spins metal-coated platters.
Your data is actually stored on these platters.
Other signals move the read/write heads to read or write data on the platters.
This machinery is so precise that a human hair couldn't even
pass between the heads and spinning platters.
Yet, it all works at terrific speeds.
[END PLAYBACK]
And you can see at the tail end of the video,
there are generally multiple platters.
And so that reading head isn't just reading the top.
It's kind of like three or four or more reading heads
that move like this, reading data simultaneously.
>> So there's a lot of complexity and sort of timing
that's involved in a hard drive.
And the thing is spinning really darn fast, so there's a lot of complexity.
But let's zoom in a little deeper and see where are these magnetic particles
and how are we're getting at them.
>> [VIDEO PLAYBACK]
>> -Let's look at what we just saw in slow motion.
When a brief pulse of electricity is sent to the read/write head,
it flips on a tiny electromagnetic for a fraction of a second.
The magnet creates a field, which changes
the polarity of a tiny, tiny portion of the metal particles
which coat each platter's surface.
A pattern series of these tiny charged up areas on the disk
represents a single bit of data in the binary number system used by computers.
>> Now, if the current is sent one way through the read/write head,
the area is polarized in one direction.
If the current is sent in the opposite direction,
the polarization is reversed.
How do you get data off the hard disk?
Just reverse the process.
So it's the particles on the disk that get the current
in the read/write head moving.
Put together millions of these magnetized segments,
and you've got a file.
>> Now, the pieces of a single file may be scattered all over a drive's platters,
kind of like the mess of papers on your desk.
So a special extra file keeps track of where everything is.
Don't you wish you had something like that?
>> [END PLAYBACK]
>> So being alluded to there, perhaps, is that topic from yesterday of deletion.
When you delete a file, yesterday we said
that a computer actually does what, when you drag something
to the Recycle bin or trash bin?
It just forgets it.
But the 0's and 1's, the magnetic particles
that look like red and blue things here, or my arm here,
are still there on the hard drive.
>> And so there exists software-- Norton Utilities and Yesteryear
and other more modern software-- that just
will scan a whole hard drive looking at all those 0's and 1's, because it
turns out that most file formats-- Word documents, Excel files, images,
video files-- all have certain patterns that are common among them.
Every video file might be of a different video,
but the first several bits are usually the same.
Or the last several bits are usually the same.
>> And so with high probability, you can look for those patterns.
And even if the file has been forgotten, you can say with high probability,
but this looks like a Word document, lets recover it and un-forget it,
if you will.
And so that's how you can recover data that's either been accidentally
deleted or deleted or deliberately deleted for whatever purposes.
>> By contrast, secure deletion does what in the context of a picture like this?
Exactly, makes them all random.
So it sort of moves some of them down, some of them up,
leaves some of them unchanged, and generally makes random noise out of it,
or just maybe makes all of them 0's or all of them 1's.
And that too can generally scrub your data away.
>> So let's return now to the issue of computational thinking, whereby
we have the formula inputs.
And algorithms gives you outputs ultimately.
We focus now on inputs and outputs, because now, I
claim we have a way of representing inputs and outputs.
We're just going to use binary.
>> And no matter what we want to represent today,
whether it's a number or a letter or thousands thereof in a phone book
or images or movies, at the end of the day, it's all 0's and 1's.
And I claim that, even though this is a super simple world with just 0's
and 1's, we can build ourselves up.
And we've seen one example of that with letters thus far.
>> So let's focus now on this middle ingredient, an algorithm.
And let's return to this example of Mike Smith.
So in this phone book, which admittedly, we don't use so much anymore,
there's a problem to be solved.
We want to find someone like Mike Smith.
>> And what might I do to find Mike?
Well, I could just open up this book, start at the first page,
and realize, oh, I'm in the A section.
Mike's not there.
I need the S section for Smith.
So just keep turning one page at a time.
Let me pretend that this is all white pages and not yellow pages,
because we're not going to find Mike in the yellow pages anyway.
But I'm in the white pages.
And now, I'm in the B section.
I still haven't found him.
So I keep turning one page at a time.
>> This is an algorithm.
It's a set of instructions for solving some problem.
In other words, look at page, if Mike's not on it,
turn page, and repeats again and again and again,
ideally looking down as you're doing it.
So is this algorithm, this process, correct?
>> Sorry.
No, I hear some nos.
OK, but it is-- yeah, it's certainly tedious.
Like, we'll be here all day if I keep looking for Mike at this speed.
But let me claim it's correct.
It's stupid, but it's correct.
>> At the end of the day, long as it might take, I will find Mike if he's in there
and I'm paying attention.
And I eventually reach his page.
And if I get too far, if I get to the T section,
then I can slightly optimize and just say, hm, all done.
I don't even need to waste time going to the Z's.
But this is a very linear approach, if you
will, a very sort of left-to-right approach, a straight line.
And its correct but slow.
>> So I remember from grade school, sort of an optimization from a first grader,
where I learned how to count not by ones but by twos-- so 2, 4, 6.
It's A, lot harder to do, but in theory, it's
faster-- 8, 10, 12, 14, and so forth.
How about that algorithm?
Is it more efficient?
Is it faster?
>> AUDIENCE: It's efficient.
>> DAVID MALAN: Yeah, so it's def-- it's literally twice as fast, assuming I
don't get tripped up with my fingers.
It's twice as fast, because I'm turning through two
pages at once instead of one, but it's potentially in correct, because why?
>> AUDIENCE: You're skipping some.
DAVID MALAN: Right, what if Mike happens to be sandwiched-- maybe when I'm later
in the phone book, Mike happens to be sandwiched between these two pages,
and I just blindly skip over it.
So we need a little fix there.
Once I hit the T section, I can't just confidently say,
we didn't find Mike Smith.
I probably have to double back.
Or in fact, once I reach someone named S-N, instead of S-M for Smith,
immediately, I could double back, because maybe he
was on the previous page.
>> But I don't have to double back far.
In theory, if I do it at the right time, I just go back one page.
So it's adding only one extra step.
So I've gone twice as fast, but it cost me one extra page.
But that feels like a net win.
>> But this is not how most people in this room would solve this problem.
What would a typical person, maybe a few years ago do, to find Mike Smith?
Yeah, didn't find Mike.
What do I do?
So get a little closer, but I do know-- what is true about a phone book?
AUDIENCE: It's sequential.
DAVID MALAN: It's sequential.
It's alphabetical.
And so if I'm in the M section, Mike is clearly to the right,
I can literally tear the problem in half--
it's usually easier than that-- tear the problem in half and throw it away,
so that now, I have a problem that's no longer 1,000 pages-- that was hard,
because I think I actually tore the phone book this time-- not
1,000 pages, but 500.
>> So the problem is literally half as big.
And that's pretty compelling, because with my previous algorithms, version
1 and 2, I was only making the problem one page smaller, two pages smaller
at a time.
Whereas now, I made it 500 pages smaller all at once.
>> OK, so now, Karim proposes that I go to the right half.
So I'm going to go roughly to the middle, give or take.
And if I did this mathematically, I could go right to the middle.
And now, I realize, oh, I'm in the T section.
I actually did go too far.
>> But I can, again, tear the problem in half, throw it away.
And my bytes not as big.
It's only, what, 256 pages or 250 pages, give or take right now.
But it's still way more than one page or two pages.
>> And so now, I go roughly to the middle.
Oh, I didn't go quite far enough now.
So I repeat, repeat, repeat, repeat, until I'm hopefully
left with just one page.
>> So that invites the question, if I started with roughly 1,000 pages,
how many steps did it take me with version 1 of my algorithm?
Well, if Mike is in the S section, in the worst case,
that's pretty close to the end of the alphabet.
So if the phone book has 1,000 pages, I'll find Mike within 1,000 pages,
give or take.
Maybe it's like 800 or so, but it's pretty close to 1,000.
>> Whereas, in the second algorithm, how many
page turns maximally might I require to find Mike Smith?
There's 1,000 pages, but I'm doing them two at a time.
Right, so max like 500ish, because if I go through the whole phone book,
at which point, I can stop.
But I can shave off a few by just stopping at the T section.
But it's at worst case 500 pages.
>> So how many times can I divide a 1,00o-page phone book in half again
and again and again-- from 1,000 to 500 to 250 to 125?
How long before I hit one page?
Yeah, it's about 10.
Depending on rounding and such, it's about 10 pages total need to be turned
or phone books need to be torn.
>> So that's pretty powerful.
We started with a 1,000-page problem in all three of these stories.
But in the first algorithm, it took me, worst case, 1,000 page
turns to find Mike.
Second algorithm, 500 pages to find Mike.
Third algorithm, 10 pages to find Mike.
And it's even more powerful when you think
about sort of an opposite scenario.
Suppose that the phone company next year maybe merges two towns together,
and the phone book is suddenly this thick, instead of this that,
so 2,000 pages instead of 1,000.
Well, my first algorithm looking for Mike Smith in a 2,000-page phone book,
worse case, it's going to take how many page turns next year?
>> Phone book is 2,000 pages, so-- well, not one more.
If the phone book is twice as thick in the first algorithm, first algorithm,
2,000, right?
In the worst case, Mike is really close to the end of the book,
so it's 2,000 page turns.
Second algorithm going by twos, like 1,000 pages.
>> But how about in my third and most recent algorithm?
If the phone company doubles the number of pages from 1,000 to 2,000,
how many more times need I tear that book in half to find Mike?
>> AUDIENCE: Just one.
>> DAVID MALAN: Just one more, because with one page tear,
I can literally divide and conquer, if you will,
that problem in half taking a massive bite out of it.
And so this is an example of efficiency and arguably an algorithm
with which all of us are sort of intuitively familiar.
But it's just as correct as my other algorithms
with that tweak for the second algorithm,
but it's so much more efficient.
>> And in fact, what a computer scientist, or in turn a programmer,
would typically do when writing code is try to figure out,
all right, I don't want my program just to be correct,
I also want it to be efficient and solve problems well.
Imagine in the real world today, like Google indexes, searches
like billions of pages, imagine if they used the first algorithm to find cats
among a billion pages-- looking at the first page in their database,
the second, the third, just looking for a cat, looking for a cat.
That's pretty darn slow it would seem.
They could instead use something called binary search, which
is no coincidence-- bi meaning two, we keep dividing something in 2, in half--
they could use binary search and maybe find cats even faster,
or whatever it is you're searching for.
>> And frankly, there's even fancier algorithms
that do much more than just dividing things in half
in order to find information quickly.
And we'll talk a little bit about those after lunch today.
So let me just try to represent this.
We don't need to go into any math or actual numbers.
We can talk about this in the abstract.
>> But let me just propose, if you were having a discussion now
with the engineers proposing this algorithm
and you're trying to make a calculated decision,
because maybe the engineer says to you, you
know what, I can implement a linear search in like two minutes.
It's that easy.
Binary search is not that fancy, but it's going to take me like 10 minutes,
so 5 times as long.
>> There's a trade here, even in terms of deciding what software to write.
Do you write the simpler algorithm, which will just take you two minutes?
Or do you spend more time, 10 minutes, writing the fancier algorithm?
How do you decide that kind of question?
Or you could make it a little more real.
I tell my boss it's going to take me either one week or 10 weeks
to implement the software in this way, how
do you decide which algorithm to green-light?
Karim?
>> AUDIENCE: The audience, I guess.
>> DAVID MALAN: The audience.
What do you mean by the audience?
>> AUDIENCE: If it's going to be used by users
who [INAUDIBLE] by users [INAUDIBLE].
But if it's something you're just doing for yourself
to facilitate a problem, [INAUDIBLE] quicker.
DAVID MALAN: Yeah, it's quick and dirty is a good way to describe it.
In fact, if you're describing much of my time
in grad school, whereby often times, I wrote bad code consciously so--
at least, that's how I rationalized it-- consciously so,
because even though I was writing code that was relatively slow to execute,
I was able to write the code itself pretty fast, spending just minutes
or hours not days.
And it turned out, I occasionally needed to sleep.
So even if my code required 8 hours to run, well that's fine,
I'll just go to sleep while it runs.
>> So at the time, I thought this was very clever, even though I apparently
worked through my PhD very slowly.
But the converse of that is that, if I were writing software
for other people who mattered more than me, well,
having them wait 8 hours to get back their search results
is not all that compelling.
And so spending more time up front to write software
that is more efficient, more like our third algorithm,
probably benefits the users over time.
So it really depends over time how those costs add up.
If you're going to be writing software to use it once,
probably might as well do quick and dirty, as they say.
Just throw it together.
It's code that embarrasses you, it's so bad,
but it gets the job done correctly, even though it's not efficient.
Conversely, you spend more time on something, get it just right.
And then amortized over time, that upfront cost of time
is probably worthwhile, if you keep optimizing for the common case.
>> And indeed, that's a theme in programming, or computer science more
generally, trying to optimize not for the uncommon case
but the common case-- what operation is going to happen again and again?
If you're going to have billions of users searching on your website,
you should probably spend the extra weeks up front writing better software,
so that all of your users benefit.
Now, let's try to capture this a little pictorially, but not so much
numerically.
>> So here's just an old school chart.
And let me say that this is time.
And it doesn't matter what-- actually, no, not time.
Let's put that on the other axis.
Let's say that this is the time, and this is size of problem.
>> And a computer scientist might generally call
this just n. n is like our go-to variable, where
n is a number, n number, and it's the number of whatever inputs you have.
So in this case, n is the number of pages.
So it might be 1,000 in the case we just told.
>> So time can be any unit of measure.
Maybe, it's second.
Maybe, it's days.
Maybe, it's like page turns.
Doesn't matter.
Whatever you want to count in, that will be time or cost equivalently.
>> So with that very first algorithm, if I, for instance,
had a 1,000-page phone book, I'm going to draw a dot there,
because if it's 1,000 pages, it took roughly 1,000 page turns, give or take.
And then if I had a 2,000-page phone book,
and I'm going to draw a second dot here, because for 2,000 pages,
it's like 2,000 seconds or page turns or whatever.
And so when I said earlier, it's kind of a linear relationship,
that was deliberate, because I wanted later on-- right now-- to draw a line.
It's kind of a straight line relationship.
The slope is 1/1, if you will.
>> Meanwhile, the second algorithm said, if you've got 1,000 pages
and you were using the second algorithm, where I counted by 2's, turning
two pages at a time, should I draw a dot below or above my original dot?
>> AUDIENCE: Below.
>> DAVID MALAN: Below, because as we saw, it takes less time, half as much time.
So the dot should be half as high as the other.
And same deal over here, this dot should probably be roughly there.
And so my second algorithm, similarly, has a linear relationship with time.
And we can draw it as such.
>> So now, the third and final algorithm is a little harder to draw.
But intuitively, if I've got 1,000 pages with my third algorithm,
it should only take me like 10 steps.
And if I've got 2,000 pages with my third algorithm,
it should take me not 10 steps, but 11, just one more.
So we're only barely going to see this.
>> And it turns out, if I zoom in on this, I'm
going to exaggerate for effect, the shape of that line, ultimately,
is not a straight line-- because, indeed if it were,
it would look more like the others-- it's actually a curved line
that, if we zoom in, is going to look much more like this.
It-- well, OK, ignore this part.
That was my pen going of angle.
It's a curved line that is always increasing, always, always, always
increasing, but only just barely.
>> And so over time, you have a relationship that's more like this.
It almost looks straight.
But it's ever so slowly increasing.
But for almost all points along your x-axis, horizontal axis,
it's lower than those other lines.
>> So this might be a relationship n, whereby if you have n pages,
takes you n seconds.
This might be a relationship n/2.
You have n pages, it takes you n/2 seconds, half as many.
And this is a logarithmic relationship, which
if you recall, log base 2 of n captures this kind of growth, so to speak.
So this is the sort of holy grail among the three of these
here, because it's just so much more efficient, but arguably more complex
to implement.
Any questions?
>> Well let me do this, let me open up a text window
just so we can try to formalize something here.
So let me go ahead now and implement this algorithm
for finding Mike Smith in code, if you will, pseudocode code.
I'm not going to use Java or C++.
I'm just going to use sort of English-like syntax, which we
would generally call pseudocode code.
Here, I have a blank window.
And I'm saying step 1 of the very first algorithm is pick up phone book.
Step 2 is open book to first page.
Step 3 will be look at page for Mike Smith.
If on page, call Mike.
else turn page and go to step 3.
Done, let's say.
>> And so it's not quite perfect, which we'll see in a moment.
But let's consider what concepts I've introduced here.
So steps 1 and 2 and 3 are pretty much verbs.
They're statements, actions-- do this.
And so in a programming language, we would generally
call them statements or functions or procedures,
call them any number of things.
But they're just actions-- do this.
>> Step 4 is fundamentally different, because it's kind of asking a question.
It's saying we're kind of at a fork in the road.
If Mike is on the page, call him, so turn left, if you will.
And if not, go back to some other page-- or rather, sorry,
go back to some other step, which induces some kind of looping construct.
And we do it again and again and again.
>> And actually, you know what?
Yeah.
else if at end of book stop.
So we need kind of a third condition, because you
can't keep turning the page ad nauseum, because eventually, I'll
hit the end of the book.
And a bug in a program might be not anticipating that scenario.
And then I just realized, oh, wait a minute, I need a third scenario.
If I'm out of pages, I should really just stop.
Otherwise, it's undefined.
What's going to happen if I keep saying turn the page and go back,
this is when computers freeze or crash, when you hit
some unanticipated situation like that.
>> Now, what about Mike Smith's third algorithm--
pick up the phone book, open book to first-- to
no, not first page this time, to middle-- oh, well, that'd
be the second algorithm.
Let's just skip to the third.
>> AUDIENCE: Oh, I'm sorry.
>> DAVID MALAN: That's fine.
Let's just skip to the third-- open to middle and now look for Mike Smith.
if on page, call Mike.
And then what do we want to say here?
else what?
We can express this in any number of ways.
There's no right answer.
OK, if not again, but we need to be-- OK, we do want to divide in two,
but do we want to go left or go right?
How do we express that notion?
Well, in Mike's case, yes, that's fair.
But OK, so that's actually a good point.
That's fine.
We'll keep going with this logic.
So--
>> AUDIENCE: Less than half.
DAVID MALAN: Yeah.
So else if page is, we'll say, less than Smith, to the left of Smith,
then-- let's see, is this going to complicate?
else if page comes before Smith, tear in half, throw away which half?
>> AUDIENCE: I thought that was [INAUDIBLE].
>> DAVID MALAN: I'm hearing both answers.
>> AUDIENCE: Left.
DAVID MALAN: OK, throw away left half, as Lakisa
said earlier, the left half, then I kind of
want to just go to-- I go to the right.
Or equivalently, and I made a little bit of a mess of the beginning here,
I effectively want to go to step 2 again,
where open to the middle-- or open-- yeah, let's just say, pages to middle.
And this fixes it.
It's no longer a book.
It's just half of a book, so open pages to middle.
>> else-- were almost there.
Step 6, else if page comes after Smith, tear in half, throw away right half,
then go to step 2.
else quit, a fourth scenario if we have no pages left to turn.
So we could clean this up.
And we should clean this up.
This is very pseudocode code, if you will, very high level description.
But it does generally capture the idea.
>> And, again, in this scenario, we have the notion of a condition,
a branch, a fork in the road, making a decision-- if this, go this way,
else if, go this way, else if, go that way.
And this is a very common programming technique
to decide which direction to go, so to speak.
And we also have some kind of looping structure, where
we're doing something again and again.
>> Now, it turns out, much as in this example,
being super precise is important.
But we've also seen something that we keep calling abstraction.
What does it mean to pick up phone book?
We're just kind of taking for granted in this room
that that has some semantic meaning.
All of us just kind of know, oh, well, pick up the phone book.
What does that really mean?
Well, that really means extend hand, lean over, extend fingers,
pinch book between fingers, stand up, pull hand towards you.
And we could be really pedantic about this,
really being super precise as to what I'm doing.
But all of those steps collectively are what it means to pick up a phone book.
>> And so earlier, when I said, each of these first two statements
can be thought of as a proceed or a function,
really it represents what we keep calling an abstraction.
It's like a high level conceptual description of a problem that
actually involves quite a few steps.
And so this, too, is a recurring topic in programming,
whereby I might write a program using syntax like this--
pick_up_phone_book().
And then syntactically, I'm going to steal something
from most programming languages.
>> Now, step 1 looks even more like a function,
as a programmer would call it.
It looks like code that someone has given a name to and given
to me to use somehow-- in other words, what the line I've highlighted
represents functionality that maybe I didn't even implement myself.
Someone older, wiser than me already figured out
how you express the notion of picking up a phone book.
And it's like the five steps I just rattled off, off the top of my head.
>> But he or she already implemented this, gave those several steps
a name, pick_up_phone_book.
And the parentheses is just what most programmers
do at the end of statements like this.
I now can stand on his or her shoulders and never again,
think about what it means to pick up a phone book.
I can just say, pick up the phone book.
And that's exactly what all of us humans did here.
>> When we were probably 1 year old, 2 years old,
someone had to teach us what it meant to pick up a phone book.
And ever since then, we've abstracted away
from those very uninteresting mechanical steps.
And we just have an intuitive understanding
of what it means to pick up a phone book.
>> And you can extrapolate now to more complicated things--
construct a building.
Like, to some people, that actually has meaning.
To contractors, to architects, that has some meaning.
And they would know what to do, if I said, go construct a building.
>> But most of us in the room couldn't deal with that level of abstraction.
You need to tell us like go get the shovel and go get the concrete
and nail the pieces of wood together and whatever else
is involved in building a building.
And that's because we have not yet been programmed to understand
what it means to construct a building.
We don't have that abstraction.
We don't have that functionality.
>> And so what you'll see in programming languages, in general,
especially more modern languages, like Java, PHP, Ruby, and Python,
they're much more mature than older languages,
like C and C++ and yet others.
And so they come with more functionality built in.
More code has been written by people in the past
that we can now call or summon or use, as I'm hinting
at with this highlighted line here.
And so even though we're not talking about programming languages per se,
just pseudocode code, all of the ideas are still in that discussion.
And it turns out precision is super important, as is abstraction.
And let's try to communicate that as follows.
>> I accidentally might have spoiled this by flashing a slide on the screen
prematurely.
But let me ask for a brave volunteer, if you don't mind coming up.
You'd be in front of the camera, if you're OK with that.
Would anyone like to come up and give instructions to your colleagues here?
Just have to come over here and stand over here and say some words.
>> Victoria is smiling the most and avoiding my eyes the most.
Would you be willing to come on up?
OK.
And if everyone else at your seats could take out a piece of scrap paper,
if you will.
Lined paper is fine.
Come around this way.
Or some of the paper that you were given yesterday,
just any blank sheet of paper, if you could.
And if you don't have any, just ask your neighbor if you could.
>> So for the moment, for this example, Victoria
is going to play the role of a programmer, an engineer, who
needs to program you all, as the computers, to do something.
And we'll see what assumptions you decide to make.
We'll see how precise she chooses to be.
And if this demonstration goes pedagogically well, lots of mistakes
will be made, that we'll then use that as an opportunity for discussion.
But the challenge for you should be to avoid those mistakes,
be a good programmer.
And so the challenge at hand, if you'd liked to walk over here,
is in front of Victoria on the screen here-- and hopefully, none of you
remember this when I flashed on the screen.
And do not turn around at all, because there is another screen in this room
that I can turn off.
So don't turn around.
>> In front of Victoria is that same scream.
And her job now is to tell you all on your piece of paper what to draw.
And we will see, based on verbal instructions alone,
computer code, if you will, how accurate your drawings
are-- your implementations are.
Make sense?
>> AUDIENCE: Yeah.
DAVID MALAN: OK, execute.
>> AUDIENCE: Draw a square.
>> [LAUGHTER]
>> DAVID MALAN: And no questions may be asked.
Can only do what you're told.
Oh, and if you have today's slides open in a tab, don't look at your tab.
OK?
>> AUDIENCE: OK, draw a circle.
A slope-- can I say slope?
DAVID MALAN: Up to you.
AUDIENCE: A slope.
And a triangle.
>> DAVID MALAN: All right.
And stay here for just a moment.
And I'm going to come around in just a moment.
And no need to put your names on it.
Let me come around and collect your drawings,
if you don't mind tearing them out.
>> Here is what we got back.
I'll project it on the screen.
I see a square, a circle, a slope, and a triangle.
So that was one answer there.
And let's-- whoops.
Thank you.
Here's another assortment, and one behind it.
>> So they all seem to capture the spirit.
Thank you.
There's another, and here's another one.
The slope interpretation is a little different, little curvy.
And the closest, either because of the wonderful specificity with which you've
described, or maybe you kind of saw it before, this is indeed
what Victoria was actually describing.
>> But now, those of you who didn't get it quite right,
let's offer some objections here.
So Victoria first said draw a square.
And now, we can assume for the sake of today
that everyone knows how to draw a square.
But that's not wholly clear, right?
How else could you have drawn a square, or where
might be some of the ambiguities here for the computer?
AUDIENCE: Location and size.
DAVID MALAN: Location, right?
All of you had a paper of some shape, generally rectangles, but slightly
different sizes.
But you certainly could have drawn, if you wanted, a huge square, maybe
a tiny square.
Maybe, it was rotated.
I don't think we saw that.
But it could have been more diamond like but still, nonetheless,
mathematically a square.
So that was arguably ambiguous.
>> Then she said, draw a circle.
Some of you did draw it next to it, which isn't unreasonable,
because humans tend to think or read right to left in most languages, so not
a bad guess.
But that circle could have been inside the square,
could have been around the square, could have been elsewhere
on the sheet, so arguably ambiguous.
>> Slope might have been maybe taking the most liberties verbally
with what that means.
And some of you interpreted it as a squiggly line
or a straight line or the like.
And then triangle, too, could have been oriented in any number of ways.
So in short, even with something that you glance and you're like, wow, so
simple, a child could draw this, well not
really, unless you're super, super persuasive
and tell the computer exactly what to do.
So if we could, if you have another sheet of paper, let's
try this once more.
And I'm going to give Victoria one other example on the screen here.
And again, don't turn around and don't look at your slides.
And I'll give her a moment to think about how to describe this.
Don't let them see the fear in your eyes.
>> [LAUGHTER]
>> And again, this time leverage some of those takeaways
and try to get almost everyone at least the right answer.
>> AUDIENCE: OK, take a piece of paper, look
in the middle of that piece of paper.
In the middle of that piece of paper, draw a cube.
>> [LAUGHTER]
DAVID MALAN: What have we learned?
We were so close.
OK, repeat if you could, for everyone.
>> AUDIENCE: In the middle of the piece of paper, draw an object,
which looks like a cube.
>> DAVID MALAN: OK, that's all you get to work with.
Allow me to be analytical and not so much critical,
but to make the claim that Victoria definitely
seems to be thinking in very high level abstractions, which
is not unreasonable.
Because otherwise, we'd all be pretty dysfunctional,
if we had to be ever so precise with everything we do in the world.
>> But saying go to the middle-- I thought we were on such a good track
there, like go to the very middle of the page, and then draw a cube.
So she's thinking in abstractions, because she's still viewing
what's on the screen as indeed a cube.
But there's so many opportunities for interpretation there.
And in fact, there's so many other ways you could express
that, which I'll propose in a moment.
So here we have one incarnation of the picture-- whoops-- one
incarnation of the picture, so a little three dimensionality to it,
which is nice.
>> Here's another one, where you have the same, though it's kind of an open cube.
Some folks took it a little more flat, two dimensional.
And that's fine.
So there, indeed in the center of the paper.
This one I think you'll like, because if we go here,
this is what she was describing.
So now, let me propose how else we might describe this situation.
>> Back in the day, one of the most more common ways to learn programming
was to write code, writes lines of instructions,
that controlled a little turtle on the screen.
Logo and other variants of this was the name of the language.
And the turtle lived in a world.
>> So suppose this rectangular space is his world.
And you would start by assuming-- I don't really know how to draw turtle,
so let's do it like this.
And then he's got a shell and then maybe some feet.
So you might have this little character on the screen.
>> And the object of this programming language
was to compel the turtle to go up, down, left, right
and to put his pen down or pick his pen up,
so he could actually draw on the screen in this very flat rectangular world.
So where I thought you might be going, and where you should consider diving
down to mentally when describing instructions more generally,
I would claim, is put your pen down in the middle--
and we'll get rid of the turtle, because I can't really
keep drawing him very well.
>> And now, how else could I say draw a cube?
Well, we could say something like draw a diagonal line northeast, for instance,
or at a 45-degree angle upward.
And that might have gotten me here.
And I'm pretty far from a cube.
But now, I could say something like turn 90 degrees to the left
and draw a line of equal length northwest.
And I could continue with similar directions.
And it's not going to be easy.
And frankly, we probably would have been here for five minutes.
But maybe we would have gotten to something that, at the end of the day,
ends up being a cube, but we dived inside of that abstraction
to do it at such a low level that you can't really
see what you're doing until the whole thing is actually there on the page.
And so this is a general principle, again, of programming-- this idea
of abstraction.
It's so wonderfully powerful, because again,
she just said, draw a cube, which all of us pretty much would grok very quickly.
We would just understand, OK, draw a cube.
We might not know the orientation, so we could be a little more precise,
but we can generally picture or know what a cube is.
And that's useful, because if every time you
sat down as a programmer at your keyboard to write code,
if you had to think at such a low level, none of us
would ever get anything done.
And certainly, none of us would enjoy the process of writing code.
It would be like writing in 0's and 1's, which frankly wasn't all that long ago
humans were writing code in 0's and 1's.
And we very quickly came up with these higher level languages--
C++ and Java and others.
>> So let's try this once more just to flip the tables, so that all of us
have the chance to think in rather the same way.
Could we get one more volunteer this time to come up to the board and draw,
not recite?
Yeah, OK.
Ben, come on up.
And, Ben, in this case, once you face the board, don't look left,
don't look right.
Only do what your colleagues here tell you.
And for everyone else in the room, you now are the programmer.
He's the computer.
And the picture I've chosen here in advance is this one here.
They're just-- they're thinking of a funny joke is all.
>> So would does someone like to volunteer the first instruction
or statement that should command Ben's pen?
And we'll do this collectively, maybe one instruction from each person.
I'm sorry?
>> AUDIENCE: Draw a circle.
DAVID MALAN: Draw a circle is the first thing I heard.
>> AUDIENCE: Up top.
>> DAVID MALAN: Up top.
OK, we can let you delete, undo.
And now, someone else.
Dan, would you be comfy offering the next instruction?
>> AUDIENCE: Sure, draw the center of the bottom of the circle,
with a small-- a little small space from that,
draw a straight line down to three quarters of the way down the board
a slight angle to your left.
>> DAVID MALAN: Good.
>> AUDIENCE: Slight angle.
>> DAVID MALAN: Undo, Control-Z. OK.
Andrew, you want to offer up the next instruction?
>> AUDIENCE: Sure.
From the bottom of that line, a further slight angle--
whoops-- maybe about a third of the length [INAUDIBLE],
slight angle downward and like a third of the length of [INAUDIBLE].
So yeah, from that point, draw a line a third
of the length of the previous line further to the left.
>> DAVID MALAN: That OK?
Straight line, that's OK?
OK, Olivier, you want to offer up the next?
>> AUDIENCE: [INAUDIBLE] from the bottom of the circle, [INAUDIBLE].
Draw on the right hand side of [INAUDIBLE] centimeters.
>> [LAUGHTER]
>> DAVID MALAN: I think you're going to have to convert that's inches here.
>> AUDIENCE: Stop.
>> [LAUGHTER]
>> DAVID MALAN: OK.
[? Ara, ?] you want to offer up the next?
>> AUDIENCE: Draw a [INAUDIBLE] the upper [INAUDIBLE] the same.
[INAUDIBLE] circle, draw to the [INAUDIBLE] and draw [INAUDIBLE].
>> DAVID MALAN: OK, no more undo.
Let's do one or two more instructions.
Chris, you want to offer one?
>> AUDIENCE: At the bottom of the circle, [INAUDIBLE]
draw an equal line slopping downward to the left [INAUDIBLE].
>> DAVID MALAN: OK.
Andrew?
We did-- Karim?
>> AUDIENCE: Starting from the right line, the end of the left line, the bottom,
you're going to go right about the same length as that line
you're on, drawing to the right [INAUDIBLE].
[INAUDIBLE] degrees, so [INAUDIBLE] degrees on the right side.
>> DAVID MALAN: All right.
Let's pause.
Don't turn around yet.
Let's pause, and let's try one other attempt
before we reveal to Ben what he's been drawing.
Can you shuffle Ben to the right-- or actually,
no, let's just give you another board, even better.
So would someone now like to take more of the approach
that Victoria took earlier on, where we speak in a higher level abstraction
and in just a sentence or two describe to Ben
what to draw without getting into the weeds,
so to speak, at this a lower level?
Victoria.
[LAUGHTER]
AUDIENCE: Draw a figure of the walking man.
And his legs and arms have to be the right side.
>> DAVID MALAN: OK, that's all you get.
All right.
Why don't we reveal to Ben what he did.
So a round of applause.
That was the hardest perhaps.
>> So even though we're talking in fairly silly terms
about just drawing pictures, hopefully you
can really appreciate the degree of expressiveness that might be necessary
in order to tell a computer what to do.
And in fact, the fact that Ben was able to draw this so quickly
is sort of testament to using a language, maybe a higher level
version of English, that allows him to just use words, or hear words
from Victoria, that allow him these abstractions-- just draw
a figure walking to the right-- that sort of has
some semantic meaning to it that isn't nearly as obvious when you're just
saying, put your pen down, draw to the right, draw to the left.
>> And so this, too, is very common in programming.
This would be said to be like a very low level language, programming
in 0's and 1's if you will.
And this would be a higher level language programming in Java,
or something like that.
A bit of an oversimplification, but that's
the sort of like emotional feeling that you feel when
using one kind of thing or another.
A bit of frustration here by the need for such precision, but the opportunity
to be a little looser with the interpretation here.
But of course, bugs can arise as a result.
>> If you'd like at home-- we won't do this one in class--
but if you'd like to bring this one home,
I thought we would dive into this.
So if you'd like to play this game with your significant other
or kids or the like, you might enjoy that as well.
>> So let's go ahead and look at one last thing here for computational thinking.
And that brings us to John Oliver, not for the clip
you might have seen last night, but to a somewhat recent issue.
A few months back, Volkswagen took quite a bit of flak
for what reason, if you know?
What did they get in trouble for?
>> Yeah, so emissions-- they were trying to beat emissions
tests by essentially having their cars pollute the environment less
when their cars were being tested and pollute the environment more
when the cars were not being tested.
And what's increasingly interesting in the world, as you may have inferred
from discussions of like-- what is it-- CarPlay, Apple's software for cars
and the fact that many of us increasingly
have touch screens in our cars, there's a frightening amount
of software in people's cars today, which
frankly opens a whole can of worms when it comes to security and physical risk.
But for today, let's focus on just what's
involved in writing software that might have gamed the system.
>> For the definition of the problem, for those unfamiliar,
let's take a look at John Oliver.
And for those familiar with the problem, let's look at it
in a fun lens via John Oliver as well.
So let me hit play on this, I think, three-minute introduction.
Damn it.
[VIDEO PLAYBACK]
-Cars--
DAVID MALAN: Obviously, on YouTube, it's--
- --the smartest characters in the Fast and Furious movies.
This week, German automaker Volkswagen found itself
in the middle of a scandal of potentially criminal proportions.
>> -Volkswagen is bracing for billions in fines, possible criminal charges
for its executives, as the company apologizes
for rigging 11 million cars to help it beat emissions tests.
>> -Certain diesel models were designed with sophisticated software that
used information, including the position of the steering wheel and vehicle
speed, to determine the car was undergoing emissions testing.
Under that circumstance, the engine would reduce toxic emissions.
But the car was rigged to bypass that when it was being driven.
Emissions increased 10 to 40 times above acceptable EPA levels.
>> -Wow, 10 to 40 times greater than the EPA allows.
That is the worst thing Volkswagen has ever done,
is something you might say if you'd never heard of World War II.
But maybe the surest sign of how much trouble Volkswagen is in,
is that people at the very top have stepped down.
The CEO resigned on Wednesday after scrambling to do damage control,
saying he was endlessly sorry, which sounded great until it turned out
he was only 10% sorry but had rigged his mouth
to artificially inflate his sorriness.
And meanwhile, Volkswagen's US chief had an apology of his own.
>> -Let's be clear about this, our company was dishonest.
And in my German words, we have totally screwed up.
>> -Yeah, but totally screwed up are not German works.
And the German language has many beautiful phrases
to describe situations just like this, such as [GERMAN], which means roughly,
the sadness that comes from business related lies,
or [GERMAN], which translates as shaming ones father involving
clouds of gasoline.
It's a beautiful language.
It just sails off the tongue.
And by the way, while that man's apology may have sounded sincere,
it's worth noting he was speaking at an official launch party for the 2016
Volkswagen Passat, meaning that shortly after saying sorry, he said this.
>> -Thank you very much for coming.
Enjoy the evening.
Up next is Lenny Kravitz.
>> [MUSIC PLAYING]
>> -OK, OK, ending your apology with up next
Lenny Kravitz does not scream sober contrition.
It screams, we asked Bon Jovi, and he said no.
Volkswagen's brand has been badly damaged.
And frankly, their new ad campaign is not exactly helping.
>> --[GERMAN], we at Volkswagen would like to apologize for deceiving you with
our vehicles.
>> [END PLAYBACK]
DAVID MALAN: So this was a roundabout way of-- sorry--
this was a roundabout way of introducing a fundamental problem
in software, which is that you need to detect certain conditions.
And so the question at hand here is, how does a car potentially,
as implemented in software by these programmers,
detect that it's actually being tested?
So to be super clear, what they were doing
was, in environments where the programmers figured
the car was being tested, they somehow made
the car emit less emissions, fewer emissions, so less toxic fumes
and such.
But when it's normally driving on the road,
it would just emit as much pollution as it wanted.
>> So how could we write the pseudocode for this algorithm?
How could we write the pseudocode for the software running in the car?
I mean, in a nutshell, it boils down to something like this.
if being tested, emit less.
else emits more.
But that's a little too high level, right?
>> Let's try to dive in as to what this abstraction of being tested means.
In other words, even if you know nothing about cars, what sort of questions
might you ask in order to determine if you're being tested, if you're the car?
What characteristics might be present if a car is being tested?
>> AUDIENCE: Testing equipment.
>> DAVID MALAN: Testing equipment.
So if testing equipment nearby, then emit less.
So I could imagine implementing that with some kind of cameras
or detecting what's around you.
And let me propose, that just feels too complicated
to actually have additional hardware just for that purpose.
>> AUDIENCE: If you're in park, if your hood is open.
>> DAVID MALAN: In park or hood open, so that's good.
>> AUDIENCE: And car running.
>> DAVID MALAN: So that's a little more concrete-- and car running.
So this would be the conjunction of a few different conditions, if you will.
So if the car is in park, and even though this is a very mechanical thing
typically, I could imagine writing software,
especially because there's often a light there these days,
I could imagine there being software that can query the shifter
or what not, are you in park, are you in drive, are you in reverse.
And I can get back an answer that's either yes
or no to those kinds of questions.
>> And so I could also probably answer a question like, is the hood open.
Maybe, there's some kind of sensor that either gives me back a 1 or 0,
true or false, the hood is open.
And then car running, I could detect that somehow via what mechanism?
Like, the car is running, I could detect that it's on,
could I detect somehow that the car is moving?
>> AUDIENCE: RPMs.
>> DAVID MALAN: Yeah, so there's always that needle that
tells you how many rotations per minute the wheels are experiencing.
And so I could look at that.
And if it's not 0, that probably means the car is moving.
But we have to be a little careful there,
because-- let's simplify this-- if we just said, if car running,
we don't want to just emit less, we want if the car is running
and it's being tested.
>> So there are a few other ingredients that folks
have hypothesized the software is doing, because absent the actual source code,
you can only sort of infer from the physical effects of the car as to what
might be going on underneath the hood in software.
So if car running and maybe, say, rear wheels not moving,
might this be indicative of some kind of test?
What am I hinting at here?
Yeah, maybe, it's on one of those roller things,
where like the wheels are turning in the front or in the back,
depending on whether it's front wheel or rear wheel drive, so half of the wheels
are moving, but the other two aren't, which
is a weird situation in the real world.
If you're driving on the road, that shouldn't happen.
But if you're in a warehouse on some kind of roller system,
that might indeed happen.
>> I think folks also proposed that maybe, if the car is running and steering
wheel not moving, that too might be a signal,
because that's reasonable for like a straightaway on a road.
But even then, the human is probably moving it a little bit or certainly
over a few seconds.
Or the course of a minute, odds are it's not
going to be fixated in exactly the same position.
>> So in other words, we can take substraction,
are you being tested, and break down that functionality
into these component ingredients.
And that's truly what Volkswagen's engineers somehow did.
They wrote software consciously to detect if the car is being tested,
therefore emit less, else emit in the usual way.
>> And the problem here, too, is that software is not
something you can really see unless you have the so-called source code.
So there's two different types of code-- at least two different types
of code in the world.
There's something called source code, which is not unlike what
we've been writing, source code.
>> This is source code written in a language called pseudocode,
which is just something English-like.
There's no formal definition of it.
But C, and Java, C++, those are all formal languages that,
when you write in them, what you have is a text file containing source code.
>> But there is also something in the world called machine code.
And machine code, unfortunately, is just 0's and 1's.
So machine code is what machines understand, of course.
Source code is what humans understand.
>> And generally, but not always, there is a program
that a programmer uses that takes source code and turns it into machine code.
And that program is generally called a compiler.
So your input is source code, your output is machine code,
and the compiler is a piece of software that does that process.
So this actually maps nicely to our inputs, algorithms, outputs.
>> But this is a very specific incarnation of that, which is to say that,
even if you own one of Volkswagen's cars that is guilty of this,
it's not like you can just open the hood or open the user's manual or look
at the source code, because by the time it reaches your car in your driveway,
it's already been converted into 0's and 1's.
And it's very hard, not impossible, but very hard to glean much of anything
from just looking at the underlying 0's and 1's.
So you can figure it out, ultimately, if you understand how a machine operates--
Intel inside-- if you understand the Intel architecture,
but it's very time consuming.
And even there, you might not be able to see everything
that the code can actually do.
>> Any questions about this or this kind of process more generally?
And actually, we can tie this discussion to yesterday's discussion of Apple.
This, too, is why the FBI can't just go and look in the suspect's phone
and find the lines of code, for instance, that enable the passcode
or enable that 80-millisecond delay.
Because by the time it's on the fellow's iPhone,
it's already been converted to 0's and 1's.
>> Well, let's pause here for our look at computational thinking.
Why don't we take a 15 minute break.
And when we return, we'll take a look at programming
itself and start to map some of these high level concepts
to an actual, if playful, programming language.