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.