[ Silence ] >> Alright. Welcome back, this is CS50, the start of Week 3. So I got an email on my Gmail inbox today that looked a little something like this. It was from Harvard University, Harvard University welcoming me and it's to say that Harvard University is running an update on their servers and requires all clients to confirm their web mail access dot dot, confirm my web mail access, regards. Thank you for using Harvard University. So being an obedient user, I went ahead and clicked that link and I found myself oh, add my dot Harvard at the web mail log in but it wasn't quite the web mail log in. If you look up top there you'll actually see that I found myself of all places at Max Films Online which actually sounds like I should've ended up somewhere else but in fact it is Harvard's new web mail system it would seem and so I proceeded to log in with my username and my password and I clicked check mail and then what happens? >> You have your mail. >> Alright, so now some Max has my username and password somewhere out on the internet. Now what can Max do with that? Well it can certainly check my FAS mail at least, maybe there's nothing even in there because I forwarded it elsewhere. He can certainly send mail now as though he were me but the thing is you can do that any way even without having access to someone's email account. You can for Gmails terribly easily. And so what does that mean? Well, now he actually has, let's say, a shell account. So you guys all have usernames and passwords on cloud.cs50.net but for problem set zero you also sign up for a so-called FAS account which really is an email address of the form something fast on Harvard.edu but it turns out FAS itself has a Linux infrastructure not unlike ours called nice.FAS.Harvard.edu, the new instructional computing environment, new as in came out about 10 years ago now but it's another system like the cloud that you can SSH to and you can right code for other courses and you can send mail and such from it but the scary thing or at least the compelling thing for Max is that now he has access to a server, a server that's not based in his own home. It's a server based maybe somewhere across the ocean and now he can do pretty much whatever he wants with your account on that server including sending spam, including setting up a file server and sharing files illegally unbeknownst to you. So in short, he now has access to some stored space and some username that you would otherwise be responsible for. So what's the takeaway here? Well, certainly if you get an email from regards Harvard University, maybe not--don't necessarily click on that link, but what this is really a testament to and it will foreshadow what we'll do later this semester, it is so terribly easy to do what Max did, buying a domain name certainly is pretty mindless. You can go to any number of websites spend 5, 10, 15 dollars and now you own maxfilmsonline.com, you'll need to host it somewhere and we'll talk about this in detail into the course. If you wanna start your next startup company or whatnot, it's actually very easy to get started if it's at least an internet startup on the web. So we'll talk a bit about that so this part is easy and then it turns out if you go to the real webmail.FAS.Harvard.edu, well by nature of the World Wide Web and by nature of the language, HTML, in which webpages are written, anyone on the internet can see the so-called source code of webmails, of webpage and so this stuff might look like Greek to some of you, some of you might have programmed in this stuff before and actually I shouldn't say program, HTML is not a programming language as we'll see. It's a markup language, more about aesthetics than it is about logic. But this kind of stuff, frankly, can be very easily copied and then pasted into Max's own homepage and if we go back to maxfilmsonline.com, sure enough, there's the exact same source code. He just pasted it in and now he's probably changed one line of HTML so that when you actually submit your username and password, it doesn't go to the server called webmail.FAS.Harvard.edu, it goes to maxfilmsonline.com. So this is terribly common. This is what's generally known as a phishing attack, P-H-I-S-H-I-N-G, which is to say you try to lure hooks on unsuspecting user into doing something that they might otherwise not if they actually understood what was going on and it's a more general notion of social engineering where you dupe people into doing your bidding because they don't really understand what's going on. So we'll talk a little about this sort of stuff toward the tail end in the context of web stuff but it certainly recurs and so refer back if you find yourself at semester's end interested in learning more about this stuff at the unofficial guide to computer science at Harvard that we have. There's a bunch of summaries of courses, among them Computer Science 105: Privacy and Security, which is more of a seminar course in the spring in which you discuss and explore and understand these kinds of issues better. So speaking of security, we left off there last time looking at this thing called secret key cryptography. Alright. There's many different ways of describing this. You might hear it called symmetric key cryptography, you might just hear it called encryption in general, but this picture kind of paints the right story for us. You have some plain text on the left, some text, some message that I've typed in English or whatever language I know, you then encrypt it, you scramble it, but to do that, you need a secret, you need a big number, you need a password, you need a passphrase, you need some secret that only you and hopefully the recipient knows and the output of this inscription process is what we generally call ciphertext and then what's nice about secret key crypto or symmetric key crypto is that you can use the exact same key to decrypt this message. You essentially just reverse the mathematics. Now what does that mean? Well, it depends. You're exploring this week, as we'll discuss in a bit, Caesar cipher, Vigenere cipher, and some other options in the hacker edition but it boils down to generally some basic math. So what's nice about this system? Well, it's terribly easy. You, Alice, and Bob agree on some key and now they can exchange secret messages back and forth. But what's the problem with this approach or with this general approach to securing your information? You can--go ahead. [ Inaudible Remark ] >> Yeah, it's very vulnerable, right. If that key gets compromised, not only are all future messages vulnerable to being decrypted by parties that shouldn't have access to it because there's no changing variable in this formula right now, they can also go back if they had a record of all of your messages that you've sent in years past. Well, they can go ahead and decrypt all of those as well. So this is a recurring theme in security that it's applying to claim that your data is secure, it's to secure it with something like a key but you have to understand what the implications actually are. So this also did not address one very common problem. These days, you go on facebook.com and log in with your username and password, you go on amazon.com and websites like this most likely and you're probably at least familiar with the notion of SSL or URLs that start with HTTPS where the S stands for secure, something along those lines and so that just means your information is encrypted between you and the web server. But as we teased you with at the end of last week, this is kind of a catch 22 in that if you don't know anyone at Amazon or don't know anyone at Facebook, how could you possibly have agreed upon a shared secret, a key, a password, a big number to use in this exchange and so thankfully, for that purpose, there exists something called public key cryptography which we won't focus so much on in this course. There are security courses at Harvard in which you can explore this but the kinds of security we use with automated teller machines these days, with online banking, with any form of website that uses HTTPS, URLs realize there is a solution to that chicken and the egg problem of getting the key to someone but getting it to them securely. But the focus for P set 2 is on some symmetric key or some secret key ciphers. This recall stood for be sure to drink your Ovaltine which is just a reference to an older movie but it was a specific incarnation of an algorithm called a Caesar cipher or shift cipher, shift in that you encrypt information just by rotating each letter by 1 place, by 2 places, by 25 places and after that it's pretty useless because then you get stuck in a loop because there's only 26 letters in the alphabet, in this case, the key, does anyone recall, was what number? >> 13? >> So it's 13 and you can infer that just by knowing well, it's be sure to drink your Ovaltine so how do I get from O to B? I rotate the letters 13 places, I wrap around when I get to Z back to A and sure enough that will give me the ciphertext and vice versa. So it turns out too, historically, this is an example of something called rot 13, R-O-T 13, for rotate 13 and you'll see there's a bit of geek humor in Pset 2 alluding to a more secure version of rot 13 but for now, the takeaway is that this is an example, it's simple of this idea of a secret key cipher. So what specifically are you doing in P set 2? Well, first, you're implementing this notion of a Caesar cipher and you're gonna write a program that takes these things--takes one of these things called the command line argument, K, that is a word or number or something that you type on the command line after your program's name and hit Enter instead of using something like get string to get that input. And then if I type in 13 at the prompt, you're then going to ask the user with get string to give you an actual sentence, to give you some plain text and what you're gonna have to then in this code is iterate, that is walk from left to right across the string that the user typed in, the plain text, and add essentially that value of K to it. Maybe it's 13, maybe it's 1, it depends on what number the user inputted and you're gonna have to do this for character, for character, for character in the user's input but you're probably gonna need some conditions in there because if you hit a period, at least according to our definition of the Caesar cipher, you're not gonna rotate punctation, you're only gonna rotate alphabetical letters so A will become maybe B, B will become maybe C. It depends on the value of K and so we'll talk toward the end of today about a race again in characters and how you can actually do this not only for this P set but more generally, but realize by the end of this you'll be able to decrypt one or more secret messages that may await you in the P set. >> And then you move on to something a little more sophisticated. So Caesar cipher, not so secure, right? There are only 26 possible keys. I mean even I with a piece of paper and pencil could probably have figured out that these things said be sure to drink your Ovaltine, I just guess and check, guess and check, and I do that in average of 13 times maybe 26 times max and bam, I figured out what the cipher--what the plain text actually was. Well Mr. Vigenere actually introduced a variant. It's still a shift cipher but he realized well, if the fundamental problem is that these keys are just too damn short, you only have a number between 0 and 25 or 1 and 26 depending on how you count, well why don't we just use more than 1 key. In fact, why don't I use a different key for each letter in my plain text so I might rotate the first letter by 1 but the second letter by 2 and the third letter by 3 and then maybe I'll repeat that process eventually. So Vigenere as you'll see in P set 2 spec introduces the notion not of a key number but a key phrase, a keyword whereby if it's A, B, C, you assume that okay, the key ABC means first use a key of 1, then use a key of 2, then use a key of 3, and then repeat, just keep using this keyword again and again but look to the P set spec because like a good computer scientist, as all URLs start counting in 0 instead of 1 but the idea is the same. The Vigenere cipher, same idea as the Caesar cipher but you're using multiple keys and you're just kind of thinking of them as a keyword where each letter in the keyword represents a different number. But what about the hacker edition? So for those hackers among you, you will find that we are, as someone acutely noted on the bulletin board, help.cs50.net, that we are encouraging you to make Crack this week. A program called Crack that when run is responsible for taking as input someone's password and figuring it out what--figuring out what that password is. Now figuring out what that password is, even though it's been provided to you as ciphertext in encrypted form, it turns out that on a lot of computer systems, even MAC-OS, Linux, Unix, and in some form Windows, passwords are stored somewhere on your hard drive. Otherwise, the computer couldn't authenticate you, couldn't figure out yes or no you should be allowed access when you type your username and password. But they're not just stored in plain text, they're not just stored as your actual password in the file, they themselves are generally encrypted and so that's what we hand you the hackers for this P set. We're gonna hand you a file. A database from a real Linux system with real users and their passwords are all encrypted but thankfully, these humans who chose these passwords weren't necessarily the sharpest, they certainly weren't the most sophisticated and so they're not necessarily the strongest passwords, that is odds are with a little of savvy, a little bit of creativity in your code, you can guess with high probability what their passwords might be by writing a code that takes advantage of certain assumptions. For instance, some of you might have passwords that instead of being let's say the word hello, suppose that were you know your password but you might think alright, that's kind of too easy to guess. I know I've been told that I need to pick a better password and in fact the system made me choose a stronger password. Well maybe you would do H-E-L-L-0, right? It's stills pneumonically useful for you to remember that it's hello but the O is a 0 but maybe you can get more clever still, H-E-1-1-0. Now, this is not an English word that you would find in a dictionary, still looks and feels like hello. You can remember it more easily but at least it's a little more secure, secure in that if an adversary was just guessing and checking passwords going through like the Oxford English dictionary, just checking is this your password, is this your password? Well, this is not gonna appear most likely in that dictionary so you're safe. But the problem is a lot of people use the same trick, right, and if you're the cryptanalyst, the hacker taking--tackling P set 2 hacker edition, well maybe you should be able to leverage these very tricks that all of us think we're being so clever in using. So it's unfortunately not a clever trick if you're not the only one who actually uses it in the world. Just to take it down the notch into putting context the hacker edition of P set 2, we're fond of this clip from an older movie called Spaceballs. [ Laughter ] >> Alright, what are you doing to my daughter? >> Permit me to introduce the brilliant young plastic surgeon, Dr. Philip Schlotkin, the greatest nose job man in the entire universe and Beverly Hills. >> Your highness. >> Nose job? I don't understand. She has already had a nose job. It was a sweet 16 present? >> No it's not what you think. It's much, much worse. If you do not give me the combination to the F shield, Dr. Schlotkin will give your daughter back her old nose! >> No! Where did you get that? >> Alright, I'll tell, I'll tell. >> No daddy, no. You mustn't! >> You're right my dear. I'll miss your new nose but I will not tell them the combination no matter what! >> Very well, Dr. Schlotkin, do your worst. >> My pleasure! >> No, wait, wait. I'll tell, I'll tell. >> I knew it would work. Alright, give it to me. >> The combination is, 1. >> 1. >> 1. >> 2. >> 2. >> 2. >> 3. >> 3. >> 3. >> 4. >> 4. >> 4. >> 5. >> 5. >> 5. >> So the combination is 1, 2, 3, 4, 5. That's the stupidest combination I ever heard in my life. That's the kind of thing an idiot would have on his luggage. >> Thank you, your highness. >> What did you do? >> I turned off the wall. >> No you didn't. You turned off the whole movie. >> I must have pressed the wrong button. >> Well put it back on! Put the movie back on! >> Yes sir, yes sir. >> Let's go Arnold. Come Gretchen. Of course you know I still have to bill you for this. [ Footsteps ] >> Well, did it work? Where's the king? >> It worked, sir. We have the combination. >> Great. Now we can take every last breath of fresh air from planet Druidia. What's the combination? >> 1, 2, 3, 4, 5. >> 1, 2, 3, 4, 5? >> Yes. >> That's amazing. I've got the same combination on my luggage. [ Laughter ] >> Prepare Spaceball 1 for immediate departure. >> Yes, sir. >> And change the combination on my luggage! [ Laughter ] >> Ahh!! >> Alright, I just need a little break there. So a couple of announcements of things to come and things that are already in progress. So if you've not yet started P set 2, standard edition or if you have but you're finding yourself not quite sure on what paths you go down, do you realize if you didn't attend it last night, the video of the so-called walkthrough for problem set 2 is already online, there's a video on the problem sets page. These walkthroughs are led by Martha, one of our teaching fellows each Sunday night and they are really meant to be an opportunity again for you to get a sense of where you should go--where to begin, what roads to go down and what kinds of approaches you might take to the problems. So certainly before you think that ah, this isn't for me and throw up your hands not knowing where to begin, you'd begin with the walkthrough. Sections 2 are already in progress, they started yesterday, they'll continue today and Tuesdays, CS50 sections are Sunday, Mondays, Tuesdays. If you have to switch out of your section, that's fine. Follow the directions in the email that you received to reach out to the head teaching fellows but otherwise, certainly turn the sections next as a resource for reinforcing what might often feel a little bit fast, a little bit new in lectures. So a word on grades 2, so now that we know who your teaching fellows are, we're gonna start turning through P set 0 and P set 1, you should receive P set 0 within the week, P set 1 within a week and a bit and then we'll be back on track with P set 2 and onward. Per the syllabus, we used 3 axes to evaluate your submissions of homework, correctness which generally means does it work right, did you adhere to the spec, is it boggy or not, two is design. Design is something we really learn as we go and it's certainly much more subjective but it boils down to did you make some good decisions. There might not necessarily be one right decision but did you at least make a compelling decision that seems like a smart way to solve a problem or for instance, did you just take your code that worked for one part of the problem and just copy, paste, paste, paste, paste, as opposed to implementing something more obvious perhaps like a loop and so you'll get feedback qualitatively from the teaching fellows over time because realize that grade--realize that the problem sets being returned to you in this course really are not just about taking off some mark in our database or giving you just a pure number but it really is an opportunity for the teaching fellows to continue teaching beyond section, beyond lecture, and provide you with handwritten or typed qualitative feedback so that you actually do learn from mistakes or from otherwise poor decisions that you'll get better at over time. Style is really the aesthetics of one's code. Or your variables, Apley names or things nicely indented. Frankly, too many students frankly every semester kind of postpone the issue of style to the very last minute and cut this corner. It's one of the easiest ways to boost your score, boost the overall evaluation because it's so easy to actually take care of and even though it might seem silly right now to comment programs that are only this long, maybe it might be silly to use a variable name other than X when you only have one variable. Realize again by semester's end, your programs are gonna get more and more interesting, more and more sophisticated and these very much are life lessons of sorts when it comes to programming. So realize too because realistically you probably spend the most amount of time just getting your program to work and getting it to work correctly. We typically wait the access of correctness a bit more than we do design and a bit more than we do style. >> So for instance, if you don't for instance comment your code, it's not gonna chip away a third of the overall score. But what are the scores? We use very course metrics. So it's essentially a 5-bucket scale where it pours all the way from the less, fair, good, better, best. They roughly correspond to 1, 2, 3, 4, 5, but if you get a 3 out of 5, yes the mathematicians in the room will realize that 3 to 5, that's 60 percent my god, I got a D or a C already depending on where the line is. Don't do that. It's irrelevant in CS50. So really in the beginning of the semester, getting a whole bunch of goods maybe even a fair so and then moving your way through the term up to better and best or 4s and 5s. That really is the trajectory we expect students to be on. So unlike my first Expos paper in which I got like a C minus and was completely devastating, a good in CS50 should not have that same psychological effect that it had on me. Good is good. Poor, oh, poor is poor. So room for improvement if it's poor. [ Laughter ] >> But starting off at good is not a bad thing and also a pass-fail. So we still have the pink forms at the end of the stage. Today, I believe is the deadline for adding or dropping courses with no fee but up until the fifth Monday of the semester can you change letter-graded or pass-fail status with no fee so realize you still have some time if that's of interest to decide beyond today. It's the fifth Monday of the term for changing letter-graded status without fee. So with that said, we've been looking at data, we've been looking at you in terms of your responses to P set 0 and P set 1. This is the mash up that we made on the course's website where you can click around and see which where all of you are actually from so we like to look at this kind of demographic data and it's really quite neat that we have folks from all over the world, certainly. In terms of more local numbers, we look at the breakdown by class and it's actually pretty consistent as it's been over the years. We have a lot of sophomores, roughly twice as many than in the other class but the other three classes, freshmen, junior, and senior is roughly about the same, about 100 of you each so especially the seniors if you feel like I am the only senior in this room who never actually took this class before now, it's not true. There's like 99 or so others of you. So realize we have good numbers all around. Just for fun, we looked at some of the other demograph--well actually, just for fun we looked at some of the phone data and operating system data but more importantly, we looked at the comfort level so here too to reassure perhaps that there are more people like you whether more comfy or less comfy, realize for the first time this year the less comfortable students have surpassed the other two pie slice this year, so that's really good. So realize especially if you are among those less comfortable that you are an increasing chunk of the pie here. In terms of how much prior experience specifically people have had, 0 courses is the answer for 77 percent of the students in this room. So though you may think that everyone around you has taken one or more courses, only 17 percent have taken one and only 6 percent have taken two or more. I was in--I couldn't help but notice the patterns of these charts, it doesn't look quite as good on the overhead but I was teaching myself keynote this morning. It's kind of fun what you can do with these products. Anyhow. In terms of phones and stuff, there's really no academic basis for this one, but in terms of phones here, iPod Touches are very popular apparently because Apple gives them to you when you buy a Mac these days. iPhones though are pretty popular, Blackberry Android, three of you have the Pre but a lot of you are "normal." Many, many, many, almost 200 of you have just normal, what we would call a normal cell phone. So we actually do ask this data for useful purposes because the course is increasingly focused on building out a suite of apps particularly focused on campus. It's actually of genuine interest to us to know exactly what the user base is out there and it's hopefully useful for you as you start to think toward the end of the semester about final projects. If you build it, would people come, would they actually use it? Well, there's a pretty good size demographic of Blackberry users, iPhone users, Android users, so those of you who might be interested in doing mobile projects for your final project, you definitely have a target audience these days. It's about 50-50 still which is consistent with the other people's statistics. Many of you over 150 are running Mac OS snow LEOPARD the latest version followed by Windows 7, some of you have an upgraded from 10.5 Mac OS, some of you haven't or can't upgrade from 10.4 Tiger OS, a bunch of you have Linux but it's pretty evenly split overall. I will mention that if you haven't noticed already, on CS50's website, thanks to the support of friends in the industry, we have a lot of resources available to CS50 students, many of which are relevant particularly at term's end but we have access for free to the iPhone and iPod and IOS-SDK so you don't have to pay the 99 dollars to actually use that. We have under MSD an Academic Alliance for CS50 students and their friends, all sorts of Window software including Window 7 so if you're in that, especially the Vista bucket, realize you can download for free following the directions on our software page and upgrade. Realize it comes with absolutely no support from us but the software, the DVDs and such are yours to download if you would like. So finally, and this was actually my favorite number to be honest because it really makes us, it really reaffirms some of the efforts we've made in recent years. Now the most common reason for taking 50 is actually as an elective and it's now surpassed taking it for concentration credit which we thought was quite interesting. It's a pretty big chunk of you that don't know why you're here. So that's okay. We'll hopefully give you a reason toward the end but it was nice to see that we have a pretty equitable distribution now of people who have to be here and people who actually want to be here. So with that said, let's turn our attention back to the command line for just a moment. So I'm gonna go into my little terminal window here, those with PCs who have been using potty, I'm using terminal on a Mac, I'm gonna go ahead and SSH to cloud.cs50.net although let me be extra careful and I'm gonna provide my username. It's gonna then prompt me for my password and now I'm at my prompt. Well, we recall from last week, from your printouts, we looked at some, you know, sort of warmup exercises, the annoying 99 bottles of beer on the wall song was useful only in so far as it gave us an opportunity to play with loops and such. So what I thought I'd do is go ahead and start off by let's see doing beer. Let's say I'm gonna reinvent one wheel here at least in real time, I'm gonna go ahead and reinvent beer 2.C you can follow along at home if you would like. This song is gotta be printed to the screen so I know I have to start off with include standard IO.H. I don't think I need CS50's library but I'll come back to that in a moment. I know mindlessly right now, I'm just gonna start this program like this because I don't need any command line arguments so I'm just gonna say void, I don't need org C or org B and then what do I wanna do? Well, I'm first gonna tell the user print F how many bottles of beer, question mark. And them I'm gonna leave a space just for aesthetics and then oh, wait a minute, if I actually wanna get this in from the user and I'm not using command line arguments, I need to use what function? >> Get ints. >> So get in probably and we'll see in just a week or two's time, how you can solve these problems of getting ints-getting strings from the user without using these training wheels of the CS50 library. Before long we will take that away and you'll realize it's--you're the better for it because you can do more sophisticated things. But for now I'm gonna go ahead and use what I know the cs50.H file so that gives me the ability to use get ints and then what do I wanna do? Well, a little sanity check and so even if it's not explicitly said in future P sets, you should absolutely always ensure that your program will not break or crash or seg fault or do any of these weird things if the user is just being difficult and so I'm gonna do a sanity check. If N is less than, let's say 1, I'm gonna ahead and yell at the user and say print F, let's say, sorry that makes no sense. New line. And then I don't wanna just move on, right, because this would be a logical error, I need to do what at this point? Yeah, so I'd probably wanna return 1, 1 being fairly arbitrary but it's nonzero and that's the key, zero means good, anything nonzero generally means bad and most people choose their error codes with 1 and then move on up. If I didn't do this and kept on going, I wouldn't actually stop the user from proceeding so alternatively, I could use a loop, maybe a do while loop but for this example I'm not gonna add such sophistication. I'm just gonna go ahead and abort if the user is not playing along as they should. So now I'm gonna go ahead and sing this song. So I could do this. So 4 int I gets, let's say, 99 while I is greater than or equal to 1 and then do I minus minus on each iteration. I don't exactly know where I'm going at but I know in general I wanna start counting at 99 and I probably wanna stop when I hit zero or maybe really 1 because remember in the last verse of the song, I say one bottle beer in the wall, one bottle of beer, take one down, pas it around, zero bottles of beer on the wall. So I don't wanna count down probably all the way to zero because then my last sentence is gonna mention the number negative 1 which would be incorrect so I'm just having a little bit of foresight here so now I might do something like this. So print F, how do I print 99? So 99 bottles of beer on the wall. Alright, so now I've already screwed up, right? I actually wanna use a variable here not just 99 so this becomes percent D for digits and then I need a comma at the end here to fill in that place over which it should obviously be I. So now I have 99 bottles of beer on the wall. The next sentence is easy, so let me just paste it, 99 bottles of beer, I think that's right. So now I do a new phrase, print F, take 1 down, pass it around, percent I. >> That one was easy. New line. Print F and pass it around percent D bottles. The song's not only annoying, it's boring. Beer on the wall--on the wall, but so here is my one moment of plot. I need to do something slightly different here which is to insert what value for this place holder now. >> I-- >> Yeah, so probably I minus one and I can put that in a variable but there's really no need. I can just do the mathematics in line and so now I think I have the right song. Ninety-nine bottles of beer on the wall, 99 bottles of beer, so same thing, take one down, pass it around 98 bottles of beer on the wall. So is there any risk that this program is going to go to negative one or beyond? Okay. It doesn't seem to be. What if the user is difficult? What if the user starts by typing in--well, there is a bug here. Yeah. So I actually was supposed to start not at hard coded 99 but at least what the user actually wanted to start singing. Okay, so that's fixed now, right? So now, it's not hard coded as 99. So now supposed they typed in 99, it obviously works. They typed in 299, still works. If they type in zero, it should stop way up here. So I think we're okay. So this was essentially what we call beer 1.C last time but I offered in beer two which you do have among your printouts. There are some alternative approaches. I'm gonna leave this here for just a moment just so I can actually see what I once did and kind of translate it now to a different construct. I could actually do this while N is greater than zero, you know what, I could just--let me get rid of this for loop altogether. Now N, I don't use I, you know, why don't I just plug in N there, plug in N there plug in nothing there and then plug in N minus one here and now is this an equivalent implementation? >> Decrement. >> Right, so I need to decrement somewhere and I could be clever and I could actually decrement it in a couple of different places. Here, I'm gonna go ahead and actually just go with the obvious and do N minus minus. Now--or I could be more explicit and get the same thing minus one or as you might have seen in the textbook, you can even say minus minus N. In this context, they're all equivalent. So I'm just gonna say N minus minus to be consistent from our earlier sock example which is when we learned the syntax. Is this now equivalent? So it kind of is, right? I think the song would be sung exactly the same. So what's an upside of this approach? Well, I'm not introducing a useless variable--an unnecessary variable I, I'm just reusing what I have but at the same time this is now destructive behavior. I've gotten an int from the user calling it N and I'm using N to my advantage decrementing it on each iteration but supposed at the very end of the song I wanted to say thanks for playing N bottles of beer on the wall. I've obviously lost track of what? So the user's original input, and then there's another one that's kind of harder to put your finger on. Which is better, the for loop or the while loop. Anyone wanna argue for the for or for the while? Which is better? >> The for loop. >> For loop. Why? >> It just seems better too. >> Okay. So that's not bad. No that's not bad, right? I mean frankly that would be my answer sometimes to these questions. It just kind of feels right. Does anyone wanna argue one way or the other more specifically? [ Inaudible Remark ] >> Does the for loop use a while loop? >> Yeah. >> In what sense? Like is it underneath the hood really using a while loop? So that depends. It's really up to the compiler to decide how to implement something like a for loop or something like while loop so they're not likely being implemented with each other. It's lower level than that. [ Inaudible Remark ] >> What's that? [ Inaudible Remark ] >> Can I explain the difference? So, sure, so at the end of the day frankly, there's none. There--our looping constructs that allow you to loop from something to something but in the case of the for loop, recall that I had to do the looping very explicitly. I had to say for int I gets N. I is greater than or equal to one. I minus minus so in short, is this kind of like a stick shift in a car, manual control. I have to be very much in control of what's going on in the loop and very much explicit whereas the while loop here, it gives me much less control. It's kind of like automatic but it's not quite automatic. It's not a perfect analogy 'cause still at the bottom of this thing I have to do the decrementation myself. So at the end of the day, it's mostly a stylistic thing. Which one makes the most sense? Frankly, I almost always reach for a for loop because I like the explicitness of it even though the syntax is a little ugly with the semicolons and all that. I just kind of--once I understand how it works I can then specify very pedantically initialize condition update whereas while this to me just looks a little uglier but these are just my eyes. So in short, it doesn't matter and this is testament to what we emphasized in the P set, that there really is no one right ray to implement this things. Now let me go ahead and back out of this for just a moment and let me go ahead and make--go into an alternative implementation which we called beer, let's say beer four. So in beer four, I decided to get a little more clever. I've taken out the comments. You do have a printout of this from today. So in beer four, the same code I'm using up top here but now you notice, actually don't wanna do this, let me back up actually. We'll start with a cleaner one. Beer three, one page prior. So the top of the code is the same but notice what I've done here. Rather than cheat with the parenthetical S which I kind of disclaimed last week that isn't completely punting. I'm just taking parenthetical S so I don't have to deal with plural expressions of bottle--bottles or singular bottle. So here I wanted to get a little smarter. So notice now in this third version of beer, everything is the same up top except for the stuff that's inside the for loop and what's going on here? I still have this place holder percent D. But now I have another place holder percent S because I want to conditionally spit out bottle or bottles depending on the value of I. Now, how do I do this? Well, I can actually do this in a couple of ways and let me go ahead and delete momentarily what I've started with to show you the more explicit approach. To make this work, I kind of need to say something like string S1 and then string S2 because I might have one word in part of the song and another word in the other depending on the number. So now I might do this. So if I is greater than one let's go ahead and say what? S1 gets, let's say what value here, bottles. Otherwise, I'm going to say--keyboard problems--S1 gets bottle, right? So I've done my logic in such a way that if I is greater than one. Well, I wanna say the plural, if it's not greater than one and presumably equal to one, I wanna say bottle and now what can I do over here? Well, notice, I can plug in percent D the number then percent S, the string which I'm calling S1 and then I can do it again on this line below. And this is a branch. This is a condition. It's terribly explicit right now and so I have now this variable S1 that I can plug in dynamically. Why did I mention S2? Well, I kind of need to do the same thing. So I kind of need this here. So I need a few copies of this line because now I need to say actually, if S, let's say bottles if it equals S1, then what do I have to do here? So now I have to think about the logic for that second value, right? So for the second word in the last sentence of the song, I need to think this through. So what do I do? Well, this is why I kind of cleaned it up. So let me--oh interesting my undo feature is not undoing. Let me go back into the original version here, so we can introduce one other piece of syntax. So this is the one and only I think ternary operator that we're going to use. So we've used a bunch of binary operators, bi meaning two, X plus Y. The plus is a binary operator 'cause it's got an upper end on the left and upper end on the right. Turns out, then this is a bit of a special case. There's this thing called the ternary operator that actually has three upper ends on the left, in the middle, and on the right and the special syntax here is question mark and colon. And we introduced this not because you need to now learn yet a new piece of syntax but because you might see it and being able to read this as useful. So notice what I've done here in this very elegant, there say one liner, I'm declaring a string called S1 and then I'm assigning it with equals to the following expression. Well, what does this expression evaluate to? Well, notice the first set of parenthesis. It says I equals equals one as the parenthesis hint at, this is pretty much equivalent to saying if parenthesis, something is true, do this else do that? So really this is a one line way of saying if something is true, do this else do that. So the question mark essentially denotes the "if" part of the construct. The colon denotes the else. This is identical to doing if I equals equals one then set S1 equals a bottle L set S1 equals bottles, but why is this arguably better? Well, you saw how messy my code was getting, it was such a simple thing and yet here I am writing eight lines of code to solve this problem. This is why there is this stuff called syntactic sugar as a geek would call it which is just features that allow you to do something in a different way but not necessarily something that you couldn't do otherwise. So this is a ternary operator using question mark and colon but the end of the day, the only optimization I've achieved here is to plug in dynamically S1 and/or S2 so that my grammar frankly is now correct. And I'm not cutting that stupid little corner to say bottle parenthesis S close parenthesis. But there's one more improvement we can make on here, so one last focus on this silly song. So notice in this version, I decided to factor out the song because it feels like conceptually I could put this in a function, right? >> Recall that a function is like a black box that you yourself can implement or that someone else implemented like print F but you yourself can implement these things and if you can imagine--if the thing you want to achieve feels like just conceptually, it can be bundled up and given a word like chorus. Well then it might very well be a candidate for a function. And the fancy word here that you might see in one of the recommended text is hierarchical decomposition. This just means taking out logical chunks of code that collectively kind of have a conceptual definition, sing a song, sing the chorus and putting them in a function of their own. So apparently, I've implemented a function called chorus. It takes how many arguments? So it seems to take one. I'm being a little clever here at the risk of being confusing and I'm trying to be--show off my coding skills here even though this is not the most clear but let's see if we can tease this apart. I seem to have a while loop. Recall that a while loop iterates again and again and again so long as the thing in parenthesis is true or more generally none false. So not zero. So remember that false is zero. Anything else is true. So this has the effect of iterating again and again and again while N is anything other than zero, right? So this is why it's clever if a little confusing, it's clever in that if I know I'm decrementing N and N and N and N down, down, down eventually, I'm gonna hit zero so this loop will stop. So it's just my clever way of leveraging what I know to be a condition and a Boolean expression in that condition and a variable that's going to return conceptually true, true, true, true, true that is nonzero, nonzero, nonzero and eventually false, that is zero. So how did I implement chorus? Well, chorus actually is just a copy paste of the code we just wrote in the third version of beer but I've wrapped it this time with a functions declaration. I'm returning void 'cause this thing just sings. It prints to the screen. I don't need to actually return something like get int or return something like get string. I just wanted to print its response to the screen and then return immediately. So I'm using this little grammar trick here but I could implement this we've seen with an if and an else but notice that I do need to take as input to this function the number of bottles of beer, let's call it B, that I actually wanna sing about. And once I actually take in B, now I can plug in--there's loop--there's no for loop here. Notice that I plug in B here, I plug in S1 for bottle or bottles and I plug in S2. It's the exact same thing. So where is B actually changing? Well, notice where did I call this function chorus? If I scroll back up, I mean D in inside the while loop and on every iteration I'm calling chorus passing in N but again just to be clever if confusing, I'm decrementing N at the same time. And so what really happens here is the first time chorus of bracket N minus minus is called the number 99 does in fact get passed in. But the moment chorus is done executing, there's still a little more work to be done before the next iteration. What's that little bit of work? The minus minus then actually needs to happen. So I meant--point this out frankly not because you should start coding in the most succinct way that you can 'cause arguably every time I look at this, I have to think alright, does this actually subtract properly or did I screw up my own code but frankly when you look in text books, when you look in online references, you're gonna see syntax like this. So it's worth at least tucking it away so that you can reason through what's going on. Yeah? [ Inaudible Remark ] >> In this case because the minus minus is applied inside the parenthetical. It first passes in the current value and the minus minus happens after. So 99 does in fact get past correctly. Yeah? >> Is this a simpler way then do you agree? >> Is there--is this a simpler way? [ Inaudible Remark ] >> It's a good question. I would say this is kind of on the fence to be honest because at this point, I haven't really gained all that much in adding this function chorus, right? Because really all I did was move these six lines of actual code from my main function into their own function. So arguably here, I'd probably leave it in main, right? There's no sense in creating work for your self, re-breaking things up into functions. If at the end of the day, your program is still just as long and you haven't really fundamentally improved it but we need this ability. We need this building block as proceed later this week and next so that as we start to design again, increasingly interesting programs, we have now this primitive to deploy. So here, I'd say it's on the fence. Beer obviously, frankly, I'm pretty happy with beer 1.C. Yeah? >> So S1 and I don't understand why that--why do you need the string S2? >> So good question. Why do I need the string S2 in addition to S1, 'cause my whole point here is grammar and because my wording changes potentially in the last sentence when I subtract off one of those bottles of beer from the wall. It's possible that I'll first be singing about bottles of beer but then I'm left in the last sentence with one bottle of beer so I need two variables S1 and S2 just in case my grammar needs to change according to the song in the very last verse that I'm singing. >> But doesn't it change like the image--like grammar is does it change like the image [inaudible]-- >> So it will change--so if you reason through, like what I would do is take a simple example like N equals three honestly and just think through or jot down what each phrase is and what you'll find is that initially, S1 and S2 are both bottles 'cause I'm singing about three bottles of beer. Take one down pass it around, two bottles of beer, but then eventually when I'm gonna get to two bottles of beer on the wall. Two bottles of beer, take one down pass it around, one bottle of beer and that's why I need this second variable to handle that silly little grammar, that little corner case. But let me go ahead and turn our attention to now a similar example that we looked at which was at the start of our discussion of arrays. So recall that in the context of arrays. Let me pull up the right visual here. We described arrays. It's just a chunk of memory and a chunk of contiguous memory such that if you wanna able to store 10 ints, yes you can declare ten variables but very quickly does the copy paste become clearly the wrong decision if your code is starting to look like a mess and now you're changing 10 different variable names. So thankfully, we introduced to the picture this notion of an array, where you can allocate just one bigger variable, break it up into conceptually identically sized parts, each of which can store an int, each of which can store a char or really any other data structure as you we'll soon see and the utility of this was that we could now take in multiple types--multiple inputs from the user but store them all essentially in the same place. So let me go ahead and open this file here, array 1.C which does exactly this and introduces just a couple of new useful tricks. I've stripped out the comments from my version but you have the comments in yours. Let's see if we can wrap our minds around some of the new tricks we're using here. So notice first at the top of this program, I'm taking main as the parameter to main because I'm not gonna use any command line arguments that's the com but now notice here, I'm declaring explicitly a float but you know what? This program's purpose in life is to ask a student what their grades are for some class and then just compute their average. But the catch is I don't necessarily wanna hard code into this program ten different ints or ten different floats for their grades. I wanna store them all together in something called an array. So what's the syntax for that? When we began to see this last week, when you wanna declare an array of floats, you simply say what data type you wanna use, in this case float, the name you wanna give this variable and then the new piece of syntax last week was square brackets and then inside the square brackets needs to go a number, the number of buckets that you want. The number of spots that you wanna reserve all on this picture for floating point values in this case. Now what the heck is capital Q-U-I-Z-Z-E-S? Well, this actually derives from a trick that I did up here called defining a constant. So it turns out a useful feature in a programming language is if you know in advance that you wanna have a hard coded number but you're gonna use that number in multiple places potentially, maybe in a for loop, maybe to declare your memories, maybe to allocate memory for the array. It's really nice and really compelling to factor out that constant like two and putting in something called the constant. So anytime you wanna express the number two in this program, you just say quizzes again and again and again rather than typing two here, two here, two here. Now, just intuitively even if you're new to programming, while it might be useful to define two in terms of this constant. How about over here, yeah? >> What if they had four quizzes instead of two? >> What if they had four quizzes instead of two in which case? >> You wouldn't have to fix all the twos later on. >> Right. It's just utility, right? I don't have to go through my code and change my number in four different places and frankly, the more places it is the more likely I am--just or if I'm tired or if I'm just a little disoriented because the code is getting much, much bigger I might miss a spot. And now I'm gonna be iterating in some loop from zero to four and yet over here I'm gonna iterate from zero to two just because I didn't change that two. So factoring it out can be both useful and it can also protect you against stupid mistakes. So what are we ultimately doing in this first line of code? I'm saying float, grades bracket quizzes. So this gives me an array that looks like this. Whereby, this is 32 bits, this is two--32 bits, they're back to back. This whole thing is called grades but inside each of these boxes can I fit one floating point value, then you notice the comma. So it turns out you can either declare variables one at a time if need be or separate them by commas if it's the same data type. So I also--because I'm gonna be computing their average. I realized that I need the summation of some numbers, so I'm also declaring a single float called sum. This is somewhere else in memory. >> It's the same shape or the same size but this thing is called sum now. It is not part of the array. It might end up somewhere else altogether. Only the array is back to back even if you're code is on the same line. Well, finally, it turns out I'm gonna need an average in I and actually, let me clean this up because I don't actually need to declare these up here. I'm gonna do this a little more tightly in here just to be consistent with some past examples rather than distract. Okay, so now I'm declaring those ints only when I actually need them. So what--it doesn't matter if you do that. The approach I had up there was sort of old school. This is sort of a newer tighter approach. So how does this program work? First a loop, from zero to quizzes. So this thing is gonna iterate twice, print F quiz number something of something and I'm just doing some little aesthetics. I'm printing out quiz number one of two, quiz number two of two. I'm trying to be a good user interface here and then notice the syntax for using an array and this is where it's really useful. Even if you're on a loop, can you use the same exact syntax to grab each and each float from the user and just increment where you are in the square brackets? So by saying grades bracket I close bracket, that means plug in through first location I equals zero then plug in to location I equals 1 then, oh that's it. Because quizzes itself is just two. So the syntax really is identical to what we might have done last week. But now because we have the ability to store multiple things back to back to back, we can start using these variables like I to just move our finger on the board, move our place holder and memory to store more and more values. Now what's this? Well this is kind of simple if unnecessarily distracting syntax for implementing the notion of averaging. I first initialized sum to zero then I go ahead and iterate from zero to quizzes then I go ahead and add to my summation the first grade bracket I, the second grade bracket I and then what do I have? I have the sum of their grades so now I know mathematically to get the average. I take the sum divided by the total. So that's whatever their sum is divided by two and yet what's with this crazy syntax? What was I actually trying to achieve here? [ Inaudible Remark ] >> Yeah. So it turns out some of you might have for P set 1, maybe P set 2 have been using the--actually--probably not for P set 2. For P set 1, you probably used or considered using something like the round functions so that you could actually round the change properly when you convert it to cents or you use the round function in the math library most likely and that's perfectly fine. It exists for that reason, but how do you think someone else actually implemented the round function? Well, it turns out with these very simple building blocks. I can take for instance the value of sum divided by quizzes. This is not gonna give me zero 'cause remember that sum was initialized as a float so this is what I think to be the notion of an average but supposed the user's--supposed the student's average right now is like 99 point let's say six, 99.6 on their two quizzes, right? That--the Harvard student would really like to get, what on their final grade? Like 100 percent, right? 99.6 gets rounded up to 100 percent, that should be my grade but not in the world of a computer. If what I'm ultimately storing in their average and on their transcript is just a number from zero to 100, what's gonna end up there, if I cast to an int? >> Ninety-nine. >> It's gonna go to 99, right? 'Cause remember when you cast to an int, you throw away everything after the decimal point. So how do you actually round if you yourself wanted to implement this notion of rounding? Well, it turns out using a computer, just add 0.5 'cause that'll push the right students over the edge, right? Assuming--ignoring some of the imprecision issues that will push a student from 99.6 to a 100.1 but damn, now the int rounds them back down to just the 100. So how do you implement round? You know, it looks a little syntactically distracting but it just boils down to push them over the edge 0.5 and then round back down using the casting. That's all it is to round. Alright, let's take a five minute break. Alright, so before we move on to something a little more visual, just an emphasis on one detail about string. So again, an array is a little something that looks conceptually like this and thus far we know that we can put floats in there certainly. We can put ints in there. We can put strings in there. In fact, recall our brief discussion last week of argv which you'll spend more time with in problems set 2, argv, argument vector is an array but each of the elements in that array are themselves, what? Array is technically or more higher level, they're strings. Remember argv is the second the parameter that main can take and inside of argv is every word that the user typed at the prompts and if it's every word, that means every string that they typed at the prompt. So argv is an array of strings. So it turns out that in the problems that you'd expect discusses this, it turns out that a string itself that we call S-T-R-I-N-G right now itself is actually an array because the string as a series of characters is just something that looks like this where each of these boxes is not a float or an int. It's actually char, char, char, char, char and then a special symbol at the very end once you're at the end of a string, so that the computer can tell. The word ends here. Well, let's take a look at how we can leverage this. So here is string 1.C. It's also among your printouts. Notice I'm using my familiar CS50.H, my familiar standard IO.H but also another header file called string.H. It turns out you don't need string.H to use the data type string because, remember that S-T-R-I-N-G is actually declared in CS50's library. The reason I need string.H is because I wanna use a function that we saw briefly last week called string length or strlen for short. So what does this program do? Not all that much. Notice that the first thing I do, is I'm not even dealing with argv and argc here. I'm instead getting a string from the user via CS50's library by a GetString. It turns out and we'll see this as we peel back the layers of CS50's library and actually look at its own code. It turns out that what GetString is really returning is not a string per se. It's returning an array. An array of characters that, we the humans interpret as a string, a word, a sentence, a phrase, or what not. So what I'm actually storing in S is an array. Now that too is a bit of white line. It's something we'll correct over time. It turns out you can't pass a whole array. This picture here, you don't pass this whole chunk of memory back and forth, back and forth. It would just be too inefficient. You have to copy way too much data back and forth. In fact, what the computer instead does is when you return an array or pass an array it actually underneath the hood just returns the address of the first chunk of memory in ram. So for instance, if this lives at byte number zero in your ram, this is byte 2, byte 3, byte 4, byte 5, and so forth right in your 2 gigabytes of ram. If you return an array, what gets returned in this case for this array is the number zero. Now fortunately, zero never gets returned even though I start counting at zero, there's other more important stuff at the beginning of your computer's ram but at the end of the day, each of these chunks just represents--it can be addressed by some number in memory. So just as a teaser for now, anytime we pass a string or more specifically an array of characters, we're actually just moving addresses around. And this is when we'll see the real power of C before long but also some of the security threats in moving things around by memory address. So here's the little sanity check that's now consistent with that revelation. It turns out that the user might not actually give you a string. If you hit Enter without providing a string, you'll actually get a very short string that doesn't seem to have any characters but it's not null. But it turns out if you hit a certain sequence of characters on you keyboard, you can actually pretend to literally give the computer nothing including not even a carriage return. Not even the return key on you keyboard. So anytime we started dealing with strings, it's super important to check, does this string actually exist? And we can check if a string actually exists or it's just nothingness by using a Boolean expression and by comparing that strings name against the special value--special constant using the jargon from the last example with quizzes, a special constant called in all caps, null. So essentially, when S is null and this is why I said my strings don't actually live in memory at the address zero when every time we draw a picture of a computer's ram which I just keep drawing for now is this big rectangle like this. It turns out that if this is memory location zero in ram, there is in fact some important stuff that lives at the bottom conceptually of your ram and that's the reserved for the operating system which is to say a program that you yourself write, you should never be handed the address zero. You should never be told, here's an array, it lives at address zero because you know in advance that must belong to the operating system, can't be mine, therefore, I should not even go there and so what the world has adopted as a convention is if you ever get back the special value null, this is actually a constant that represents the notion of the number zero. This means something bad happened. The user did not actually give you a string as you requested and so the computer is returning the address of the first chunk of ram which by convention is not yours which means you better check, is that string null because if it is, don't touch it. Don't start traversing it as though there are characters there. So in short, null is a special sentinal value that means something bad happened. Do not proceed. It's a stop sign of sorts. So if it does not equal null, then I'm safe. Then I know I've been handed conceptually a string. I've been handed an array. I've been handed more technically the address of a chunk of memory but more on that next week. And so I can proceed. Well, my purpose in life with this program is simply to iterate over the string, and to demonstrate that a string is just an array. >> And if a string is just an array, that means I can use this new syntax using square bracket notation and print out one character at a time by iterating from the zero character to character bracket zero--to bracket one, to bracket two, to bracket three dot, dot, dot up until the very last character in the string. So first, let's run this program. Make string one, I'm gonna go ahead and now run string one and I'm gonna type in H-E-L-L-O Enter and all this program does is print out every character one at a time with a new line character. How did that happen? Well let's see. I first do a sanity check. Did the user definitely give me a legit strength because if he did, then it won't be null, so I'm safe, then I have a for loop. I'm gonna iterate from I equals zero up to I is less than the length of the strength, so I don't want to--you go up to the equals the length because I again I start counting from zero, so this is old stuff, I plus plus. So this for loop means walk across the string from left to right, then what do I do? I declare a charge so I have a specific variable to play with and I store in C the Ith character in my string S, that is--the square brackets mean go to this location which is initially zero, get me the first character then do what with it? We'll present C as the place holder for print F for the notion of a character, backslash N just puts the cursor on the next line and so I print out the letter C. And so all I'm doing there is printing out what the Ith character is. I can be a little more specific here. Let me go ahead and say, the let's say, character number percent D is, and now I can just plug in I here, oops! Now I can plug in I here, so I'm gonna explicitly say what character is what? Let's--make compile that, rerun that, hello and now it's very explicitly telling me character zero is H, character one is E and notice even though this is a five letter word, there is no character five. In fact if I go to five, I'm gonna be stepping beyond the boundaries of the array and let's just see as a little sneak preview what might happen. Well, a common mistake would be to this, iterate from zero to the length of the string, that's actually gonna be one to many, let's recompile with make, let's rerun with string one, hit Enter, now give it a word, hello. Okay, so that's not too bad. It's definitely buggy but at least nothing bad happened. Now let's just do something stupid. Let's assume that the user's always gonna type in 100 character string, just to see if we--at what point the computer breaks. I recompiled with make, I'm gonna rerun string one, hit Enter, H-E-L-L-O Enter, okay, so far not bad, right? I am so far not screwing out things too much, not let's go back in here and say, you know a hundred--let's go to 10,000. Now what does this really mean? This means I have typed in to be clear and apologies that the board is getting a little messy, this just means, if I've typed in H-E-L-L-O, I only have a string of length five which means H-E-L-L-O so now, let me draw a rectangle around this thing. So this means I have one byte, another byte, another byte, another byte, another byte and then it turns out even though I don't see it, there's always this special sentinal value at the end of a string that I don't see but is there, it's backslash zero which is essentially the same as null but its defined a little differently so it's backslash zero, you don't see it but it is there. So the length of the string is indeed five but when I accidentally printed out the sixth character, the reason I saw a blank line was because zero doesn't have a keyboard equivalent, so it just printed as blank. But now, what am I doing? I just iterated from zero to a thousand which means literally, I'm going here, here, here, here, here and thankfully 'cause this program is so short, it's not doing much with my ram at all, there's just nothing there. It's all blanks, its all zeros. But surely, if we really get obnoxious, we can push the limit 10,000 characters that way in sanders must have some data for us, so let's run string one, type in just hello again, still not being a good demo, let's keep going and let's multiply by a factor of a hundred again, rerun, H-E-L-L-O, there we go. So now, 135,000 bytes that way there is some data that really does not belong to me. The operating system owns it. And the moment it detected that I was trying to touch that memory over there, it killed my program and induced what's called the segmentation fault which as we'll see before long just means my segments of memory are overlapped. I'm touching memory that is not mine. Now, obviously, if your making this kind of mistake in the program there's probably some other issues going on, right? 'Cause this was completely contrived but it does hint at the fact that if you don't check the boundaries of your arrays bad things can happen. And again as a teaser to security, when you start allowing the user to write anywhere in memory, I could put some dangerous code, some crack code that actually compromises the system, let's me in and that's how you induce it by plugging at places that you didn't expect there to be code. Yeah? >> So instead of percent C for the percent D there will we see all of the data that was actually in those bytes? >> A good questions, so supposed I print out not percent C but percent D, so I print this character, not as a character but as a number which we know is the case because the numbers are chars, chars are numbers underneath the hood, it just depends on how I wanna view my world. Let's actually see. So let me go ahead and rerun this thing now and type in hello again and if fact they were all zeros by default but the last one was something that I should not have touched. So let's go ahead and do this. Let's actually start using these things for some useful purposes, sort of game show style, I came prepared here. Thanks to the teaching fellows. I know, it looks fun, alright. So, don't cheat. Someone who did not just see one of the secret things behind the doors here, I need one volunteer, as our little teaser here, yeah, in the black shirt come on up. Alright, so the goal at hand now is to transition from this very low level focus we've had the past couple of lectures on syntax and on arrays and loops and all of this and now take it up a level conceptually to actually solving real problems with some of these new tricks. So, I have on the board what I claim is going to be my poor man's implementation of an array. I'm using pieces of paper and behind each of these pieces of paper is a number as though, this is an eight byte array up top or an eight int array up top, and an eight int array on the bottom, and what's your name? >> Talla [phonetic]. >> Talla. >> Yes. >> Okay, nice to meet you, so your task here and I'm giving you no foreknowledge of this is find me, let's say, the number 50 in the top most array, now you, the computer, or you the human have no foreknowledge of this array, do you? >> No. >> Okay, you were not involved in setting this up were you? Okay, so you have no idea where the number 50 might be. So I ask you, the human or computer, however you would like to think of your self, find me the number 50 in the top most array implementing that process however, you see fit. Find me 50. Nope. 61. Nope, 171. Nope, 179. Nope, 121. Nope, 51. Nope, 141. Yes, the number 50! Excellent, very nicely done! So this is where the algorithm got clever, alright. [ Laughter ] >> That's good. No, it's good! If you--you ruin the whole demo if you jumped to the right answer too soon. So, okay, so what was your process there if you could just explain in words and let me rather than talking into my chest, why don't you take this? [ Laughter ] >> I started up the first one and I just moved down and then the wind blew that one up and I saw it was 12, so I skipped it. [ Laughter ] >> Okay, fair enough. Okay, so that's pretty reasonable, right? 'Cause anytime we've coded something involving iteration, moving from something to something else. We generally start conceptually at the left. I int I gets 0 and then we plus plus but we could have started from the other end and I was hoping you wouldn't try to be clever and start at the other end and it worked out okay. But this is not terribly efficient because in the worst case here, and very deliberate case, it took you as many as what, 8 or 7 steps or more generally N steps where N is the number of doors behind which there are numbers here. It took you N whole steps just to answer that question for me. So I asked you could you have done better. >> Suggest a random number? Like random number here? >> When you put it that way, it sounds kind of it matches but yes, could you have done better in finding me the number 50 with these numbers. >> I don't think so. >> Okay, so no. The answer is no, right? With no foreknowledge of these numbers and with no assumptions to govern what algorithm you implement, you just gotta try them all. You have to brute force your way through it as we say in the hacker edition of P set 2 with passwords. Alright, so what if I give you another piece of knowledge. So suppose now that you have a second array, but this time, I'm not gonna be so difficult with you. I'm gonna actually give you some assumptions that you can leverage if you see fit, and the assumption you can now make with the second array is that same numbers may very well be there including hopefully 50 but I spent sometime in advance sorting these numbers for you. So now, the list is sorted, the array is sorted, what is your algorithm now gonna be? >> I'm gonna--I think that's the second highest number, so I figure it could be here or there. Okay, so you're taking some liberties. So the only--actually, no you're not 'cause I said you have the same numbers. I didn't say that part. So you have some numbers here and I want you to find the number 50 and I say this because we don't wanna base this answer on this one now. So how would you now find the number 50 knowing that these numbers are sorted? What algorithm would you do? >> The same one. >> Same one. Okay, what is that same one? >> Just start at one end and move out or maybe like depending on what I get on the first time. >> Okay, good. So this is where I need to correct my own self here. If you know a little something about the numbers in advance, obviously, alright, 50 is they are sorted, right here, right. >> This is probably 50 but if we don't know what the numbers are, but we do know that they're sorted, right, we can at least strategize a little bit. Right? Recall what I did in the first day or what we did in the first day together which was if I'm looking for Mike Smith. Now, I know he is in here but I didn't start for instance here. What was my strategy then? >> You opened it in half and you saw what letter you are on. >> Okay, so let's try that approach if you would, if you don't mind my nudging you toward that approach like the phonebooks. Start roughly in the middle. It's not an odd number so we can. Okay, 124 and now, what decision can you make? >> I can move down or up. >> Alright, so you can move left or right, down or up, and which way do you wanna go? >> Down. >> And because, just be clear. >> Because the number is lower. >> Alright, so the number is lower. Right. It might be a statement of the obvious. This is what hopefully a reasonably intelligent human being would do but the visual takeaway here is that now, right, we can literally much like we threw the phonebook away the other day, we can throw half of that puzzle away because now the problem is half as big, right. So now what logic are you going to apply? >> Maybe pull that up. Choose something in middle here. >> Okay, go for it. Choose something out of the middle there. Alright, so 51, so we're closer but now notice the takeaway here. Obviously, it's not 51 because the numbers are sorted. We know it's gonna be this way and so tearing off this piece of paper was effectively like tearing off this piece of paper and so now the bytes you're taking becomes significantly larger than they could have been had you not known anything about their sorted order. So now the problem is finally getting whittled down to, ironically, what you would have guessed the first time and we've taken 3 steps to get there but what are you now gonna do? >> Pull that now. >> Alright, and so now we find that indeed the number 50 is there, we have solved this algorithm in maybe more steps than you would have had you taken your initial instinct, though I had to push you along but that does ultimately beg the question. Okay, sure that was faster, sure on day 1, I was able to churn through a thousand page phonebook in just 10 tears of the book in just 10 page flips. That's pretty powerful, certainly more than a thousand page turns but we have an assumption. In this case, Verizon sorted this thing for us, in this case the teaching fellows sorted this for us which then begs the question using these new skills, using these powers in C, how can we take in inputs whether it's numbers, whether it's a billion webpages, sort them and then search them more effectively. So a big round of applause, if we could, for our volunteer. [ Applause ] >> And we will see you on Wednesday. ==== Transcribed by Automatic Sync Technologies ====