>> Unknown: Alright, welcome back to CS50. This is the start of week 7. For those of you that have been playing along at home, there was no week 6 on film at least because of last week's quiz. And now that quiz 0 is in fact behind us, I dare say that you are now qualified to either laugh with or laugh at a little something like this that went around the TF's list this weekend. 

[ Laughter ] 

[ Music ] 

>> Unknown: Hey. 

[ Background noise ] Mom, Dad, this is Ryan. 

>> Unknown: Oh, so this is the famous boy we've been hearing so much about. 

>> Ryan: Nice to finally meet you Missus Lead and sir. 

>> Unknown: So, Ryan, what kind of server do you play on? 

>> Ryan: Is that on, is that on a computer? 

[ Laughter ] You know what? I think I forgot the dessert in the car. 

[ Background noise ] 

>> Unknown: Who do you think you are bringing his kind into my house? 

>> Unknown: But dad, he's a nice guy really. 

>> Unknown: No, he's a newb Jessica, a newb. 

>> Jessica: But Ryan and I are perfect together. 

>> Missus Lead: This relationship is headed for an epic fail young lady. 

>> Unknown: You're elite damn it, we don't take newbs, we prone them. 

>> Jessica: Well maybe I don't like to be elite. 

>> Unknown: You're insolence, for a lose. 

>> Jessica: No, maybe I love that he watches VHS tapes still and maybe I love that his phone still has a cord. 

>> Missus Lead: You might as well date somebody who plays Aliant. 

>> Jessica: I'll take whoever I want. 

>> Unknown: Over my level 80 Roadster Pirelli dead body. 

>> Ryan: Mister Lead. I may run around in circles when I play Halo and I might never get a monster kill. I can't even find the space bar half the time. But I know when I found true love. And that is worth more than all the uber gear in the world. 

[ Music ] 

>> Unknown: Too long, did not listen. 

[ Laughter ] 

[ Background noise ] 

[ Laughter ] 

>> Unknown: It's like the fifth time I've watched that. 

[ Laughter ] So a couple of announcements, problem set 5 went out the door on Friday. This recall is the forensic P set which involves you're not only recovering a secret hidden message but also recovering some photographs that we accidentally deleted. And to add to the fun you'll find that once you've recovered these photos, they are all of persons, places or things on campus and the goal ultimately after the P set is submitted is if you can with your section mates find any or all of those photographs and then photograph yourself or someone else in your section in that same place or with that same person or thing, happy cat excluded. We will award you amazing well in some form later this semester. So you have a few weeks for that scavenger hunt portion. You'll notice on the course's website too that we've been soliciting beta testers for cloud.CS50.net. So CS50 has some super fancy hardware that we bought over the course of the summer that's taken us a little longer to configure it than we would have liked. But finally we debuted this weekend and the cloud.CS50.net is essentially a cluster of servers running Linux, virtual servers actually, virtual machines. More on that in the future. That you all will very soon have accounts on. This is so that we can leave nice.fas and some of its shortcomings behind us and operate our own infrastructure entirely. And this will be particularly useful for you come final projects time because inevitably many of you will go off and want to use a different language or a different piece of software. And because we'll finally be in our own infrastructure, we can just type a few magical commands and wala, you will have with higher probability what you need. Because this P set is related to forensics, I actually smiled when I happened to cross this this morning. A little something stupid as well for you. Oops. 

[ Laughter ] Ok, a few chuckles, alright. So that's from the popular website Icanhascheeseburger.com which we actually used to integrate into the course's own website. We used to have a wall catch of the day. Based on Q guide evaluations and a recent comment made in computer science 61 for those familiar, we decided to remove Wall Cats slightly from the course this semester, but some of you might enjoy wasting some time there. It's linked on the course's website. Alright, so final project. So it might be a little early, but actually now is pretty much a really good time to start thinking about final projects. And thinking about projects that even if you at this point in time have no idea how you, little old you would actually implement something, that's fine because there's much more to come in the weeks to come including a look at web programming and some of the languages, the technologies and the concepts underlying web based applications. You will find on the course's website a few relatively new links. For one, there is this link called seminars. And all of this is linked right now in the course's homepage. What the teaching fellows have done historically and will continue doing this year is offer a number of seminars on topics related to but nonetheless somewhat tangential to CS50 on material that we just haven't the time or the syllabus for, so that if you're interested in learning about developing a voice based application like Shuttle Boy Voice, well we'll have the infrastructure and the tools to make that possible for you and we'll offer a 60 to 90 minute seminar in early November led by one of the course assistants on how to do exactly that. We'll talk about Rails which is another programming environment, iPhone development, Android phone development. And we actually have access to some pretty neat stuff. So those of you who might like to tackle an iPhone app, you might be vaguely familiar that Apple actually charges people typically to download the tools necessary for such, 99 dollars here, 299 dollars there. Well you won't need to pay any such things. We have our own CS50 account that we can make you part of. And also Google has very generously donated a number of Android cell phones to the course. Some of the teaching fellows are actually carrying this around already and have been playing with Google's API, application programming interface with which they've been writing their own software for these phones. And we'll demo at least one of those apps before long. But if you are a student in this course and are already on TMobile ideally or at least AT and T, both of whom uses GSM networks. And you would like to tackle an android based project, a phone based project using one of Google's new phones, we can provide the phone. And if this is something that you see through to throughition, you'll be welcome to keep the phone as well. So more on that in the time to come. And you'll also see that we have built up an archive over the past couple of years of seminars past, all of which were videotaped and made available online. So even if we're not offering something this year on some topic, realize that there's a couple of dozen of seminars from years past. And there's probably going to be some more to come. And also, I keep using this word API. And even though we've not used APIs at least public ones just yet in the course, we will for P sets 7 and 8. But an application programming interface is essentially, think of it kind of like a header file almost, a dot H file that has a bunch of functions declared in it that you can call inside of your own program. But you didn't have to implement the functionality defined in that API. So in P set 8 for instance, you guys will implement a mash up using Google Maps. Well you're not going to have to invent that from the ground up. You will be able to use Google's tiles and graphics for various maps around the world. You'll be able to use their JAVA script code that allows you to drop little markers on top of maps and pan from location to location. So you'll have a lot of functionality just handed to you in the form of an API or perhaps a library which just means Google has written a lot of functions or methods that you can call in your own code. And then actually wire things up in a more interesting way. So what we've started doing on this page here, which is also linked on our homepage now, is we've just started linking what we think are some fun APIs. And we don't specify on this page what you might want to do with them. The hope is that you'll skim this list at some point and just say oh wow, I had no idea I could do this with Facebook or I had no idea I could do this with Google or Twitter. And then hopefully it will start to instigate some ideas in your own mind. So we'll release formal specs for the final project in a few days time. By next week when we look at, start looking at web programming. But again the hope now is just to start fostering some thought. And it's funny, you've seen on CS50's website that we've been dabbling internally with various apps for events and news and shuttles and all of this. Partly just because we can and hopefully because people find it useful. But we actually had a staff member at Harvard email me the other day saying hey I've been using Harvard News. It'd be great if you did something for Harvard Twit, Twitters, so people who use Twitter, the Twitter audi. So I up until a few weeks ago had never let myself say words like Tweet and similar words, but I've kind of sunk to that now. I don't yet do it myself. Although I have a lot of followers on Twitter because I signed up like a year ago for a Twitter account because we were playing around with CS50 ideas. So apparently people have just been subscribing to mail in it post for the past 12 months. I've never said one thing. I have a lot of subscribers. Maybe we'll start doing something with it at some point. But in any case, I was inspired. So I was away at a workshop last week and I had some down time in the hotel room late at night. And I figured already, maybe this could be interesting to do something with Tweets. And so I figured, you know I vaguely knew what Twitter was and how it works and I figured, alright, they're pretty hip, they're pretty huge now. Maybe they have an API, some way of me interfacing with their data and with people's tweets and all of this so that I could present it maybe on a Harvard specific basis in my own site. So I Googled something like Twitter API, hit enter and wala, Twitter API Wiki or here's the documentation. So I spent some time that night just kind of reading through this. And a lot of this frankly I didn't really need. You'll find that even within Google's APIs, there's a lot of functionality you don't care about. So it need not be overwhelming but rather kind of exciting what you can do with this. And I found ultimately that I could serve through tweets that had been posted around the world. I found that I could search for a specific user names and get their icons and get their actual names and URLs and so forth. And so you know a few hours later that night and then a few hours later the next night, once I had touched things up, thus was born Harvard Tweets. So now we have another stupid little website that simply aggregates tweets from people who know about all over campus, whether person or department or group. And what we did was write a few scripts behind the scenes that synchronizes this site here, Tweets.CS50.net with Twitter's own dataset every 5 or so minutes. So it's actually fascinating since that hotel room last week, Harvard affiliates have tweeted 2344 times. And that number grows by the minute. This was kind of my innovation last night. And innovation is generous since I didn't really do anything here. But I found this on someone's blog just randomly. And I was like oh that's a really cool tag cloud. It's actually a cloud or a sphere. So this is actually a flash animation but this guy too had open sourced his project. He made available essentially what was an API for putting your own words into a 3D cloud like that. And so what these are, these little hash tags in Twitter speak that are simply key words that you can then search on. So if I go over here and I'm curious about people talking about baseball, I can click that. And all of the sudden I get all the recent tweets about baseball, people that have mentioned it. So. 

[ Laughter ] You would be amazed, ok. So. 

[ Laughter ] Alright, so this is ridiculous. You should see how many posts come from Harvard FML. This is since like last Tuesday night in my hotel room. So you guys are out of control. 

[ Laughter ] So, anyhow, at some point soon we might need a new filter of sorts because if you start skimming through this morning alone, I think it must depend on whoever's running the site when they actually wake up and start approving things. There it comes, so that's last night. I mean it starts to overwhelm. But the point here is I mean partly just to distract perhaps. But also it's actually really just neat what you can do. So now you guys have like half a semester behind you essentially and you have some programming chopped. You have hopefully conceptual understanding of how the world works, at least technologically. And there's again much more to come, but doing something like this is relatively now accessible. And the hope for a lot of you, especially those dubbed less comfortable, is that you'll be able to do come term's end for final projects things that you had no sense of your own ability to do at the start of the semester. So hopefully a number of you will amaze yourselves. And you'll find at the end of the semester that the goal is to exhibit precisely those accomplishments in the form of the CS50 fair for which we have several dozen videos from last year, hosted on Facebook. And it was actually a lot of fun. And we will host a similar event for you and your friends this year. Any questions, logistical or otherwise? 

[ Background noise ] Alright, so last note here. So dinner, this Wednesday, we had lunch last Friday, we'll do dinner this Wednesday hosted by Matherhouse and also in attendance will be Professional Rodica Nagpaul who teaches a number of course at SCAS including the course dubbed robo soccer. So last spring I had the pleasure of seeing some former CS50 students and teaching fellows compete in robo soccer, whereby they'd spent the entire semester using their computer science and engineering background. And to program these little robotic devices that were supposed to play soccer. And it was really neat, up in the Quad in Hillis Library, they had their little soccer field set up. They had cameras mounted in the ceiling and the cameras then looked down onto the field to figure out where the robots were in order to determine what algorithm should get applied to a particular robot at a given moment in time, given the locations of other robots, given the location of the ball, given the location of the goal. So Rodica will be joining us this Wednesday largely for a casual chat. She'll talk about her work and that kind of stuff. And then it's also an opportunity to chat with me and the teaching fellows and course assistants. So just head to CS50.net/RSVP if you are both hungry and interested in getting got know some of the team. Alright, so as much as excited as I tried to sound at the very start of this semester about four loops and vial loops and do while loops and all of this stuff, so we were kind of misleading. Like none of that stuff is really all that exciting. But we had to get you through it. But it's now after quiz 0 that we can finally dive into what are some more technical challenges. And also some more sophisticated solutions. So up until now, a lot of the problems you've been solving have evolved using you know an array or maybe starting last week thinking about things like link lists. But using those same basis, arrays and linked lists, we'll see this week can you do a lot more sophisticated approaches to similar problems. And we'll talk this week about compress. We'll talk this week about bit wise operations, manipulating bits at the very lowest levels, trees and things called tries and heaps. So data structure that you can continue a discussion of in a course like CS124, but generally that will empower you to solve actual interesting real world problems with a much richer tool kit under your belt. So first a practical tool. So it's been very annoying for you I'm sure to wage battle against seg fault and other memory related errors. And usually if you've triggered a seg fault you've done something per quiz 0 like step over the boundary of an array and touch memory that you don't own. Or you take a pointer and you try accidentally dereferencing it. Or you take null and worse yet you try dereferencing it. So in short, any time you guys have done something wrong, unintentionally with memory, have you possibly triggered a seg fault. Not always, but sometimes. It turns out there's help besides your own eyes and besides the teaching staff. So there are tools like this one, Val Grind which is a Linux or a base tool that you can now run much like GDB on your own binaries. Your own executable code and it will do its best to analyze your program to see did you screw up anywhere, at least with regard to memory. Might you trigger a seg fault? Did you allocate memory that you did not free? So do you have memory leaks? So what I did was I whipped up a little program here, you should have a print out of it today, hand outs were outside, a bit belatedly on the way in. If you didn't get them, there will be some there on during break. But it's a very small program and you can see it here. So I have a main routine that just calls a function called F and then it returns. But what does F do? Well I do an allocation of memory and then I do an assignment. So there's at least two bugs in this code. This is memory.c and whether you have it on paper or just in front of you, can someone identify one of the bugs or mistakes in this program? 

[ Background noise ] Say again? 

[ Background noise ] Ok so we don't free the malock, so the top of the function F I call mallock and I allocation 10 times 4 bytes, so 40 bytes assuming a 4 byte integer here. So I allocate 40 bytes dynamically and I retain that address, but then I never in fact call freeze. So that's arguably one bug in here. Now granted and to be clear, when this program quits, generally the operating system should take back the memory that was allocated for this program. So realize that even though with little baby programs like this, it might seem lame or unnecessary to bother freeing memory. Very rarely in life will your programs be as simple or as short as this. So this habit of freeing memory that you allocate is indeed important. So that's one bug there. So I haven't freed my memory. And there's another bug, maybe a little more subtle but even worse. 

>> Unknown: [Inaudible] the 10th element of array X. 

>> Unknown: Ok. 

>> Unknown: 0 through 9 element. 

>> Unknown: Ok, good. So and let me tweak your jargon. So I don't allocate but I assigned the 10th location or the 11th location of X even though there are only 10 locations there. So because it's 0 indexed, I can go from X bracket 0 through X bracket 9, but 10 is not good. Now not necessarily will this trigger a seg fault, which is why especially C and C plus, plus, some of these bugs are hard to chase down, because the word segmentation fault, the phrase segmentation fault actually hints at what's real, slightly more complicated structure underneath the hood which is that your computer's RAM is organized into different segments and it's really only once you cross segment boundaries that bad things happen. So realize that this might not trigger a seg fault but fortunately can you the human, or we the staff or programs like the one I'm about to demonstrate actually detect even mistakes like that. Because there are situations certainly in which bad things can happen like your program dumping core. So let me do this. Make memory. And that's going to execute the long GCC command. And I'm going to now run valgrand on memory and unfortunately its output is going to be kind of crazy, alright. A little overwhelming at first but let's just glance at the bottom on up, leak summary. So I definitely lost 40 bytes in one block. Alright, so that alone is a pretty clear warning. I have allocated memory that I did not free. It was even able to count that amount. Unfortunately it consists with what I predicted earlier when you pointed out the memory leak. So there's a problem there and then possibly loss, still reachable, suppressive. So this actually looks ok and you know what? Let me take its advice. I'm going to rerun the program with this switch as it's called, this command line argument often in Linux or UNIX or Mac OS when you want to tweak the behavior of a program, yes you can pass in command line arguments. But if they're sort of configuration options, those arguments will often begin with a single slash or a slash, sorry a single hyphen or two hyphens. This is simply convention. So let me do as it suggests and rerun it like this. Alright, so it looks the same at the bottom but I think I got a little more error, a little more reporting up top. So error summary, 14 errors, wow. I don't even have 14 lines of code. So something's really wrong. So let me scroll up and as is the case with GDB, don't focus your intention entirely on the bottom. Don't solve problems from the ground up. Go back to the very first message, because remember there's sometimes a cascading effect where a problem here can actually create the appearance of problems here even if there are none. So let's start at the top. Here's where I executed it. So mem check, a memory error detector, that's indeed what I'm running here. Some copyright information, which is not that useful. This is you know interesting but it feels a little cryptic, so I'm going to turn a blind eye for the moment until ah, here we go. Here is mention of my program. So this is shared library. This thing here. So if it's not your code or not a file you're familiar with, probably not a mistake. In almost certainly not your fault, but let's look here. Invalid write of size 4. Alright, so you can probably guess where this is coming from. So Valgrand is telling me in memory.C, line 2, I'm doing an invalid write of size 4. That is I'm probably trying to write 4 bytes or one integer to a location that it doesn't belong. And let's see, oh ok, so that is the result of having called F, the function F in line 29 of memory.c. So it's the output is similar in spirit to what GDB can do for you. And then let's see here. Alright so this is not good. Let's see, address 0 bytes after a block of size 40 allocated. So I'm calling mallock apparently in line 21 of memory.c, right inside of my F function. So it's not being as clear perhaps as to what the problem is. It's referring to an allocation of memory. But again per the summary down at the bottom, I have definitely lost 40 bytes because of my allocation in this line. So let's see if I can fix this. Let me go ahead and load memory.c again. Alright, so let's fix this to do this. So let's change this to 9, that's probably safe. And let me go ahead and recompile. Alright and now let me rerun Valgrand. Oops, not vim. Let's rerun the memory check. Alright, so good, leak summary definitely lost 40 bytes but if I look up here that mention of writing 4 bytes is no longer there. So that's good and let's fix this other bug. So let me go in here and after I've allocated X, how do I go about freeing the memory pointed at by X? 

[ Period of silence ] Anyone. Free X, very difficult, alright, so. Notice you free the pointer, don't dereference the pointer. So let me recompile make memory. Alright, nothing's bad yet so let me rerun the memory check and ok, interesting. Error summary, 13 errors from 6 contexts but and here's where sometimes you should not be misled by the program because it's really doing a very diligent, very anal check of all of the code related to your program. But recall that almost any time you write a C program, you are linking in other people's code, which isn't necessarily buggy but maybe is in fact giving tools like this a little bit of cause for concern. But if I now look through this, I actually don't see any errors that seem to be mine. Mallock free, I did one allocation, one free, 40 bytes allocated. So in fact, no leaks are possible. So this is good. Down here, all heap blocks are free, no leaks are possible and let's do the more succinct one where we don't actually do this command line argument. And in fact none of these seem to be mine. Ok, so you might enjoy or you might be disappointed to go back into say p set 4 which didn't use pointers all that much to run this program on your own code, especially if you did actually use something like Mallock and or free or the lack thereof. And certainly for problem set 6 which will be our last problem set based in C for which you implement that fastest spell checker possible, will you absolutely want to check whether or not you are risking memory errors. Because problem set 6 is the culmination of all these discussions we've been having about data structures and pointers. And it's dare say the most dangerous one with regard to memory, but also very easily solved especially with the help of tools like this. So more on that in the weeks to come. So this was as cute as I could be late at night with the slide. So hexadecimal is something we've talked about already and it's not all that complicated even though it might look a little cryptic and we talked about it in the context of Photoshop and you'll see it again when we do web stuff for colors and all of that. But you'll particularly see it this week because some of the tools you'll be using forensically or to get your program working for problem set 5 is, I forget how I started that sentence, one of the things you'll be doing this week is looking at hexadecimal values. Because of some of the tools you'll be using forensically to debug your code and develop your code. So you'll use a program for instance called xxd which simply dumps the contents of a file, like a JPEG or a BMP file or even your own binary and shows you the bits but it doesn't show you them as zeros and ones which is beyond useless for a typical human. It will instead show you things more succinctly in a more interesting way using hexadecimal. But we bring this up now because you'll start to realize that some details related to files on computers are very much operating system and or CPU specific. Some computers store data differently on disk than they do on say another computer altogether. So what do we mean by this? Well, there is this notion of endianness in the world of computing that refers to how numbesr are stored in memory, RAM, or perhaps on disk, depending on who is writing to disk. So what do I mean by this? Well, let me open up a silly little text editor here. And if I have the hexadecimal number like 1 and I store something like this, int X gets 1. Well in let's see decimal that's just the number 1. In binary it's the number 1, 2, 3, 4, 5, 6, 7, 8 and let me go ahead and copy this. It's going to be 1, 2, 3 and change this and now I'll shrink this down. So that's in binary the number and this is why humans tend not to use binary as a representation system. It's not all that useful. But in hexadecimal how would I write this same value? So that's in binary and incidentally, notionally some people will often add a suffix of lower case b just to indicate this is a binary number. How would I write this same thing in hex? 0X what? 

[ Period of silence ] 01 because each of these digits happens to represent how many bits? So 8, so each pair represents 8 because each individual digit represents 4 bits and why was this? Just to go back to a couple weeks ago when we started talking about hexadecimal and we said that each digit 0 through 9 and A through F represented 4 bits, either some pattern of 0s and 1s. So this was the decimal number 0 and 11111 is the hexadecimal number or the decimal number what? 

[ Period of silence ] 15 or in hexadecimal we would write this as an F. So here in the left hand column I'll write this all out. So in the left hand column here I have binary and then I have decimal, decimal and then here I have hexadecimal. Ok, so those are my three little contrived columns there. So why is this relevant? Well, this number here, just the number one, it turns out when it is stored in RAM on a typical computer including NICE.fas.harvard.edu it's actually not stored in this format but in the little NDN format. So there's this notion of big Ns and little Ns to numbers. So here is a number, granted in hexadecimal. The little n is the lowest ordered bits. So the tiniest numbers right? Because if I put a one at the other side, this actually makes this a pretty big number. But because the number here is at the right hand side, this is the little n, this is why this is such a small value. So the big N is over here. So this is very nice and neat because when we've been reading binary numbers from left to right, or rather from right to left we have the ones column, the twos column, the fours column and so forth, everything mathematically works out nicely. Unfortunately a typical computer would actually store this number, the number 1 as this. 

[ Period of silence ] It would store it in little NDN format where the lowest ordered byte actually comes first in memory. So in other words the thing is essentially reversed in memory. Well what do we mean by that? Well we have this nice little picture which if any of this is unclear it's actually a really nice article on Wikipedia for this topic, NDN ness. Take a look at the top left box there called register. So inside of a CPU are a whole bunch of registers. These are very tiny units of memory that ultimately is where all the action happens, all of the additional, multiplication, subtraction, all of the lowest level operations in the CPU happen in these things called registers. So in that top left box there, 0A, 0B, 0C, 0D, person who made the picture just needed a contrived number that's easy to remember. That is a number just as I might write it by hand on the blackboard or on my little notepad here. So it's from the big end all the way down. So what's the case in a computer that big NDN, what happens is if the left hand thing there represents RAM, where A represents the low of, location A plus 1 represents the next location, A plus 2 is the next location. In other words the bytes are getting incremented from top to bottom in this picture. Notice that the big end of the number 0A does in fact come first in memory. It comes at the lowest ordered address which is little A. Meanwhile the lowest ordered bits which is 0D come later in memory. So in other words at least if you think like I do about numbers in memory, the real number 0A, 0B, 0C, 0D is laid out in memory exactly as you the human would expect, from left to right or in this case from top to bottom. But in a little NDN architecture like nice.fas.harvard.edu and a lot of Intel hardware, what you have instead is kind of the opposite. So if we have that same number in the registers, the same number on a piece of paper, 0A,0B, 0C, 0D, notice that it gets laid out in memory essentially backwards. Where the big end of the number 0A comes last in memory. So this is simply unfortunate because I think it adds unnecessary confusion. But the world decided long ago that some CPUs would be little NDNs, some CPUs would be big NDN and really complicated annoying things happen when two computers need to talk to one another. So thankfully the world has decided on a network NDN format. So because we have this thing called the internet now, where data transfers from points A to B is commonplace and A and B absolutely might not be the same type of computer, thankfully the world has standardized what format is actually used across the wire, so that you don't have one computer talking to another in the wrong order. So what does this mean for you? Well when you take a look at BMP files, bitmap graphics that we've given you as part of problem set 5, you will find when you look at them with this program called XXD, it will show you the contents of bitmap files in memory. You're going to see that the numbers are not the way you would expect them if you wrote down those numbers in memory. So you'll be seeing and the whole spec walks you through this, a bitmap file can be represented with a whole bunch of RGB triples, red green, blue pixels, red, green, blue triples. You'll find unfortunately that these are laid out backwards when you actually look inside. So more on that in the spec itself. And let me go ahead and open this one file here. So vi of let's say NDN.c. Notice we have this little program here. So this is a quick teaser for what you'll be playing with probably partly in problem set 5. Let me go ahead and scroll to the top. I have one main function. This is NDN.c, now you got a little anal check here to make sure I provide a command line argument and if not I just return 1. I don't even yell at the user explicitly. Here recall is the notion for opening a file in read format. So the goal of this program is simply to run it, give it a BMP file, a graphic file like a Windows wallpaper, that's all a BMP file is. And then actually look inside of it and see what some of its fields look like in the order in which numbers are laid out. So let's see, if this thing, this file pointer is null, let's return immediately because that's not a legit file. And then there's some instructions like this, F seek. So you'll see this more in the spec and I'll defer to its explanations. But F seek, file seek is a function that simply starts at a file and then fast forwards, much like an old cassette player would, to a specific location in the file. So F seek seeks two bytes forward in the file, thanks to that 2. Down here I'm doing an F read and as you'll see in the distribution code, which again is well documented, notice that F read is file read. It's going to read into a variable called BF size a number from that file, thanks to the use of FP here. So in short what this program needs to do is given the name of a BMP file, it needs to open it, it then needs to fast forward to a specific location in that file and then it wants to read out a specific chunk of memory, specifically 32 bits which we're going to call BF size. Now why is this the case? Well I can whisk us over here to problem sets and I'm going to go down to just the standard edition of the forensics P set. I'm going to scroll down to a picture I'm looking for which is this one right here, which the specifics of which aren't terribly interesting right now. But what we're ultimately looking for in this file is a specific field. So long story short, files have different parts to them. This is what makes something a file format. A company like Microsoft or someone else declares that the first few bytes will mean this, the next few bytes will mean that, and so forth. This picture as the spec explains discusses exactly what's inside of a bitmap file and where. So the goal very simply of this code, because I know what that picture looks like, is to read out an integer inside of the file that's going to tell me how large it is. How large is this actual BMP? So what do I do next? After I've read in this nt, we report that the value of this nt, BF size is what's inside this variable. Then I do this, it turns out much like a cassette tape. There's a rewind function which rewinds the file to the very beginning. And then well I'm trying to, oh this is getting so much more complicated than I want it to be. Ok and then I do some complicated stuff which, damn. I don't really, let's spoil the ending. NDN. Ok, NDN of I have a file in here called doc.bmp. Ok. Let me skip some of the details because they're not going to be enlightening, they're just going to be boring at this point in time without P set 5 under your belt. So what I have just run here is a program that analyzes a tiny little bitmap file called doc.bmp. I made this with Photoshop. I opened up a one pixel by one pixel file and then I clicked my paintbrush tool and said make this a black dot. Then I save the file as doc.bmp. That's a bit of a white lie because making one little dot like that would not make such a big file. But BF size of this file is 58. This file in total is 58 bytes long. And simply what I did at the very end here, so that very complicated piece of code which I now regret teasing you with already is to show you that in memory, the size of this file is in fact laid out in little NDN format, even though this is an nt. And I would therefore expect it to be something like zeros then some zeros then some zeros then the number 58 because there's 4 bytes to an integer. In fact I do see from left to right that the little end of this number comes first. So let me wave my hand at some of the complexity I tripped over there just to say that when you dive into problem set 5, if not already, these are precisely the encoding issues that you are going to encounter for yourself. But let's take a step back and keep things a little less overwhelming at first and just look at these building blocks. So even though thus far we've been only doing operations like addition and subtraction and multiplication and division in the context of C, there's some other useful operators as well with which you can do much more interesting things even though they're incredibly low level. So henceforth, if you ever want to take two variables, say X and Y, and you want to somehow combine their bits in an interesting way you can do that using these so called bit wise operators. Unlike the arithmetic operators like plus and minus that sort of operate on the number in the aggregate, bit wise operators when applied to this variable and this variable essentially line them up and then apply the operation one bit at a time. And there's the notion of anding bits, together oring them together, exclusively oring them together, complimenting them and also shifting left and right and by this I mean the following. So let me go ahead and just list out let's say a number X and call it 00000. For simplicity I'm not going to use integers because I'd be writing 32 digits all of the time. But let's say this Y is 00001 and suppose the operation I want to perform is X and Y. So X and Y would be represented as X and Y and this equals the result of applying the and operation to each pair of digits that line up together. So let's start from the left to right. 0 and 0. So just logically that's false and false. So what should the answer be if you're anding them together much like we did with Boolean operators weeks ago. So it should be false. So 0 and 0 be clear, 0 and 0 is in fact 0. So that's the first of four digits. The next pair, this guy here and this guy here are also zeros so 0 and 0 gives me 0. 0 and 0 gives me 0 and 0 and 1, false and true gives me 0. Alright so something that's false and true, if you and those two together, if you think of that as an ampersand ampersand operation whether it was in Scratch or it was in C. False and true gives you false as well. Meanwhile if we do this, this is the or operator. So x or y means either one bit or the other must be one. So what about 0 or 0? No. 0 or 0? No. 0 or 0? No. 0 or 1? Yes. And now this one's a little more interesting. X, X or Y, so slightly confusing name but exclusive or represented in the language C using the little carrot operator. This means that one of the bits and only one of the bits can be 1 for the result to be 1. So you need exclusivity, either one and zero or zero and one. But not 0 0 or 1 1. You need exclusivity. So 0 0, 0 X or 0, not exclusive. 0 X or 0, not exclusive. 0 X or 0, not exclusive. 0 X or 1, yes, so now I have this answer here. Now some of them are pretty darn trivial. So Tilda X which here represents the compliment. This just means to flip the bits, 0 becomes 1 and 1 becomes 0, so Tilda X is 1111, that's pretty simple. And then we had a couple of others. Let's say X left shift, so 2 angle brackets 1, let me go ahead and shrink the font a little bit. Actually let's do it to Y. So Y left shift, left shift is going to equal what? So this means take the bits of Y and shift them to the left by one place. So what does the output become? 

[ Period of silence ] 001 and then what do you want to put at the left hand side? So 0. So the shift operators indeed pushes all of the bits to the left, if you're using the left shift operator or pushes all of the bits to the right if you're using the right shift operator. And it adds any empty spaces typically with zeros. Though FYI, there's some corner cases when you're using signed integers as to how you handle negative numbers in particular. But we'll focus just on simple positive numbers for now. This is kind of a funny thing and actually let's do this. Y right shift 1 is going to equal all zeros in this case because you're pushing the bit off the end of it. So this one's kind of interesting. If you shift the bits of a variable by 1 position like this, what's the equivalent mathematically? 

[ Period of silence ] Yeah, so this is actually a really neat low level way of multiplying or multiplying any number by 2. So if I had the number Y equals 1 up here, shift the bits to the left, you told me that we get this. This is the value. Let's see this is columns, ones columns, two. So that's the value 2. So one becomes 2, if I left shift again by 2 places this number becomes this which is the value in decimal known as 4. Do it again and we get 8, do it again if we have enough bits, 16, 32. So a really neat way of multiplying a value by 2 is simply to shift its bits to the left. So this is one of the underlying representations. Now who cares is an interesting question now, right? So this is all fine and good but I promised that we would actually be solving real problems and not devolving back to for loops and while loops and all of this. So it turns out there's some very interesting applications of these very simple ideas. So these, how many of you just by a show of hands has ever lost data because your hard drive crashed or got corrupted or something bad happened? So a lot of you. Now how many of you didn't actually lose data because you were using a raid 1 or raid 5 set up in your machine? Alright, so not many, maybe just one or two geeks who ever awkwardly raised their hands that second time. So what does this mean? Well frankly if you have a desktop computer these days, there's no excuse for not having a pair of hard drives, two hard drives that are in a so called raid 1 configuration. So raid is redundant array of independent disks. It's just a really fancy way of saying you don't have one hard drive, you have two hard drives. And what's really neat about RAID 1 specifically and you can do this with Mac OS, you can do this with Windows these days, some computer companies like Dell offer this feature now when you use that little web based configurator when buying a computer. RAID 1 takes one disk of size you know let's say a terabyte or 500 gigabytes, then you get another identical hard drive and RAID 1 means that your computer treats them as identical. So any data that gets written here simultaneously gets written here. The upside of this is that if you are very unfortunate to suffer a hard drive failure, this guy just breaks, all of your data is literally still on the other drive. So now you're operating in kind of a dangerous mode. Your computer is smart enough, if it supports this technology called RAID to keep on plugging away using just the one hard drive. But obviously if bad things happen to this hard drive too, then your data is definitely lost. But it decreases the probability that you'll lose data because now you would have to have this drive and this drive fail simultaneously for you to actually lose data. And what's really neat about RAID is that if this drive fails and therefore is useless and this one keeps on plugging away, you can go out, buy an identically sized or larger hard drive, plug it into this slot, throw the other hard drive away and then the computer will automatically synchronize this data over to the new drive and now you're back in a stable RAID 1 configuration. So this is not related at all to bit wise operators. This is just very useful for consumers. But that only scales so well. There's other technologies like RAID 5 which actually lets you have multiple hard drives inside a computer or more commonly inside of a server that allows you to treat multiple hard drives as though they were just one. So if I had 3 1 terabyte drives, RAID 5 would actually let my computer think it had one 2 terabyte drives. So if I had one terabyte, 1 terabyte and 1 terabyte hard drive and I'm using a RAID 5 configuration, I get a total of 2 terabytes of space because one of those terabytes, one hard drive is actually used to store a check sum, which is a term that has came up very early on in the course when talking about ISBNs and credit cards for problem set 1. So if you're willing to sacrifice one hard drive which frankly is pretty reasonable these days given the cost, you can actually not only get this ability to lose a hard drive and keep on plugging away, you can also expand your storage to give the illusion that multiple hard drives are just one really big hard drive. Now how does this work? Well I'm really going to simplify things. So I don't want to write out one trillion bits here or one trillion bytes. So I'm going to instead say that suppose this hard drive here has just 4 bits in it. So I've only stored a tiny little file. I've stored the number 15 and this hard drive simply stores this value, another 4 bit value. What's really neat about RAID 5 is that essentially what it does it is uses the third hard drive simply to store the XOR of the first two hard drives. So using this very simple primitive can you do the following. 1XOR1 is going to give me if I line these left most bits up, 1XOR1 is what? 0, 1XOR1 is 0, 1XOR0, 1 and then 1. So this third hard drive is now essentially my check sum. So what does this mean exactly? Well let's suppose some bad things happened like this guy gets deleted or breaks. So now I've lost my data, right. This is really bad because some of my MP3s are over here, some of them just so happen to be on this hard drive. I seem to have lost it and frankly this is not a back up right? This third hard drive was clearly not the same as the one I lost. It happens coincidently to be the opposite. But what does this mean? Well thanks to RAID 5, XOR can also be applied in the, a reverse direction conceptually. If I now and let me go ahead and do something like can I change colors? Let's say that this guy broke entirely. So red is bad. So what can I do? Well it turns out if I XOR this guy with this guy, what do I get back out? So let's call this result. And now let's see. So look just at the black numbers. 1XOR0 gives me 1, 1XOR0 gives me 1, 1XOR1 gives me 0, 1XOR1 gives me 0. Wala, thanks god for that third hard drive that really wasn't doing anything in terms of space. It wasn't giving me another terabyte. It was just keeping not a backup, but the result of XORing the first two drives together. Can my computer if designed to support RAID recover the data that was lost in red? Let's suppose it was the opposite situation. So the take away to be clear is that this result equals the lost hard drive. So what is instead it's not the hard drive number 2 that is lost, but instead let's make him ok, back to black there. And now let's say it's this guy that actually disappears. So now he is the dead hard drive. Thankfully I've kept around my third hard drive, so let's see what happens here. 1XOR0 gives me 1, same thing gives me 1, same thing gives me 1, 1. Wala, I've recovered my data as well. And what's really neat is RAID 5 doesn't just support 3 hard drives, it supports 4 hard drives, 5 hard drives. You simply use the nth disk as this XOR disk, the check sum disk and can you recover all of your data in this very simple bit wise way. I'm going to take a 5 minute break. 

[ Background noise ] Alright we are back, another application of XOR is actually this sort of mind blowing example where you can actually swap two values A and B without using a temporary variable. So alright, we've used this exercise multiple times to demonstrate how not to swap values, how to swap values, how to swap student's houses, so we kind of belabored this notion of swapping, but in every case, quiz 0 and before in lecture did we actually use some temporary storage because just conceptually it's kind of hard to imagine putting this variable here and this variable here without actually clobbering this one in between those two steps. But it turns out using XOR you can do this. I don't think it's all that enlightening to belabor the details, but this is a very quick and dirt main routine that notice declares two variables, X and Y. And this is called Swap2.c for those following along on paper. X is 1, Y is 2. I print out the values of those variables then I call this function swap, passing by reference or pointer, not passing by value because value is very bad. It's not going to work here. But then this program does actually work correctly. Let me go ahead and make swap2 and let me go ahead and run swap2 a the command line. And indeed it works. The interesting question is how does it work? Well notice we have these three lines of code, none of which actually employs a local variable. So I'll leave this I think more as an at home thought exercise, but don't be distracted by the use of pointers. The fact that we're using pointers is irrelevant to the trick itself. The pointers just allow us to actually do swaps at all. So we're using pointers, allows us to actually exchange the original values. So don't think that the magic lies in the stars, but the magic really lies in this carrot, in this XOR operator. So simply by XORing two values together once, and then again and then again while updating the values of A, B and A accordingly in each of those steps, you can literally like take 2 values and I'll do it dramatically with fingers this time, move them from one to the other without losing any data. And it's a neat trick and for those curious you can follow along at home with the slides for today where I belabor the point, line by line by line showing you in comment exactly what's going on underneath the hood, using very simple values of 1 and 4. But it's really neat. And if you're ever asked in some you know silly interview question years from now how can you swap two values without using a temporary variable? This is the answer Microsoft and the like are looking for, using bit wise operators. So it's neat if nothing else. But let's take a look at something that is more enlightening and perhaps more useful longer term. And that is to actually use a notion of a mask. So this is a common idea. And actually let's use these bit wise operations at a lower level, but let's see what we can do. So I'm going to do this from scratch even though you have a copy in front of you for reference, least I screw up on the fly. But I'm just going to go ahead and start, the goal here is to ask the user for an integer and then I want to convert that integer which the user is going to type in decimal. I want it to display as binary. Right I'm really curious to see what binary numbers look like. I want to see what the mapping is like. So if I run this program and I type in the number 1 in decimal, I want to see 31 zeros get printed and then 11 or if I type in 4 billion something or other, I want to see a whole lot of one's be printed across the screen. Alright, so how can we do this? And we'll see what the take away is in a moment. So let me go ahead and include my own library. Let me go ahead and also include let's say standardIO.h. Here's my main into main into arc.c star arg v bracket. Ok, coming along. So now what do I want to do? Well let's go ahead and ask the user, ask user for nt. Alright, so let's see, I'm going to need to store this somewhere and I'm going to need to do the following while the user doesn't cooperate, so I know this construct is generally useful, I'll fill in the blank in a moment. What do I want to do? Well let's do n get nt. Alright and now how do I check that this is actually, actually let's tell the user what to do. So print def give me a non negative nt. Alright, so now while and what do I want to put here to ensure that they're giving me a value I want? 

[ Period of silence ] While n is? Less than 0. Alright so this will just pester the user again and again, give me a non negative nt, non negative nt, non negative nt until finally they give me 0 or higher, then this loop will break. And so now I can do something interesting with it. So now I want to print the number in binary. Alright, well this is where things get a little more interesting. Let's at least do a sanity check here. Let's print out the number in integer format, n. And then we'll just return. So let me do, make sure I didn't screw up anywhere else. Ok, so far so good, binary, give me a non negative nt, 1, ok seems to work. I'll give it 15. Ok, seems to work, alright. So let's move on now. Alright print number in binary. So how do I print a number in binary? So there's no, unlike JAVA there's not just a function that says print this in binary. There's most anything in languages like that. So C we have to kind of get our hands dirty or go lower level, but let's see I know how a number is represented underneath the hood. It's just an nt, let's see it's 32 bits. So I essentially just need a loop that's going to iterate 32 times conceptually from the left end of my number all the way to my right end, because print def is only going to print from left to right. I can't go backwards as we usually do on the screen. So I need a loop that's going to execute 32 times. So let me start off instinctively like this. Nt is 0, I is less than 32, I plus plus. So that's the right idea. I can maybe clean this up a little bit. In fact, I kind of want to do it from the left hand side, but we'll come back to that. I'll clean up that loop, but I at least have the basic building block in place. Now what do I want to do? Well I essentially want to ask this question on every iteration. Is the current bit a 1? If so print a 1. Is the current bit a 0? Print a 0. Because we're now talking about individual bits. But what I'm going to print to the screen is actually quote unquote 0 or quote unquote 1. So I need to essentially convert these tiny little bits to an actually ASCII character so the user can understand. So you know what I'm going to do? I'm actually going to scroll back because I want to do this from the left hand side first of the number, not the right hand side. So really I'm going to do this. And I'm going to be a little more dynamic. So nt I gets size of nt, oops, size of nt. Alright, so that's going to give me a 4 bytes but I want 8 bytes. Sorry, 8 bits per byte so size of nt times 8 gives me what number? Quick sanity check. 32 hopefully. On the 32 bit machine, this is going to give me the value of 32 because it's 4 times 8. But I don't want to go to the 32 bit because really if the bits are 0 indexed it's 31. So I'm going to be a little defensive and I'm going to start at 31. So the left most bit is going to be bit 31 because the right most bit is going to be bit number 0. So I want to do this so long as I is greater than or equal to 0. And then I want to decrement I on each iteration. So again the goal is if I have a really long 32 bit value, I conceptually just need I to point at the bit 31 then decrement to 30, 29, 28, dot, dot, dot. To bit 0 because what I want to do on each iteration to be clear is print out in ASCII form that particular bit, 0 or 1. So the question then becomes if I just have a chunk of 4 bits called an nt, how do I actually get at individual integers? Thus far we've not actually given you the ability. And you've probably not discovered the ability to actually manipulate individual bits. The smallest unit of data that you've probably been able to manipulate thus far is what? How many bytes or how many bits? 

[ Period of silence ] Like what's the smallest piece of data you've actually changed or read in any program you've written thus far? 

[ Background noise ] A char right? 8 bits or 1 byte is a char, but we want to go deeper than that. And there's no data type called bit, so we actually have to accept the fact that we have some limitations and figure out how inside of a char or inside of an nt we can nonetheless get at something we care about. And this common trick, this is just a piece of jargon, but it's an idea that will recur in programs perhaps throughout your life if you continue playing with stuff like this. We can define what's called a bit mask. So a mask is just a value that usually mostly zeros, but it has a 1 any location that you happen to care about at the current moment in time. And you can actually flip the definition and say it's all zeros, it's all ones except for occasional zeros. But I'm going to think of this mask, kind of in Photoshop form, in overlay where I want a whole bunch of zeros but I want a 1 at the location I currently care about. So in short, on every iteration now my goal I've decided is to give, is to create for myself a 32 bit value, all zeros but I want to turn on the bit I care about. Bit 31 followed by bit 30, followed by bit 30, 29, all the way down. And then on each iteration do I want to change all the 1s I've created back to 0s. So I want a big sequence of 0s and then just a 1 that moves from left to right on each iteration. So how do I achieve this? Well using these primitives from today. If I want a mask, if I want a 1 at the ith location, it turns out I can just do this. So I'm going to declare a mask to be 32 bits. That's why I'm using an nt. I need a 1 at a certain location. Well what location do I want it at at first? I want it at location 31. So using left shift, what this means is when I simply do 1 left shift I that's really like saying on the first iteration 1 left shift 31, which means ok, take a 1 and then shift it to the left 31 places, which essentially means, 1, 2, 3, 4, 5, 6, 7, 8, let's just make this look like an actual nt. And I'll shrink it so it actually fits on the screen. And that gives us this, get rid of our stupid color wheel. So if I have a 1 as I do at this point in time and then I shift it 31 places, that means my 1 goes 1, 2, 3, 4, dot, dot, dot. It eventually ends up over here. So my mask is now this integer of all zeros but a 1 bit at the location I care about. And now using another bit wise operator can I actually check a specific bit in the number that I got from the user. So let's take a look. Let me go ahead now and do if n, the number the user gave me, ended with bitwise ended with my mask is true, if that gives me back a positive value and rather a non 0 value, what do I want to print? In other words if the user's number ended with my current mask gives me a non 0 value, what does that mean? So I want to print a 1 because it means a 1 is there, else and I'll rewind in a second, I want to print a 0. Now why does this work? Well let's take a look at this. The mask I've created is in fact this. So now the user, the very, let's suppose the user types in 15. Let me use the same number of bits. So the user is going to type in 15 as I did in my second demo there, 1, 2, 3, 4. So this is the number 15 that the user has typed in. Sure more sophisticated tools exist than text edit for lectures, but that's ok. And this is my mask. And got to work on my font size. Alright, so this is my mask and I'll space things accordingly. Alright, this is a nice state of the world. N is that value 15 that the user typed in. My mask initially is a 1 all the way over at the left hand location. And then I do this and operator so what does that actually give me at this location? 0 and 1 is 0 and then how about everything else? If you just fast forward to the end. It's all zeros. So this is interesting because if I take the user's number N and and it with my current mask and my mask current has just a single bit set at the 31 location. And the answer comes back as zero. Well what's the take away? That that one location all the way on the left was a 0. Because if it were a one, what number would I have gotten back? If the user had typed in something like 4 billion, something atrocious and then I had anded those two values together, what then would I get as one and one? So I'd actually get a value like god a 1 here and then yes, a whole lot of zeros. And I don't know what this number is off hand. This is like 4 billion, 2 billion something or other right now. But what's the take away? 2 billion is non 0 which is why my check here if N anded with the mask gives me anything other than 0, if it gives me any 1 bits anywhere, ie a non 0 number, then I found a one at that location. Otherwise it finds only a zero and so I'll print that. So that's all it actually takes. I now have a loop that we've already concluded is going to iterate 32 times. I'm creating on each iteration a temporary mask, a temporary variable that just is all zeros except a 1 bit at interesting locations from left to right, 1 bit at a time. And the goal of that is to leverage the reality that if you and a number with a mask, the only bits that are going to be allowed to pass through this filter of sorts, through this mask is going to be a one bit in the original value. And that's kind of where the idea, the word gets its name. So if I have a mask with a 1 here, the only bits that will be allowed to pass through to be clear are where there are ones in the mask. So this number passes through. These numbers all get blocked by the and operation but that passing through of the left most one is enough o make me realize, oh this expression N and mask is true because remember true does not mean 1. True means non 0, false means 0, true means non 0, more generally. So let's actually now compile this and if I've made no mistakes, fingers crossed, ok mistakes, oh I called it print instead of print def. That's easy to fix. Alright. Let's go ahead and recompile. Better, so let me run binary in my current working directory, give me a non negative nt, let's give it 1. Ok, I need kind of a print def there, so let me go back in here and do a little print def of backslash N. And now let's recompile this. Just for aesthetic reasons. Ok. Now I'll give it 1. Ok so that's kind of cool. Underwhelming, let's give it something more interesting, 15. Ok, so now again all I've done is iterate 32 times left to right over that underlying 15 to get this result and let's do something like 2 billion. Enter, that's apparently what 2 billion in decimal terms actually equals in binary. So it's kind of neat. And this idea, this is a problem you will not often solve simply printing out numbers in binary. But this idea of selecting individual bits is actually a really powerful one. In some of your problems, that's like problem set 4, how many of you guys used an array, maybe a 1D or a 2 dimensional array of boles simply to remember which of the numbers had come with the bore. Anyone take this approach? Yeah, so from just chatter on the bulletin board, this seemed to be a not uncommon approach. Recall that p set 4 required that you remembered which numbers came with the board and which ones did not. So that you could actually prevent the user from changing some of them. Well, you guys, it sounds used a 2, some of you used a 2 dimensional array storing a whole bunch of Booleans so what is that? 81 Booleans to keep track of true or false. That was really a waste of space, right? You used 8 bits probably or you used 8 bits because a bole, if you ever really looked closely is represented with what data type? I think it's actually represented with what's called an unsigned char, but either way. The smallest data type you said we have in C is a char. Which means a bole underneath the hood is actually 8 bits. You were using 7 bits more than you needed to for every one of those true false values. So a very common approach to these low level bitwise operations is actually to compress your program into using only as much memory as it needs to. Because right intuitively a much clever, more clever approach would have been yes to have the notion of a 2D array, but just use a single bit for each of those locations. And you could have used one eighth the memory to remember something like which numbers came and did not come with the board. How do you actually implement this? Well you could actually now implement just a chunk of memory, if you think back to that problem set. You could actually implement yourself by manipulating individual bits. And so what you'll find in this world of bitwise operations, you can implement a function called set. And you can implement a function called get that simply takes a chunk of memory and flips individual bits on and off and get simply checks them. So we've looked at setting bits, sorry. We've used getting bits using the and operation, which of our several bitwise operations might be appropriate for actually setting a value? ANDOR, XOR, or compliment? 

[ Background noise ] How might you turn on a bit? 

[ Background noise ] Yeah, so or is actually the case. And how do you do that? Well if you wanted to OR two numbers together, what you could do is something like this. Let me get rid of my little scratch pad. If I had nt X gets let's say something like 0, and this actually equals 00000. And then I have, suppose I want to set the one bit, suppose I want to set this bit. What operation can I perform? Well I can actually do X GETS X OR 1 and that would actually set the left most bit. Why? Because if you line these two numbers up, 00000 and 00001, and you OR them together, well this guy here is obviously 0, 0 or 0, 0 or 0, 0 or 0, 0 or 1. So in fact the or operator has the effect of turning bits on, so long as you use something like assignment to keep that value around. So any questions on bitwise manipulation? Alright, so let's lay the foundation here for these higher level data structures that I promised. So we've used arrays, we talked about link lists, you'll use link lists, many of you for problem set 6. You'll find that you have some design discretion for that problem set. But suppose the problem at hand is to actually store data like words in a dictionary in some structure that facilitates answering questions like is this word here. A data structure that facilitates maybe even sorting this information faster than something like a link list could. So there's a problem with a linked list. If we implement, we're going to have you like for problem set 6, 140000 English words. And we're going to hand you a really big text file and you're going to be challenged with reading that file into memory using things like F read and other little functions we've seen or will see. And you've got to somehow represent all of those strings in memory because then we're going to make your code spell check actual files, really big files like the screenplay from Austin Powers and the King James the fifth bible and really large texts that will have some spelling mistakes or at least unrecognized words. And you're going to have to do this quickly. Unfortunately if you just load all 140000 words into an array or maybe being a little fancier a linked list, what's the running time of your lookup function going to be? What's the running time of your spell checking function going to be? I mean it's linear. Every time you might have to on average you're going to look at half of the word, so 70000 words every damn time we ask a question is this word spelled correctly. So can we do better? Well it turned out we can with any number of data structures, one of which is this thing called the hash table. And it turns out you'll see this for real in PHP and JAVA script, sort of the data structure that's known as the universal data structure, the one that some geeky computer scientist once joked that if you're on a desert island what data structure would you want to bring with you? Well you'd bring this thing called a hash table because you can do most anything with it. Whether sloppily or otherwise, but a hash table is simply this. It's essentially a big array and before you put something into this array you ask yourself the question at what location does this new element belong. In other words given a word from a dictionary, you ask yourself here's a big array or here's a bunch of buckets. Which bucket should I put this word into? Alright, so there's a problem though with this approach in general. If you're treating a hash table as just a big array or a whole bunch of buckets and suppose I take in a word like apple. And you decide somewhat arbitrarily that all of the apple, all the words starting with A should probably go where intuitively? At the 0 location right, just because right? A words will start at the beginning. And then I get banana, where should I put that into these buckets? Put it at location table bracket 1 and then zoo would go at the very bottom of the table. But there's a problem. What if then another word from the dictionary is aardvark. Well where does that go? If you've already got apple inside this table? 

[ Period of silence ] Well those are the only three words so far. Apple, banana and zoo. And now I insert aardvark. Unfortunately bracket 0, bracket 1 and bracket 25 are already taken using our very simple heuristic, so what's, we need to get the word in there. We need aardvark to be in the dictionary. Where can we put it? 

[ Period of silence ] Now you only have, alright, so there are what 23 remaining answers. You have a 1 in 23 chance of getting this right. Where do you put aardvark? 

[ Background noise ] So two location, sure. Right? In short, who cares, right? Put it somewhere and so there's this general approach called linear probing which means try to put it where you want to. So in this case I'm going to try to put it at the zero location because that's where the A word should go. Unfortunately I have what's called a collision which means I already have something in that location. So probe the buckets, probe the hash table, just step by step by step until you find an empty slot, then plot aardvark in there. So we probe bracket 0 and we find apple there. We probe the next location and we find banana, ah ha! There's no C words yet, let's steal the C words place and put aardvark at table bracket 2. And you continue in this way. So now you are going to bump up against a real world limit. How big can this dictionary obviously be? So 26 words and that's it. So we're kind of screwed with our 140000 word dictionary already. So hopefully there's a fundamentally better approach but there's a problem fundamentally with linear probing itself which is that you're really hurting your look up time. The amazing thing about hash tables is that in the best case lookup times for words, lookup times for elements are how fast? In other words if I ask you is apple a word, how many steps, how many units of time do you need to answer that question with this data structure? 

[ Background noise ] One, right? Because I hand you apple, you check the first letter, oh A, let me check my 0th location. Oh, there's apple, constant time, right? One operation of time is required. What about banana, is banana a word? Check the B, oh brackets 1, yes, banana is a word. But now you've got this problem. What if I hand you aardvark? Is aardvark a word? Well, you check its first letter and say damn, apple is there, but maybe I've got it elsewhere. Let me look. And that process of let me look now devolves into how many steps in the worse case? N, right? So we have this really interesting trade off. The motivation for hash tables if really cleverly designed is to achieve constant time lookups for pieces of information. And we have yet to discover this recently because we did have this with arrays. But even with arrays our search, our search time eventually became log N when we couldn't, when we had an arbitrary number of elements in here. So this kind of begs the question how big, how bad is this problem, right? One approach to this problem of having collisions between apple and aardvark is fine, yes this was just stupid using 26 buckets. Let's use 1000 buckets. And then with use a more sophisticated hash function then just checking the first letter, right? Slightly more interesting then checking the first letter might be why don't we check the first two letters? Well that helps us with aardvark and apple because we have aa and ap. So those would end up in different buckets. But I'm sure we could find another word that starts with AA or another word that starts with AP that's going to create another collision. So the problem is that even though this is sort of the holy grail of data structures, constant time operations because we can blow out of the water every other algorithm we've implemented thus far. We have this problem of collisions and we'll see that this problem will become in a room full of N CS50 students, what's the probability that 2 of you have the same birthday. Turns out that happens with strikingly high probability, which means in the analog of the world of apples and aardvarks, it's going to happen really frequently here too. And so we'll need a much more sophisticated approach than this, but for that we wait till Wednesday. See you then. 

[ Music ] 

==== Transcribed by Automatic Sync Technologies ====