>>All right, welcome to CS50. This is the end of week 5, so I felt that Monday's lecture fell a little flat, I wasn't really feeling it so I thought we'd try to spice things up perhaps today with some props. So I went shopping there in the square. But first, some good news and some bad news; which would you like first? >>Bad. >>I heard 1 person say good first, but then everyone else wants the bad news. Bad news, Quiz 0 is next Wednesday. But this is mitigated by the fact that there's no class Monday and there's no problems with next week as well. So realize you have a handout in your hands from outside that describes all of the particulars for Wednesday's logistics. Do not come here because of our size, we'll split up into 3 different lecture halls, where you actually have a decent writing surface for the quiz, so that's all there and it's also on the course's website. If you lose this piece of paper or tuning in afar do not have this piece of paper, it's under the "Quizzes" page. Also on the "Quizzes" page are 5 previous quizzes, along with their solutions. I know, this is probably more interesting than the quiz, but okay. And actually the segue way here was this is a wonderful way to waste a lot of time. Not only was this implemented years ago, actually in ASCII or ASCII Art, which is a complete tangent, isn't it? So this was implemented in ASCII Art. The relevance is that we used ASCII Art for last problem set, for the game of 15, but we definitely raised the bar a bit with Sodoku, where you're actually using a graphics library, called N Curses, albeit a very limited graphical library. So this thing used to live on a server that you could TelNet to. TelNet is like SSH, but it's unencrypted. So this guy, years ago made this whole animation of Star Wars. And now there's variants on the web and in Java applets. But it's pure ASCII Art for almost the entirety of that movie. So we'll link to that on the course's website, if you're curious. It's an hour or more long. Now, back to reality. Let's see, we were on the bad news. The bad news is that the Quiz 0 is Wednesday, but there's innumerable resources on the course's website under "Quizzes" from past quizzes. Realize that the material does vary somewhat year to year. So if you see some topic that's completely over your head, it may very well be that it is completely over your head, but we might not have covered it, either. So do consult the syllabus or me or a teaching fellow. And then also this week, on Sunday, Monday, Tuesday the sections will obstinately be review for the quiz. And then, this Sunday at 7 pm in Emerson 108 will be a course-wide review which is optional, but you're welcome and encouraged to go. It will be filmed and put online by Tuesday. And this will supplant the regularly scheduled walk-through. So there's no walk-through this Sunday, instead there's a review for this. And all of that is on your PDF for your reference. Okay, so let's see. We did the good news. No P Sets [assumed spelling], no lecture on Monday. Which means this last time we'll see you for a week. But without further ado, some stuff. On Monday, we talked about pointers. And we've been talking about pointers. And this is the last piece of interesting, or dare I say, complicated syntax that we're going to introduce in the concept of C. Because once you have this ability to manipulate memory at your will, you can do a lot of interesting things. And also thus far we've not have useful data structures. You've had these things called primitives. And primitive is an int, a char, a float. Any of those little things that you get for free in the language. And then we have this data structure called an array. But it's really just a nice conceptualization of a chunk of memory back to back to back to back that you can address via that square bracket operator. But today, we introduce a fundamentally more interesting data structure and it's more of a traditional data structure. Or, as people call it, an abstract data type. ADT, if you ever see that acronym somewhere. And that just means that in general, these more interesting data structures are things that have data associated with them. Properties, fields, call it whatever you want. Pieces of information about variables, much like the structs that we've discussed, but they also have operations related to them. So the thing about C is that even though we have these structs that we started using on Monday, just to encapsulate related information. Those of you who have tackled P Set 4, know that all of our global variables, which is tucked inside of a struct, because it felt a little cleaner to encapsulate them. And this word, encapsulate, is actually a theme in programming because it means to gather together like, or related, data. But there's no fundamental operations that are supported by that struct. There's no functions related to Sodoku's board. Anything you do with G dot whatever has to be done very manually. G dot X gets some value, G dot Y gets some value. You don't have any built-in mechanisms. But now that we start talking about these things called linked lists, which will address some weaknesses in arrays, can we actually say that there's some formal operations, some features of these data structures that up until now, we haven't really had. But why care at all, why not just draw the line after arrays? Well, arrays are only so good. What is a downside, in your mind already perhaps, about arrays? >>[inaudible audience comment] >>Since it's not been working very well in past lectures, I felt there are just some murmurings and then I fill in the blank with my own answer. So give me a hand, if you would, it's hard for me to hear you. Okay, black shirt here. Yes. You're wearing white. >>[inaudible audience comment] >>Good, so you need to know the size of the array that you want before you create it. And there's a couple of ways we can create arrays now, right? One is just to declare it statically within some function, or maybe globally. But statically in the sense that you start int, then the name of the array, open brackets, some number. Closed brackets, semi-colon; or maybe it's 2 dimensional or 3 dimensional. But you have to know in advance what that size is going to be. Or you can also allocate an array dynamically, which means on demand using what new function or what useful feature of C? >>Malok [phonetic spelling]. >>Malok. And Malok doesn't give you an array, per say, it just gives you a pointer to a chunk of memory that is as big as you ask the operating system for. But in the event the OS just doesn't have enough memory to give you; you ask for 5 gigabytes, and that's just unreasonable. What will Malok return? Quick review. So it's going to return that null value. So the best lesson you can hammer into your head when you're playing with problem set 4, 5 and beyond is anytime you manipulate pointers in C, constantly, very defensively check for null pointers. Because otherwise these very bad things known as Segfalls [phonetic spelling] happen a little too often. So arrays require that you know in advance how big they are. And that might be fine because we already saw in that silly little registrar example that I did where I inputted students' names and houses and ID numbers. Well, I can just change the constant, called students, from 3 to some other value. So why is that not really a compelling argument that okay, yes, you have to declare an array's size in advance, but you can always change it. What is the downside about that approach? And recall in that example, there was sharp defined students and then it was hard coded at 3. But I could very easily change that, right? That was the whole point of the constant. So why is that not really a compelling argument in favor of arrays? Yes? >>[inaudible audience comment] >>Okay, so causes security vulnerably. So the fact that arrays are fixed to 1 length and view, you as the programmer have to check the length of them. That's the security vulnerability, sure. But specifically with regard to their size. Why can I just not say array size can be changed, just change the constant in your code? >>[inaudible audience comment] >>Right. So the user can't do that. You, the programmer, absolutely can go into your dot C file or dot H file, change that constant. But then, what do you need to do? Recompile, right? And that's not that compelling. Maybe now in ES50, week 5, it's pretty easy to recompile, it's pretty fast because we're only writing so much code. But if you're Microsoft, if you're a company that's actually written a program and ships it in a shrink-wrapped box, or a user has downloaded it. No, there's no chance thereafter to change anything in the source code unless you update the whole darn thing. So we need some more dynamisms. So Malok does give us that, because we can ask the user how many students are in the class. And then we can allocate using Malok a chunk of memory that's actually big enough. But what happens if I start up my program and I say I have 100 students this semester? So give me enough memory for 100 students. So 100 times the size of the student struct. Okay. But what if there are some late registrants at the university? And this happens in every course here. People add, they drop. But after the program's already running, after the program's already compiled. So I now have an array of size 100, what do I then do if while the program's running, I need to change its size? What are my options? >>[inaudible audience question] >>I mean intuitively, would you like to do? Right now, I have 100 students in an array, but now I'm out of space. So just intuitively, what would you do? >>[inaudible audience question] >>Make a new array, right? So use Malok again, whatever technique you used the first time, make a new array, maybe err on the side of safety, make it 200. Even though you might waste some memory, and then what do I do? I have an array that's 100, and an array that's 200. What do I do? >>[inaudible audience question] >>So copy one into the other, that's a simple foreloop [assumed spelling], wild loop [assumed spelling], whatever you want to use. Then what should I do? >>[inaudible audience question] >>So free the first array, right? And you can do this in relatively few steps. We just rattled off maybe 5, 6 maybe max 10 lines of code to call Malok again. To use a loop to copy the contents of the old array into the new; and then to call free on the original array. But what do I probably need to keep track of now? Arrays are just a chunk of memory, what do I need to keep track of? If I've now added some more students to this bigger array. There's murmurings, what? Okay, the size of it, right? So this is one of the downsides, upsides, however you want to view it to see. The burden is on you to remember the size of some integer called N. All right, but this is annoying and we saw this ability in get strings. You might not recall the CS50 source code, but you do have it and at this point in the semester, probably pretty accessible, reading it top to bottom again at home. But our get strength function is exactly this. We took a guess. We allocated, I forget what the constant is, 128 bytes. Something arbitrary, but relatively big. And then we have a loop that says if the user types in 129th character, uh-oh, let's call a new function and we actually slightly more fancy use reallocation, which actually does that copying for you, so you don't need to resort to the foreloop. But the same idea this is arguably annoying. Every time you want to add something to the array, you have to check its length. Too small reallocate an array. That's a lot of minutiae just to add something simple to your array. So it turns out that there are data structures that address this. The downside of an array is that it's fixed eyes. Well, why don't we craft a data structure that's of variable size? That grows when we want it to, and we don't have to jump through all these stupid hoops of copying big chunks of memory again and again and again just because we didn't have the foresight to know in advance how big this thing needs to be. So we can express this data type, frankly using a pretty clear picture. So if I have an array, it looks like this. And this is of size N or in this case size 4. So I put a bunch of new students in here. We've got Students 0, 1, 2, 3. But now I'm screwed if I want to add more students here. But this new data structure that we'll call a linked list and is much more compelling is something that might look like this. Well, when I have one student, let's allocate a student object a student struct in C speak. Well, if I have a second student, let's create another one. Another student, another one. Another student, let's create another one. And then inside each of these structs, just as in my example last week. I had an ID field and I had a name field and I had a house field and repeat that for each of these guys here. I can do the same thing here. I can do ID, I can do name, I can do house. But, because I've called Malok for each and every one of these students on demand. I need to somehow keep track of where they are in memory. Because you call Malok, the stuff you get back, the pointer you get back is not guaranteed, in fact the pointer you get back does not guarantee it to be back to back to back to back. Maybe by chance it will be, especially if we call it in rapid succession because no one else is using that memory, but it's no guarantee. So what you get back every time you call Malok is a pointer to this thing, a pointer to this thing, a pointer to this thing. And again. And now we seem to have a downside. An array is previously we could remember by way of 1 pointer or by way of their name. But how many pointers do I need now to keep track of my 4 students? So it seems 4, right? 4 unique addresses, they're not necessarily continuous, which means I can't use pointer arithmetic because I got back 4 unique addresses, they're not contiguous, which means I can't use pointer arithmetic, I can't use square bracket notation because that assumes that requires a leap of faith that everything is laid out contiguously where it's expected. So I intentionally left this extra field here. So if we just are a little clever, and define our student struct as not only having 3 fields that we really need, but a 4th field, maybe we can just string these things together. We can daisy chain them, if you've heard the word. So we have a pointer that yes, points to the very first student. But you know what? We don't need pointers separate, why don't we just include them in our struct? And somehow link these things together in this fashion. And the only thing I have to be really careful about right now is what? What goes here? So you need some sentinel value that will probably be null in this case. Anytime you need the absence of a pointer, or null, it's important. If I hadn't done that, what might happen if I traversed this list as by in the foreloop or wild loop just following these pointers. And how you follow the pointers we'll see some tactically today. What could happen if this is not null, but some unknown value? Garbage values, as we keep calling them? >>[inaudible audience question] >>A little louder? >>[inaudible audience question] >>Yes, you could follow the pointer that just so happens to look like a number but really leads nowhere useful. Nowhere you own and so you get that typical segfall [phonetic spelling]. All right, so let's try to frame this specifically. All right, so this, I would propose is a new struct that we use. And let's simplify. Let's not use student objects just yet because there's a whole bunch of additional data which feels a little complicated to keep track of. Let's reign it in, assume we're storing numbers, just the IDs. So I'm going to use that same type of feature before because I want to call this thing a node. And so in general, anytime you have these graph-like structures, these list-like structures in Computer Science or Math are generally called nodes. So we'll call this thing a node using the same syntax as last week. But, notice 1 difference here. Last week, when I typed up something, I didn't type deaf struct. Name of the thing and then the curly braces the name of the thing again at the end. But in structure, notice how 1 of the fields, even though this is the student version, notice how 1 of the fields needs to point to in object of the same type as the thing storing this pointer. In other words, we need a way to be self-referential and this just means that using the syntax of C if you want to store inside of a struct, a pointer to that same kind of struct. You just have to append its name here, even though it looks somewhat redundant. So just take it on faith for now, declare a struct that is inside familiar syntax and if we want to have a pointer that leads elsewhere, we simply define it as struct node star next. Although, next can be called anything we want. So what does this mean specifically? This just means that I declared a structure that in general is going to look like this, where this field is called N. This field is called next and the data type of this thing is what? [inaudible] That's just an end and this thing, a pointer to a struct node. So a pointer to a struct node, or a pointer to a node if we just want to just simplify. All right, let's just take a look at what we can do with this and why we should actually care. Let me go ahead and make something called List 1, this is the same printout from Monday, if you have your handout with you, or there's extras outside. I'm going to go ahead and run List 1 and to demonstrate this use of linked lists I had to write a quick and dirty program. Because just coding up linked lists in no context really isn't that useful, but if instead run this version here, what I decided to do was turn it into a little bit of an interactive interface. So what's just executed as my main routine. My main routine has some printout stuff and it just prints out this quick and dirty menu when I map numbers to different operations. So a linked list, as this picture will be generally called, has a bunch of operations that are inherent to it, or related to it. The things people like to do with linked lists is find things inside of them. So in this case, I might want to find an integer in this list to answer questions in the form is this student in the list? Is this integer in the list? That's find, otherwise known as search for any number of other things. Traverse just means start at the beginning, go to the end and maybe do something along the way, generally print things out so that would be the traverse operation. Insert, as the word implies, means add a number to the list, but here's where things will get a little interesting because if you have this string-like structure like this, inserting can actually be tricky in some situations. Because if you want to keep this list sorted, which you probably do for efficiency reasons, as we've seen. Can actually search it a little more effectively. We might want to put the new students here. That looks like it's pretty easy. I'll take this arrow and some other arrow in here. But if it's sandwiched in the middle, it feels like there's going to be some more code and some more movement of pointers. If it's at the end, again, it's a different case. So this simple idea of inserting a number into a sorted length list can actually be broken down into 3 cases. Beginning, middle, end. And hopefully we can generalize in that way. And delete, the same thing. If I want to delete an arbitrary student or link from the list, I might have to treat the front guy a little differently from the end guy because they look different from everything else in the middle. So this is consistent with this idea we've been preaching of design. How can you break a problem down to its constituent parts? Well, there's 3 cases, beginning, middle, end. And that's precisely what we'll do. So right now my length list, according to this program, has nothing in so I'm going to go ahead an insert by typing, "3." It's going to ask me a number to insert and I'll say 50, enter. So list is now 50. So this is a very ugly, quick and dirty program that I just spit out what this list currently is. Let me insert another number. Let me go ahead and insert. Let's say the number 61, enter. Program seems to be working. I've inserted 50, then I inserted 61. And maybe it was just appended, but hopefully it's actually been appended in sorted order, let's try again. Insert 51, which will hopefully end up in the middle. And yes, indeed, and we can continue along this way and we'll insert 1 more for demonstration's sake. And we seem to have a running list that if it's consistent with what we're talking about here, is growing. And is growing, and is growing. So a very underwhelming program. We could have implemented this a week, 2 weeks ago just using an array but if I start inputting in enough numbers, as you pointed out, eventually we're going to hit a hard coded limit at which point you have to do this somewhat annoying, somewhat time-consuming process of creating new array, copying the old into the new and then repeat. Now, give the examples we've discussed. Students and the example last week, it's really not such a big deal. Looping from 0 to 3 or 0 to 10 or even 0 to 1,000 is really not all that problematic. So why do you think that this constant resizing of arrays might actually be a bad thing? Why bother introducing what seems to be more complexity, even though you could have solved this problem last week using the semantics of last week? At what point does that approach to dynamism growth become a problem, do you think? >>[inaudible audience question] >>Yes. >>[inaudible audience question] >>Exactly. When the time actually gets noticeable, either to your CPU or worse to the human. So a number of you have posted questions on the course's bulletin board about problem set 4 in Sodoku, like, is it okay to exhaustively check the whole board this 9 by 9 grid that's 81 separate cells. It feels like a lot but again you have a billion hertz at your disposal. You have a gigahertz, 2 gigahertz. Checking a 9 by 9 grid that's really meaningless. And we saw as much when we talked about amitotic behavior and we did some searches and sorts for small data sets. The running time is fairly negligible, but these days, and after a class like this, you're going to start playing with much more interesting data sets, whether it's because of computer science, or you go back to your bio labs or your chem labs, where you actually had interesting sized data sets. Again this naïve approaches, these week 2 approaches of storing things contiguously in memory probably aren't going to cut it because you're going to start to incur the costs of time, of space, of CPU cycles. All of that begins to add up. So, how much do we go about doing this? Let's take a look. In this code is list 1 dot C. And we have the following setup. Let's just glance at C for the moment. So main looks like it's pretty simple here. Print def I have some new lines, and this is a little trick. If you've never picked up on this before, or haven't seen it in a TF do it. If you have a multi-line string, it's not the best thing to call print def, for instance 6 or 6 times here because anytime you recall a function, you actually incur a bit of cost because of all of the stack frame stuff that we discussed. So you can actually call print def 1 as a multi-line string and notice I have not put semicolons at the ends of any of these lines but I have closed the strings in double quotes each time. All right, so scrolling down, it looks like I'm using CS50's library, telling the user to give me the command. I'm using the perhaps now familiar script construct, though I could have used an if-else. I have 4 cases, I call a specifically named function that's in the case that we need to delete, find, insert or traverse the list and then again we do this wild construct because it's a user interface. Well, let's see a hint of the notation here. It looks like I'm doing some stuff with pointers at the very end, just to free the whole list. And that's consistent with this idea of managing our own memory. But how do you represent linked list in the first place? Well, if you have an empty list, how can you represent an empty list? What primitive do you need, I potentially left the answer on the board. How do you represent an empty list, what do you need? Do you need a struct? Do you need to call Malok to represent a list of size 0? No, you just need what? >>[inaudible audience question] >>So a null pointer. Where can you store it? Looks like in this program we've decided globally to declare a pointer called first. It's a type of node star, which means that this thing is just going to hold an address of the thing that it's going to point to, is going to be a node. So that's all that's saying, and it's consistent with last week's definition of pointers and we're going to initial it to null. Which is to say, in the context of a data structure like this, we simply want to create a new list or represent a new list we won't have had occasion to call Malok yet, so we won't have an valid addresses, so we simply need to declare 32 bits of memory. We'll call this apparently first. And what's going to be inside of it? Well, unless we assign it a value, it's going to have junk in it. Which is why in this case, we've initialized it to null. So that's it. So now think just conceptually. When I call the insert function. When I type in the number, what was it? 3, the insert function is called and I type in thereafter the number 50. So that's what I did in the little demo a moment ago. What is the insert function probably doing? Step 1. The insert function, based on the behavior that we saw, is doing what first? And just to remind, so if I run this linked list program, and I type in 3, what's it doing first? So it's doing a print def, and then I'll only jot down the more interesting 1, it's doing a get in. Right, it's probably using the CS50 library also. And here's where I typed in 50. So what did it do with this value? Get it? It probably stored it in, and I'll write slightly more complete code, it probably stored it in a local variable called N, or whatever. So N equals get in. This is probably the code that was just executed. What it probably doing is step 2, when I then proceeded to hit enter, thereby putting a value in N. If the goal, again, is to construct dynamically, one of these things called a linked list. Just conceptually, what did it have to do? >>[inaudible audience question] >>Sorry? >>[inaudible audience question] >>Okay, so it's got to somehow set this pointer, which has up until now still null, to point to this value. So we can't- this is not a pointer to an int, so we cannot do, for instance, this. We cannot, if this is the int in memory, we cannot just have the pointer point to that int and no longer be null because what is this a pointer to? Not an int, but- >>[inaudible audience question] >> A node, okay. So how do we make that happen? If we need to have this pointer point to a node, and all we've got in memory at the moment is apparently an int, what do we need to do, or who do we need to call? >>[inaudible audience question] >>All right, so we call Malok. So we call Malok with something like this. I'm going to do a node star. So this is pseudo-code at the moment. So I'm just going to use PTR, this is a constant variable people use as pointers. So this gets what? I need to call Malok, and then what do I ask Malok? 1 node, as I ask in that slightly sarcastic voice, the answer is no. So what do I put in here? >>[inaudible audience question] >>Yes, so size of the node. So we need to ask Malok for a specific number of lights. Now maybe I know how many bytes there are in a struct. In fact, if I think it through, a struct called node has an int. If it has an int and a pointer, I actually can guess how much space it's going to take up. How many bytes is a node struct can you infer? >>[inaudible audience question] >>So it looks like it's 8. Because I need 4 bytes, 32 bits for the int. And another 4 bytes, 32 bits, for the pointer, because all pointers are 32 bits in this environment. So that means 8 bytes so that means I actually go a bit riskily type in 8 there and get the number of bytes I need. This is not a safe assumption to make, because it's not necessarily the case that the compiler or the computer is going to give you just 8 bytes. There are cases in which you actually get back more bytes and things would so let's instead use the size of the operator. I pass in the size of what? Not ints but node and now, dynamically, I will hopefully get back either a null pointer, but that's pretty unlikely given how few things I've asked for so far, or I'm going to get back the address of a chunk of memory that is now mine to manipulate. Now this is just raw memory but the neat thing is that I can treat it as this is a node. Because the thing about C is that just handed a chunk of memory that has no data type associated with it fundamentally, you if you know how big it is, can just assume that you can treat it as the struct in question. So the fact that we're saying node star pointer means that with the memory I'm getting back, even though it's just a generic address, I'm going to proceed to treat it as though it's the address of a node struct in memory. So now what do I do in step 3, most likely? I've got an N and an int. I've got the address of a chunk of memory that I can use for a node now. What do I need to do as the next step to create the beginning of this linked list structure? What needs to happen next? So here I have, just pictorially, my int, it's got my number in it. This thing's a little bigger because it has 2 fields ready and waiting for me. So what do I need to do? >>[inaudible audience question] >>Yes, so put the int into the node, so how do I do this? Well, we've seen that we've not used it that much. In fact, before, if I want to go into that address and follow that address to the memory location, but I want to go to a specific field, the notation is this arrow notation so I'm going to go pointer, arrow and then the field I want to update is called what? >>[inaudible audience question] >>Little bolder. N, right? So go to that address, go the field. I have defined as N and assign it a value of N. Now you might be recalling issues of scope, you might recall when we had the same variable names before was problematic. But this is okay, because the compiler very quickly realizes that you want the variable called N, the field called N, that's associated with this pointer, with this chunk of memory. Whereas N just in this vacuum clearly refers to the local variable that we're using here. And let me reangle this, in case those of you on the side are having trouble. So there's 1 last step to clean up the memory I've just been given. I have this. I have the same memory question mark question mark But, at the top now, I just have the value of N is, so let's put 50 in here. 50 is now also in here, but what's this? >>[inaudible audience question] >>It's just garbage value. Because it's just a chunk of memory I've been handed. So step 4 is probably going to be to do what here? >>[inaudible audience question] >>So create a null pointer. And it's probably not the best verb to use, since you don't actually create pointers. This is just a hard coded value of zero, but that's the right idea. The next field of this struct is just going to be null. And now what I have is something that looks like this, 50, and then null field here and actually I'll draw it graphically, but what most people do to represent null is just a backslash, or some kind of angled slash in the box. Okay, now that's step 4, but I haven't actually created a linked list. At this point in the story, my linked list appears still to be empty. So the fifth and final step is going to be what here? What needs to happen now? So we're so close. We have this thing just floating somewhere in memory and that's fine, because memory does not need to be contiguous for lists. This thing here is our global variable called first, which we initialized per the code we saw, is initialized to null. So in order to literally connect these things, what do I need to do? >>[inaudible audience question] >>Yes, so assign first the value of pointer. So the last step is first get, which is currently null. Let's overwrite the value of null with the address of this struct in memory. So pictorially, what I just did in step 5, is that I changed the value of first to be from null to being something like O, X, 1, 2, 3. Or wherever this thing happens to be in memory, but that's not really interesting any more. The specifics anymore, so let's just draw it with our familiar value notation. Now what I have is that. So to do recap in step 1, this old school stuff. Get the ints. Step 2, allocate space for the structure that's going to store that int. And another pointer, so metadata, if you will. So that we can string these things together. Then what do you do? Put the int into that structure. What do you do then? Put null in the next field of that structure so that you don't reach a garbage value and assume more things in this list than there are. And then finally, you just need to link things together. Your list was previously empty. You now need to wire things together. So now what do I have in memory, even though this thing's a bit messy on the board, let's spin it around for 1 final clear picture. Our linked list now is quite simply first and then we have the number 50 stored in a node here. This arrow points here, this is a null pointer. Voila. That's our linked list. Now, this felt like a lot of work. It's easy to create an array with the number 50, done. We did that last week, we just syntax int. We'll call this array, bracket, 1. So we've just done a lot more work. But, if we now factor out these concepts, these operations, like insert and later delete, spine and traverse. Then you just have to call it a function. Hand it the linked list, or have it have access to this first pointer, and then you can repeat these same operations again and again and you as the programmer no longer have to worry about how big this structure needs to be in advance unless the user really wants to push the limits of reality and ask for billions of things, which again tends to run afoul of some real world limitations. So, any questions? So that was either really clear or really confusing, and I'm not sure which, so I'll ask you again. Any questions? Well that's good. Thank you. So I'm not sure you can see this, but thanks to Harvard's financial crisis the temperature is intentionally being raised in the rooms so I apologize if you can see the glistening here. But, let's now put you guys in the spotlight. So we're not going to use the clay. I'm not sure I can take myself seriously playing with Play-Dough in science [phonetic spelling] theater. But if we could get 4 humans up here, we won't be playing with this, you'll be a compliment to the clarity. So come on up, you're number 1. Someone else, yes in front? 2. And you do have to be comfortable, yada yada on film here. 3. And 4, you stood up so you nominated yourself. Okay. So we've done things like this before and I'm always amazed by how many humans are willing to come up here and do these silly things. But what I hope is that what we just did on the board is very easily forgotten. It's fairly esoteric kinds of low level details. But let's see if the visualization doesn't make things a bit clearer. So let me go ahead and I'm going to use 3 of you guys, just as a chunk of memory. So if you could duck off to the side, for just a moment. We're going to allocate you in a moment. And you're name is again? >>Alex. >>Alex, you are a pointer. So you're a null pointer, it's just say you keep your hands at your side there. Just don't point at anyone just yet. So you guys are a chunk of memory. So you are RAM. And now, we'll start with small numbers. I decide here that I want to insert into this currently empty list called Alex. A number 2. So I call get int, I am handed the number 2. What's my next step? Malok. So I'm going to allocate memory. I'm going to ask the operating system for 8 bytes of RAM please. Nominate who you will. Okay. So I get back a pointer to- your name is? >>Olga. >>Olga. So I get a pointer to Olga here. She is 8 bytes of memory. I'm now going to do what, with respect to our chunk of memory here? >>[inaudible audience question] >>It's not fun if we're the only ones playing this awkward exercise. I'm going to store in the field called on, which they're going to represent with their hands, just as Alex is doing. And value 2, and why don't we stalk here just on the side a little bit so we're out of the way. So now she has a pointer. And your left hand is your value and your right hand is the pointer. Or actually, let's do the opposite. That way, that'll make sense. So now we were at wherever we were- this is, we just did step 3. So actually, we're almost there. So that's step 3, but we really don't have a linked list, we've got a null pointer and we've got a chunk of memory only half of which has been used in an interesting way by storing 2 there. What do we now need to do? So we now need to store a null pointer here. So for dramatization's sake, can you make a garbage value with your left arm? So that's before, and now we initialize your pointer to null. Excellent. First time we've ever done this demonstration in CCS50, so we're figuring out as we go. So now what's the fourth step? >>[inaudible audience question] >>So actually point the first variable, that's right, to this new chunk of memory. So Alex, your time to shine. Excellent. Good. So we've now just recreated what we had on the board, except with a slightly different number. So now things get a little more interesting, though. Because now I get a little greedy and I decide that I want to put in, say, the number 3. So I call get int. I am handed by the user the number 3 and I just side step 2 to call Malok again. So Malok away. Hello, what's your name? >>Julie. >>Julie is returned to me, the address of Julie. She too has in her right hand space for an int. And in her left hand, what's in both of- oh, this will embarrass you. What are your 2 values right now, we need you to represent 2 garbage values. Thank you. So now we store in Julie's N field in her right hand is the value 3. What do we do for step- let's keep track for those following notes. We just did step 3, step 4 is to do what? >>[inaudible audience question] >> Good. Assign null to her left hand. Done. And step 5, finally, is to have what? Alex point at Julie? >>[inaudible audience question] >>No, right? So, what do we need to do if the goal, to be clear, is to sort the list? So here we need actually a bit more work. Here we need a temporary pointer. So I'll play that role, and I need to initialize myself to the start of the list. What does this mean? It really means that I'm going to point to the same thing Alex is pointing at. So now I'm going to check, let's check Olga's N field. Is 3 less than 2? No, so I'm going to keep going. Now, unfortunately, I'm pointing at nothing. Which means I've reached the end of the list, because Olga has nowhere else for me to go and so this implies that this number 3 goes here. So now, very carefully, and we haven't walked through these steps, what needs to happen now? To add Julie to the correct location on the list? 1 step, in fact. Your time to shine. >>[inaudible audience question] >>Very good. But for intentionally plucking off some of the easier ones. Now, finally, we're going to go with the number 1. All right. So things get a little trickier. I call int, I store number 1 in my variable called N. I then call Malok. Hello, what's your name? >>Robert. >>Robert, nice to meet you. So you look like what at this point in the story? That's great. So now we assign you this number 2 N, which goes in this hand here. Now, again, Robert, if I can drag you in this direction. You're anywhere in memory. So you could be here, okay. Yes. Can't see in the camera. So now Robert has his N field initialized. Left hand is still doing whatever. So step 4 here is nullify your pointer. Good. So now he's in good shape. So now it's my turn, the temporary pointer and I have to have some kind of loop again. Maybe it's a foreloop, maybe it's a wide loop so I point where Alex is pointing. I then check, does Alex belong here- sorry, does Robert belong here? Yes, to the left of Olga. So now there's a bit of trickery. So now let's see what we need to do? What would you, the audience propose that we insert Robert into the right location here? What's the first step? By a show of hands, so we can actually pinpoint the voice? Yes, in back. >>[inaudible audience question] >>Alex has to point to Robert. Alex, please point to Robert. Okay, now what? >>[inaudible audience question] >>Yes. So now dangling pointer, as this is called. Because we've now lost Olga. We've lost Julie, which means you've just cost us a lot of RAM. Now your computer is going to slow to a crawl. But thank you for playing, that's good. Let's roll back. R, Control C back up. Rerun the program here. And again, Alex is pointing at Olga, we do do this check, we realize Robert doesn't belong to the left, let's do a new first step. >>[inaudible audience question] >>Okay, so Robert points to Olga. Robert points to Olga, looks a little weird but maybe this is okay. Then what? >>[inaudible audience question] >>Now Alex points to Robert. Now, this is actually realistic in that the memory can be all over the place for visualization's sake, let's cheat and have Robert come over here even though he really is anywhere in memory. But now notice what's- so that was actually a bad part of the visualization, because the compelling thing about linked lists is that you don't actually have to shuffle people all around. And this was one of the problems initially with arrays, which is if you wanted to insert something in the middle, we had a problem. We saw this with our searching algorithms and our sorting algorithms. And if we wanted to put somebody into the middle, we had to shift all of those people over. But as soon as we started shifting, we started increasing our running time, and we started devolving, if you recall, to things that are quadratic and no longer linear. But yes, even though the humans here didn't need to make room for the addition of Robert, technically, they're just updating pointers. So the first pictorial with him way over there speaks to the fact that it's much more efficient to insert here because we don't need to worry about contiguousness of all of these elements. But big round of applause if we can for these 4. [ Applause ] >>We have a little parting gift here for you today, I'm not sure how you'll use this. But thank you, let's take a 5 minute break. And you people, I need to see you in the corner. >>I already signed this. >>Okay. >>All right, we are back. Brings the fun to a crashing halt, because now we have some code on the board. So you have, in your slides, that will be available online, there's actually a number of depictions of what we just did with humans. So realize and refer back to this couple of weeks time, because what this is meant to seize your minds for, for problems that sticks, which is a little bit aways away but it's problems in t6 you'll find that your challenge is implementing the fastest spellchecker possible. And we pretty much take off the training wheels at that point and encourage you, and invite you to implement your own choice of data structure. We haven't seen many yet, we've seen linked lists, but you'll find that these linked lists from today will become a building block for much more sophisticated data structures that we do in 2 week's time. So these pictures realize walk you through the process of what just happened, perhaps a little quickly with humans on stage. But what I'm going to do instead, instead of walking through this again and again, which is what we pretty much just did, let's focus on the actual implementation of this. Because some of the syntax is new, but hopefully the concepts, once visualized with some people is now a bit more clear. So this is the guts of the insert function. So again, you'll have a printout of this, this is list 1.C. In lists.H, note actually has the definition list 1.H has the definition of the struct. Just to be clear, I factored it out to this header file, which again is pretty typical and any time you want to declare some data structures or you want to create a file that other people might also use via sharp include. So here's the function insert. It takes no argument because we're going to ask the user for a number to insert this coin. But notice what I'm first doing. I've decided at the very start of the function called insert. Try to substantiate a node for the number. Now I'm doing this because I know that once I get a number from the user, I've got to tuck it away inside of things. So the order of operations here is a little different than we did verbally, but we're going to cover the same steps. So the syntax for this is, give me a pointer called New Pointer, could come up with most any variable name there, and it's of type node star. Let me scroll back to that. So it's of type node star, which means give me a pointer to a struct that a type node. Okay, I'm calling Malok, passing in the size of a node. And just to be clear, why not just hard code the number 8? Why incur the expense of calling this? Yes? >>[inaudible audience question] >>In case you want to enlarge the struct, and again, even though this is more of a corner case but we can see a taste of it in problem set 5, forensics problem said you're not, even though we draw N on top of next sort of back to back in our picture, that doesn't mean they're going to be perfectly back to back in memory. Now, in this case, in reality, they probably will. But if we start creating data structures that don't have these 4 by values, an int and then a pointer, or maybe a char another char, a float. And then you start to comingle lots of different data types for efficiency's sake what the computer will do is word align these values, which just means that it's going to try, for efficiency's sake, to line them up every 4 bytes which means you might have gaps. Another motivation for actually keeping track of this thing here by a size. So here's a little sanity check. If I get back null, just return. Now I don't bother in this particular demo to tell the user anything. I just ignore the user. So it's unfortunate, but at least we handled the return of null. Because if you take a null pointer and try to follow it, you will in fact segfault. And that's a feature of the language. Null is a constant that represents the number 0. The number 0 is a valid address and memory. Right? 0 byte of RAM, but the authors of C essentially decided that this byte will never be owned by the user. So it will always trigger, a segfault, so you know there's a problem. So that's actually a good thing, initialized to some known value. So here's what our first step was. Printout, number to insert. Let me go into that, and actually saved a step here. Didn't bother wasting the space for a local variable. I just flopped to the end of the user give me directly into the struct. Reasonable optimization, but it achieves the same task. But then I do very carefully initialize the next field of my node pointer to null. So that's precisely what we did on the board and pictorially here. Now I'm just going to check the 3 cases. So at this point in the story, we had Olga holding a number and then we had Alex pointing at nothing. So we now needed to consider the scenarios. Is Alex pointing too something? Because if so, we're going to have to traverse the list. If he's pointing to nothing, that's actually really nice because it's really easy to code. If Alex is currently null, if the first pointer is null, well this is so easy. First gets new pointer. Just make Alex point at Olga as he did, then we're done. But there's a couple of other cases. Apparently, I need to check if the number belongs at the head of the list, the start of the list, or if it belongs in the middle or turns out you can model the tail, the end of the list, in pretty much the same way as the middle. And the only way you would realize this, frankly, is by thinking it through. This is not necessarily obvious. But let's go with the slightly easier case. I like 2 lines of code instead of several there. So case 2 is, if the number we just inserted belongs to the list's head. So now fast-forward to the situation involving Robert. Robert was number 1, he belonged to the right of Olga. So Alex would have to start pointing to him, so the case there, we had them update 2 things. And we didn't quite get it right at first, but we did subsequently. We first told Robert to point at first. Wait, I'm a little confused. Isn't first Alex? Why does this actually work? What is first? First is a pointer, it's an address. What's it the address of, to be clear? So it's Olga. So even though we talked about Alex and representing this first pointer, the value of side of him actually represents the address of Olga at that point in the story. He's just a container storing an address. So when I say that the new pointer's next field equals first follow Alex's hand, which leads to Olga and store that address inside that field. So it's the same thing, but just realize that Alex himself was not a node, Alex did not have 2 fields, he just had an address which is why this direct assignment makes sense. Now we told Alex, go ahead an update yourself to be the address of this new node, that is point to Robert. So at this point, I'm not sure whether your mind prefers the model of just thinking about things as arrows and human's pointing at each other, or if you prefer thinking in terms of addresses, this approach too is literally a translation of what we did in that demonstration. So if you're more comfortable thinking of things as addresses, if you're more comfortable thinking of them as arrows or hands, that too is fine. Now let's glance at the slightly more complicated case and this is where your brain gets a little squeezed because you have to very carefully consider how to do this. But thankfully, you do it once, and then your insert function works. So let's consider, ideally without getting lost, how we go about inserting in the middle of the list or to the end, the tail of the list as we did with Julie in that second scenario. So what I'm going to first do is this apparently my role. When I came over, I was pred-pointer, predecessor pointer. And I chose these variable names just to be consistent with the textbook's figures. I pointed at the same thing Alex was pointed at. So that highlighted line of code is exactly what I did, with that temporary variable called, apparently, pred-pointer. Now I just need an infinite loop, and it's okay to produce an infinite loops using fore or wild, so as long as you are sure, logically, that you break out of it, if that's your clear goal. So I'm first going to check this, and we didn't bother doing this because I didn't print duplicates on paper, but I am going to check. If the pred-pointer is end field equals the new nodes end field, we'll forget about this. I don't want duplicates in this list. This is an undocumented feature of the demo that we just did. This feels a little foolish, though. So some of you might notice, I just wasted some time and allocating a node at the top of the file, the top of the function using Malok. And yet this feels dumb. Only then do I check for duplicates and deallocate by calling free. What would be an alternative to this because this feels like I'm wasting time by allocating the node and then realizing, damn I don't need this node, here it is back by calling free. What's an alternative to that approach? >>[inaudible audience question] >>Yes. >>[inaudible audience question] >>So just intuitively, I'll just do a pre-check. Let me run through the whole list, which is pretty easy to do with the foreloop and I just did it by pointing again and again to the humans on stage. Let me just do a sanity check and if I find a duplicate then, maybe then I can actually quit. But now I've essentially doubled my running time because if I do this pre-check, I have to linearly go across the whole list, then I might say there's no duplicates, now I have to find where to go. So that would work maybe we could do slightly better. And maybe better just means let me just allocate the moment I need it, this node, and don't do it at the front of the list. In other words, let me go ahead and copy these lines and down here, when I actually needed the new node, I could insert this code here. But the reason I didn't is that I have these multiple cases. If I had done this approach, allocating this node on demand, now what do you notice me doing, which is generally a bad thing? >>[inaudible audience question] >>Copy paste, right? Duplication of code, there's clearly an opportunity to rip that code out, so it's just a trade-off and it's a design decision that one could argue. Maybe either way, but generally when you resort to copy paste, there's probably a better way. So at this point, we're going the right direction, it seems. I have my node and maybe duplicates are a rare thing. So maybe we could argue that it happens so rarely, who cares? Every once in a while we spend a few extra cycles. That's a reasonable decision to make. So let's see. Check for insertion at tail. So there's 2 cases in this bigger case. Is it in the middle, or is it the tail? After a lot of thought, and maybe some trial and error, I realized that it's a little easier for me to check insertion at the tail. So if the temporary pointer, me, if I'm pointing at nothing, as I was in one situation when we were inserting Julie, then it's actually a really easy case. Go ahead a new structure, go ahead an point to the end of the list, whom I'm currently pointing at, to the new node. And again, I won't go too long on too much of the code because I know it's easy to get caught in some stupid little detail and that's fine reasoning through it with the picture in hand can certainly help afterwards. This is just the translation of what I did to insert Julie at the end of the list when only Olga was there. The list was size 1. So now let's assume, and we didn't do this per say, because we inserted Robert at the beginning, not at the middle, but there is this last case. So this is interesting. You can actually chain together this arrow notation. If I am the temporary pointer, pred-pointer, and I follow the next field and then I follow down into the end field, so gone 2 steps. If that equals the N in the new node, I know that this node belongs somewhere in the middle and so I need to update 2 pointers here. And again, I don't want to dwell too much on the syntax here, because I think it's best done by drawing a picture on the sides, thinking this through. But the takeaway, that I think is interesting, that there just needs to be 2 pointer updates. So we've really only seen 2 general cases. 1 pointer update, which was terribly easy, and that's why we did those examples first, and that's why I myself coded them up first and the only more interesting examples is when the thing belongs to the list's head, we realized we needed to update 2 pointers in the proper order, and similarly if it belongs in the middle, just conceptually we have someone here, someone here- certainly we need to update 2 pointers so they point to me and then I point to them. So the reason for this double traversal is because once you go left, you can't go right in a singly linked list. A singly linked list, by definition, has only single lists going in 1 direction. So as this picture here depicts, this is how it relates to deletion, which is the same idea when searching through a list and then wanting to delete a node, what do we do- let's actually do insert in the middle. And this is the one with several steps. If we want to traverse this list, notice, just as the arrows indicate, we can only go left to right. So it turns out that sometimes, for programmer's convenience or for algorithm's sake, you can throw more metadata into these structures, there's nothing stopping us from having not only a next pointer, but also a previous pointer. Because in fact, it would have simplified some of my code if I had the ability to traverse the list this way, and then looked backwards because then I could have eliminated, if you look closely at the code in problem set 6, I could have eliminated one of my temporary variables. Because, again, in that code I had myself and then there's also a temporary variable who's essentially following what's going on in the story a left hand and a right hand, if you will. But if I have the ability from any node to go left or right, can I then get rid of one of those temporary variables? But this, again, hints at this trade-off. I can double my number of pointers, save myself some thought, saver myself some logical coding, but the downside of course is that I'm spending twice as much memory on these pointers. But here's another question, and this picture spoils the fun answer. How do you determine the length of a linked list, according to how we've implemented it thus far? Which is a picture more like this. How do you determine the length of this thing? >>[inaudible audience question] >>Just traverse it, right? Start at the beginning, start where Alex was, and go duh-duh-duh-duh, following the arrows and as soon as you hit what do you stop counting? The null. As soon as you hit the null pointer, which was originally at Olga then at Julie, their left hand was null, then you know that you're at the end. And so long as you are keeping track with an N plus plus plus plus, you know that the list if size three. But that's a little inefficient. Here, too, is this trade-off. We could probably spend 32 more bits up front and actually avoid having to recount the length of this list. If I'm writing some programs that constantly requires that I know the length of the list, why not just compute it once, and keep that answer around. So what this picture also hints at is that Alex did not need to be so simple. He did not just have to be a pointer to a node. He himself could have been an entirely separate structure. We've seen how to define a struct. Type def struct and then some name, whatever you want to put inside. We could have made Alex a special struct that we used 1 copy of, 1 of his fields is in fact a pointer to a node. But his other field maybe is, as this picture implies, an int, the size of the list. So what I could go do, is go back through all of my code and go back through all my demonstration and every time I insert, say, Julie. Every time I insert Robert, not only do I update the 1 or 2 pointers that a requisite for that. I also do what to keep track of the current length? Then do the plus plus there. So again, this hints at the opportunities that you, as the designer as a computer scientist has to solve problems more efficiently. If you don't want to waste time again and again. Incur linear costs, linear costs just to compute the size of something, the length of something, you can solve that a priori by keeping that information around. Linked lists are only 1 interesting data structure. And again, we will use these before long for a problem set. Another canonical example is this 1 here, a stack. And the cheesy example most any instructor gives when discussing stacks is that it takes some photographs of some phrase like this and cafeteria and much like you experience as a human, when you put a tray on top. When the folks running the dining hall put trays on top on top on top of one another, the last 1 in is the first 1 out. In other, words, the top tray is the first one you, the customer actually take off. So a stack is another data structure that is what's called a LIFO data structure. Last in, first out. Now this actually has some applications that you'll cover in courses like CS121 or even, if you've ever written HTML, made web pages, you know there's a structure to them. There's a hierarchy where literally, if you indent things properly, even though it's not required, it gets in deeper and deeper and deeper and deeper. You can actually parse, you can actually analyze a webpage for correctness and for other purposes, using a stack and the idea, just as an aside is that each tag you read, you push onto the stack, push onto the stack, push onto the stack, so you have the most recent tag latest and then you can check your indentation and all of your symmetry is right by going backwards. But there's more useful purposes than just that. But this is a LIFO data structure, but all a stack is some chunk of memory that you can put something here, then something here. Here, here, here, here. But this is just a general data type, an abstract data type. How could you implement this idea of a stack? Using what C primitives or basics? >>[inaudible audience question] >>Sorry? >>[inaudible audience question] >>So we have a couple of data structures that are disposable. What is the simplest way to dispose of this idea of a data structure that looks like you put something on top of something on top of something. We've done this, right? We just always drew the picture like this. Something, then something and then something and then something. Right, it's just an array, just flipped conceptually upside down. But there are some constraints. And here's the distinction array is really not an abstract data type, it's not a proper data structure in that you can go anywhere you want. So in that sense, there's no- it's much simpler than the things we're now discussing. Whereas a linked list, you can't go to a random element. You have to start at the beginning, search through it and that now has a more interesting cost but with stacks, what is the only element in a stack, at least in reality, that you can access in a given time? The top tray, right? If you assumed 1 stack of trays here, the only one realistically you're going to get is the top tray. Going anywhere in the middle or bottom is just not physically feasible, generally, so the operations that a stack typically supports is something called push and something called pop. And these functions would just be implemented, whether they're using an array or even a linked list to add or remove elements from this stack. But there's another one. So this is a silly picture of some crazy people lined up for the iPhone 3G in New York. So this is a queue. This is a line, this happens all day long but there is dare I say even more common data structure. In computer science or in programming in general, because this data structure is a FIFO structure. First in, first out. That is, if you get there first at the front of the line, you're the first one to buy the iPhone. And this has fundamentally different applications, right? Queues, or queues in this real world sense are a much better solution to the problem of fairness than a stack. Imagine if you were 1 of those crazy people who wanted to get an iPhone that first day and Apple, because they're a computer-minded people, decided to implement this thing as a stack. Right? You'd be ticked off, right? Right now, that's something that a computer scientist might actually do. But anyone with a queue similarly has insert operations and remove operations. But fundamentally those operations manipulate different pieces of data. So anytime fairness is important, queues are used. So in fact, you might generally note that the internet has routers. Devices that take data from point A to point B and they send them every which way. Well, routers have RAM they have memory, they have hard disks often. So when they get overwhelmed by traffic spikes, a lot of people downloading something in a given time, the routers can't handle everyone's traffic all at once, so traffic starts to back up. So thankfully routers and many other devices have queues, chunks of memory, whereby a packet comes in and then it queues up, a whole bunch of packets come in and when the router finally has a moment to deal with your data, or your download, does it finally move you through the line. But here, too, there are interesting opportunities. You might note that some people like to prioritize on the internet. Or would like to prioritize data like voice traffic. Or they'd like to deprioritze downloads of illegal movies. And the ways you can do this is by using different data structures at the router level to prioritize different data. Queues is a pretty fair thing, but if you want some other type of traffic to go through that router first, a queues is not necessarily the right data structure to deploy. So those are just teases of some of the data structures to come. What I thought we'd do is end on this note. Very common in this point in the semester are bugs in your own code. We mentioned several weeks ago, that 1 of the first bugs, or one 1 of the most defining bugs in our history is this one here. When the great Grace Hopper or one of her colleagues pulled out what was literally a bug from the Mark 2 computer and then was entered into the notebook here and they had a good laugh, ha-ha, computer actually has bug. Well, there's been some stupid bugs. And we are at the stack, by no means guilt-free of this. We make mistakes, you make mistakes and so what I did was troll around for some inspiring, reassuring, if not humorous errors. This one you might have seen. How many of you have ever seen this on your own piece of tape. So this is called the "Blue Screen of Death." Not a terribly helpful message, but frankly at this point in the course a fatal exception 0 E. I have no idea what that means, but hexadecimal. I can now understand a little bit more of this thing. Has occurred at 0 0 28 cog pull in some other stuff. VXD, that happens to represent virtual device driver. You wouldn't know that other than by Googling. But this was Microsoft's early on form of a really bad error message that you know what? Is actually useful, just not to most of us in this room. In fact really none of us, to Microsoft's engineers, on the rare occasion you might be able to tell them what number you're experiencing, this is some kind of error code indicating a problem in this driver. Well, this one, too. Similarly arcane, but perhaps is a little more accessible. I have no idea what the problem was in this program, explorer dot exe. But the instruction at OX77FF. So that's an int. That's an address in memory, referenced memory at some other address. The memory, and this is the funny part, I think. The memory cannot be read, just want to emphasize that. But this was just a bug in the program and frankly, it sounds like it was some stupid pointer mistake. So if you ever do see this message, that's really what they're hinting at. This is just a bug in many ways. So this is a legitimate error that someone took a screenshot of. Now things devolve into less compelling ones. This is cute. [ Laughter ] >>This one, you have to think about it, that is true. So that is many years old and quite popular. This is just a problem. This is within a browser using JavaScript, bad things can happen in even just the confines here. So this is just weird. This is what happens when you start using Google images too much. So this is a tattoo of a blue screen of death on this fellow's arm. He's still red from it, I don't know why. I'm a little uncomfortable with it, but we'll leave the slides online. So this, too, is bad, And I actually thought of this the other day. Fidelity Investment bank on the corner of some street, maybe in New York, so that's a scrolling blue screen of death, essentially. An error has occurred and Windows has been shut down, or something to that effect. And I wish I'd had the foresight to pull out my camera at the time. I was just going through the subway the other day in Harvard Square and the swipe machines that they have to the entrance to the T, I was very sad to realize that whoever designed them, they used Windows to run these things, because the little thing that normally says, "Enter Here," said this. So that was amusing, if you can catch a photo of that, do. So to be fair, this one was actually fun. So this was an advertisement for Windows Vista. The machine, funny enough, was behind glass. Macs are not infallible. This is the Mac version of this. They simplified it, it's a little less scary than the blue cryptic message. Apple, in fact, doesn't tell you there's a problem, just, "You need to restart your computer," cutting corners there. So there's 2, if you start Googling. There's the sad Mac users get. I will not follow the link on the page I found this. And some people have done some sketchy things to their bodies using error messages from computers. I'll link it on the website. This is from Scent OS, a version of Linux. So this, too, happens sometimes. Please insert negative disk 099 to continue. But perhaps the best 1 of all time, no- second to best. This 1 I snapped myself. I was ordering pizza late at night, being a geek, I thought a printout error was cool. So I was offered this upsell to buy some chicken in addition to my pizza, do you see the mistake? This is a print-def fail. They didn't use the right width for the floating points value. So this is $6.30, but they haven't padded it properly to half that 0. And this 1 is perhaps the most famous 1. So some engineer somewhere, years ago, maybe at HP to the light decided that paper cassette would load a letter, or a PC load letter would be sufficient information for millions of people over 10 years to understand when it's time to load the paper into the machine. We are perhaps not the only ones who find this aggravating. I thought we'd end on this infamous note. Slightly R-rated, but we'll end with this. We'll end with this final moment, a wonderful movie, if you've never seen it called, Office Space. >>What would I do if I had million dollars? I would invest half of it in low-risk mutual funds, and then take the other half to my friend [inaudible] who works in securities. >>Samir, you're missing the point. Point of the exercise is to figure out what you'd want to do with it. PC load letter, what the fuck does that mean? [ Crash ] [ Music ] ==== Transcribed by Automatic Sync Technologies ====