[ 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.
>> 2.
>> 3.
>> 4.
>> 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.