[Section 9] [More Comfortable]
[Rob Bowden] [Harvard University]
[This is CS50.] [CS50.TV]
>> All right. Basically today it's all up to you guys to ask some questions.
I might be able to wander with some topics
for a bit if no one has any questions to ask.
Hopefully you do. Does anyone have any questions?
Maybe from past quizzes, things you're not comfortable with currently.
>> Yes. >>[Student] Can you go over buffer overflow attacks? >>[Rob] Sure.
The main example actually might be right here.
The main deal behind buffer overflow attacks are
we have some buffer, here.
Char c--which is only of size 12--
but then we are inserting something into that buffer
but not checking exactly how much we are inserting.
Here we are inserting strlen(bar) into C, but who knows how long bar is.
If it's longer than 12 characters then this is going to overflow this buffer.
Looking at this picture--
if you take 61 you'll get much more familiar with this sort of layout
and dealing with the saved frame pointer and return address and parent's routine stack
and all of these actual things.
But here you just need to know that we have
this little space for our buffer.
Here we have c(0) and then we have c, 1, 2, 3, 4, 5 and so on.
Under normal circumstances we would fill this buffer as per usual.
If we inserted 'hello' we'd have h-e-l-l-o/0,
and then just a bunch of empty space.
For a hacker--oh, I guess this is the example.
For a hacker we get something like this where
what they're specifically trying to do is
usually override the return address.
Whenever you call a function and your stack frame gets pushed onto the stack
that stack frame needs to know how--
well, the function that has been called needs to know how to return to the function that called it.
So, if main calls foo, foo needs to return to main,
and so that's what this return address does.
But what the hacker's going to do is
override it with a special return address
where again--Little Indian--it's not straightforward but each byte is backwards.
This return address as far as the computer is concerned
returning to this address is equivalent to returning to foo or main
or whatever function called it.
So it's going to return to this address
which just so happens to be this address
which either sometimes what they do here is use the return address
of a specific function that they know is already there.
I can't remember what the function's called.
I'll look it up later.
>> Here what they're doing is passing the return address
to the stack itself, and this is somewhat strange where
there are examples of memory where--
memory can be split up into read-only, read-write, and executable memory
where we have seen read-only memory before where the--
if I say char*s = hello I can't modify hello.
That's read-only memory.
There's also this idea of executable memory
where the executable memory would be the text segment of your code.
Looking at your usual address space layout--
I believe that's going to be a good picture--
this works--where we have our stack up here. We have data memory.
Ignore this basically. This is our heap.
And then we have down here our main program code.
This is similar to the place where we put our strings like char* = hello
and that's read-only.
But you could also mark this main program code as executable.
And if you are doing that or your operating system does that correctly
then this should be the only place in memory
that code can actually execute
which means that this sort of buffer overflow attack we have over here
would be ineffective because this is trying to execute memory up here in our stack.
Notice the pictures are first.
We have our stack growing up.
Here the stack is growing down.
For CS50 purposes the stack grows up.
>> It is possible to circumvent this particular type of buffer overflow
by having these executable regions of memory in non-executable regions.
But it just so happens that rarely is executable memory marked as executable.
It just tends to be read-only and re-write are the only things that are used,
so this is still very effective.
And here we could put whatever we want.
It wasn't actually done as a Pset in 61 this year,
but if you look at last year's offering of it or any previous year
one Pset is you're specifically supposed to insert in here code that is supposed to
print some specific value or return a value that is different from
the value that is supposed to be printed.
Or even more cleverly, it wants you to call or write--
so this will return up to here and then you'll execute some coding here,
and the cleverest of overflows will then return to what this return address used to be.
So even though we needed to override this
to come up here, we still remember that return address somewhere
so that we can return to main or whatever,
and it's like we never even noticed that things went wrong.
But things did so that's the case where maybe inside of here we gelbroke our iPhone.
Things go as normal--like we run some program and things end up returning to
whatever it's supposed to return to, but in the meantime
you managed to destroy the entire operating system.
You don't need to know code concerning buffer overflows or actually taking advantage of it.
You do need to know the basic ideas of this is the buffer that's being overflowed,
and this is the reason that it can be overflowed because we're not checking whether
we're actually within the bounds of it.
>> [Student] The solution for preventing it is just checking the bounds?
[Rob] Yes. In this case the solution would be
you could either say if strlen of bar is greater than 12-1--
because you need the /0 at the end--
or you could manually do a for loop that only copies the first 11 characters,
or just anything where you're actually checking to make sure you don't overflow that buffer.
>> Other questions? Yes?
[Student] Can you talk about tries and maybe something about programming (inaudible).
[Rob] Sure.
The actual program--
we would never make you do an implementation of a trie on the exam
because it would be unfair to those who did hash tables.
And similarly we would never make you implement a hash table on the exam
because it would be unfair to those who did tries.
You should nevertheless know the struct of a trie or the struct of a hash table or whatever.
That's actually true of any sort of data structure we've seen.
Linked lists, stacked skews, binary trees--
you should be able to define those structs by heart.
A trie--that means the only thing you will need to do is maybe we'll give you
some word or something and we'll say construct the trie that--
we'll give you maybe a set of words
and we're like construct a trie that represents this dictionary.
>> Let's make our dictionary cat and dog.
The idea of the trie is we start out with this array--
26 slots--
and in each slot the actual index of the slot corresponds to the letter we're concerned with.
So here, if we're trying to insert cat into our trie
the first character is 'c' which is going to be 'if a is 0 then b is 1, c is 2.'
We're going to go into the second index,
and we're going to create a trie off of that.
We're going to have 26 slots.
And then we are going to index the second character of cat.
That's 'a' which is going to be the 0 spot.
And that's going to have 26 spots.
Then we go to 't' and we would also have that coming down which is actually kind of important
because--let's have it come up here. Here's our trie for 't'.
Let's say this is index 't' is 19.
The important thing to remember about tries is you can't just keep track of these pointers.
You also have to keep track of whether this is actually the end of a word.
So, inside of here we need some kind of flag that says
okay, this is actually the end of a word.
The reason being if we later try to insert catastrophic into our dictionary
which has the same starting 3 characters
but goes on further we need to recognize that this is the end of a word.
Or alternatively if we try to look up 'ca' which maybe isn't a word
but we get down to here then we--
or would it be c and then we look at a--
we need to recognize that even though there's a pointer coming out of this node
it doesn't represent the end of the word.
>> So, what does that mean--what were you going to say?
What does that mean our struct looks like?
[Student] It's an array of pointers that is 26 long and then a bool were or not were.
[Rob] Yeah. So, we'll have a struct trie* pointers--here we'll say [26] on
and then the semicolon over here.
But on the Pset, we also need to account for apostrophes,
which meant you needed to hard-code that apostrophe with index 27 or something.
But here we only care about 26.
And then we need maybe a char in or bool--let's call it is word.
That's 2 of the 3 things I think you would ever need to know about tries--
building them, the struct of them, and the last thing is the run-time of them.
>> What is the runtime of a trie--or the lookup in a trie?
This is where we say it's o(k) where k is the length of the word we happen to be looking up;
but at the same time we say--at least for Pset 5 speller's sake--we say
the longest word in the dictionary is 45 characters, so this is basically
the O of 45 which is constant time.
So, if there is an upper bound on your longest word then--
or even like the English dictionary--there is an upper bound on your longest word.
Or any dictionary--there is a longest bound on your upper word.
No matter what you're doing is constant time,
but O of k is nice because there actually is a difference between running say
45-character word versus an alphabet which only has words up to 3 characters.
Another thing about that is that the--
oh, because just saying that 45 happens to be our longest word
is kind of silly because at the same time let's say an algorithm is O of N.
Well okay, because memory only supports up to 2^32 bytes,
then N is at most 4 billion and that's constant time, which is why at some point
it's silly to say this sort of thing where there's an upper bound
that we can just reduce to constant time because everything is constant time
when you think of it in that way.
But we would probably accept both of these.
In any case explain either that O(1) means you have an upper-bounded length of word;
O(k) means your length of the word--
well, k means length of the word.
>> Yeah. >>[Student] Does the bool--because when you made your trie
it seemed like it was--you would go c-a-t and then you go to the next pointer
and then you tell if that equals true--would you put that true at like with the t?
[Rob] Let's think this is the case where a lot of examples you can just try and come up with
simple and/or extreme examples and what it should be, so let's think of the word 'a'.
In our original trie--
would we want to put a 1 here, or we'd want to put a 1 down here.
I would say that in the end it would probably be either/or.
I can't think of a reason--or really you wouldn't--
the reason I wouldn't put it down there is because you don't even need to go that far.
We never need to allocate this trie.
We just put the 1 up there.
This is still pointing to NULL.
If we're only going to have single characters
there's no reason to extend down to another trie just to mark that letter as used.
Similarly, if we had put the 'a' down there
then necessarily all of these would just be 0 at all times.
>> [Student] But don't we need a starting trie that will point to this 'a'?
[Rob] We have some global or something struct trie* t
which points here, but that's just a pointer.
It's not a full-blown trie that's pointing to it.
[Student] Okay. How would we assign the letter 'i'--with the word I?
[Rob] His question might be answering that. Hold on.
That is an issue where a trie in and of itself--
I don't know the way the Pset would have written it.
The previous struct was bad.
But we could also do struct node is a bool--and a pointer--
there's actually multiple ways you could write it.
Alternatively a trie doesn't need to be a struct.
It could even be trie--typedef node*--
node [26] is a trie; and this is no longer struct.
Now there's going to be--I'm trying to think of the way that Pset would have expected you to.
[Student] I pulled up that review session and I think they just go--
like if you have an a then you go to the next-- >>[Rob] That's how they do it?
[Student] And then if there's a true there it doesn't work--
[Rob] Yeah. That does work. It wastes the space of--
you necessarily have a whole other level of trie that you wouldn't need in the first place.
Here it's getting ugly with each--
basically what I'm trying to do here is associate--
instead of being 26 pointers to your tries,
it's 26 bool pointer, bool pointer, bool pointer, and so on.
>> [Student] You can't make that 2 arrays? An array of bools and an array of pointers?
[Rob] You could but then you'd need to--
2 arrays of booleans and pointers.
You would need to then build your array of booleans--
your array of booleans needs to be as big as the trie
because you can't just have 26 booleans.
It has to grow with each possible--
like your trie has more than 26 true or false possible words.
At that point they may as well just be a single struct that your trie grows down with.
This doesn't seem right because--what do I want here?
So, trie* t--
can you do typedef (node*)[26] trie;
that might be the syntax I'm looking for.
And this should just be a regular trie.
I'm not sure.
But that is the way we did it in the review, so that works perfectly fine, too.
In which case if it is just bool is word and then an array of 26
then you do have to go to the next level.
I'll think about the way I would do that.
>> Other questions?
[Student] Can I ask questions about something else? >>[Rob] Yes.
[Student] Can you go over what the difference is and when you'd use jQuery versus Ajax?
[Rob] They are in and of themselves completely different.
JQuery does enable Ajax. It does give us some easier use of Ajax.
But Ajax comes shipped with JavaScript. JavaScript has Ajax capabilities.
All Ajax means is liken I'm already on a page and when I want to--
when I click on something I don't need to reload the page to download that new information.
I just request that new information.
You can look at it in Facebook or something.
Inspect network.
Shrink this.
Down here we see that we're getting all these requests.
Now when I click on--well, it's doing Ajax before I even click on anything.
But if I click on this, then it's going to make a bunch of requests down here
which just making these requests--oh, now it's over here.
Let's refresh.
Do this again.
We see that we get all these requests, but this could still be in the process of the page loading.
Notice Facebook is making these constant requests even after the page has loaded.
And if I click on here, it'll make some more requests for some data
that is in response to the thing I just clicked on.
That's just what Ajax is. It lets you pull for data that wasn't downloaded with the page originally.
>> JQuery is separate. JQuery is just a JavaScript library that makes a lot of things easier.
With jQuery it's a lot of the advantage is this just--
dollar sign--dollar sign is a valid variable in JavaScript.
So, jQuery--all it's doing is saying like var$= a whole bunch of stuff--
like some big function with all this stuff in it--
and then you use that dollar sign in ways like
$("#footer").style ("text-align", "center").
JQuery gives us this sort of syntax where a big advantage--
it has other features but what we want you to focus on most
is just being able to select elements like this.
In regular, plain-old JavaScript you can do things like
document-dot-get element by ID footer-dot--I don't know what it is at that point--
something about CSS or style or something--
but then alternatively, let's say we wanted to select by class.
Now we are styling everything with a class footer with this style.
Even if we wanted to style any paragraphs.
So, this selector--being able to select things in the dom like this is incredibly convenient
since in plain old JavaScript you would have to do document-dot-get elements by class name
or whatever it is; or if I wanted a tag I'd need to say get elements by tag name.
So, I need to know the specific ways that I access all of these things.
The functions are going to be different depending on whether I'm using a class or an ID
or a tag or what, whereas jQuery just does that for me.
>> [Student] Is jQuery going to be used when you're doing initial styling of the page?
Or in order to change the styling after it's already-- >>[Rob] To change it.
[Student] After it's already loaded. >>[Rob] Yeah.
Any initial styling--well, even the--
generally you would use this sort of change.
You wouldn't change--this would work perfectly fine.
But usually you wouldn't change the style like this.
Instead, you'd give it a new class or something
whereas the CSS has already been defined for that class in a certain way.
By giving these items I'm selecting a new class
I'm applying the styles that have already been downloaded.
[Student] So you select a couple of checkboxes and the things that you've selected
change to a new style and start looking different. >>[Rob] Yeah.
The other things to remember about--
well, there are several functions you should remember about jQuery.
Let's say that we are selecting something with ID P.
>> [Student] Do you always have to use the pound?
[Rob] This means ID. It's equivalent to CSS, so CSS selectors--it's inspired by that.
Where in CSS if I wanted to style a footer--
or something with ID footer--
it would be like text-align: center;
you won't need to write CSS on the exam, but you need to know the selectors.
You need to know what--you need to know how to read it.
But we would never--
you don't need to memorize all of the different possible styling things. Or any of them.
>> JQuery things you should remember--
you should remember dot-HTML, and a common pattern in jQuery--let's re-write this.
A common pattern is we have $("#f").html
If I put just plain parentheses that means get the HTML;
whereas if I say HTML and put whatever I want in here--some link to something--
putting something inside of the parentheses now sets the HTML.
That's pretty common amongst a bunch of functions.
There's the same deal with text.
The difference between HTML and text is that text is going to insert this
as literal less-than a, greater-than instead of as an anchor tag.
And text is going to be the same if I just do this.
It's going to retrieve the text of the document--not the HTML of the document
but just the text within this element.
Another one is if 'f' happens to be an ID for an input,
then hash-f-dot-val--if I want to set the input to something like--
let's say I hit a checkbox and I want to set a default value--
dot-val--I don't even know--3--so that will automatically insert into the text box 3,
but if I say 3-dot-val, that will retrieve whatever is currently in the text box for me.
>> This is useful for form validation where
if I just want to make sure that they actually filled out all of the things.
One way of doing that is if after I hit submit it's inevitably sent to some page on the server--
like for us it would be PHP--and that would try to process the data and it would say
they didn't fill something out, so that now redirects them to another page that says
you didn't fill everything out.
Instead of having to do that, in JavaScript/jQuery you can just see if val is empty.
Or is val--empty quotes.
That's going to just--now we can alert them that you didn't fill out this field.
Inevitably you do need to do the PHP server-side checking because
you can just disable JavaScript in all the browsers.
But JavaScript makes it convenient for those who do have it activated,
and virtually ninety-nine-point-something percent of browsers have it on nowadays.
Very few people turn JavaScript off.
It is a user convenience. You need to do PHP validation.
You should do JavaScript validation.
>> [Student] What does #f refer to here?
[Rob] What does #f refer to?
There is some element in my document with ID 'f'.
We'll look at--probably Facebook has plenty of examples where if I come to elements
looking here under the elements tag I see this particular div that's being highlighted up here--
or is it the whole page--yeah, it's up there. This has ID pagelet_bluebar.
In console I assume they're using jQuery.
So, I could select pagelet_bluebar so that selects that, and I did something wrong.
Let's try--or maybe they aren't using jQuery and that character's mapped to something else.
A better example in something I know is using jQuery--
still looking at our elements here--we have here class equals navbar.
This is something with class navbar,
so inside of our console we can look up the thing with class navbar.
Here we can scroll over this and see that's what this is.
If I wanted to do .text this is the text of that, so I see settings for report above log out
which are all under here, but that's still text within that HTML tag.
I could set the HTML to just some link,
so I'll get rid of my bar. Now that got rid of the header entirely just so it's linked to YouTube.
>> And is there any form example?
Here's a form.
I can right-click and inspect element to come to it right here.
I see that its ID is text search,
so down here if I do ID text search.
I'll bring over it and I see that is the correct thing I was searching for.
If I want to do .val it would give me what I had typed there.
If I wanted to do hello it'll change it up here to hello--jQuery.
Of course I could do ridiculous like document.get element by ID--text search--
I don't even know what it is at this point--dot value--no, I forgot that guy.
So, that's hello. I don't know how I'd set it equals something.
Yeah, so that changed that.
But you don't need to use these and very many websites at this point use jQuery.
Even like on a final project--if you're doing a web project--the first thing
I recommend is just including jQuery so you can get the convenience of all these functions.
>> [Student] I think I saw a different way to get to a element using dom.
Do you have to use dot and then keep going down?
[Rob] You can do that. I don't know if it would work very well.
It's difficult to navigate that way.
One example is--I don't even know if we have any forms--
but document.forms is going to return the list of forms that's on this page,
then I can do document.forms 0 is going to be the first form.
Dot--I don't know what we've called that--so it doesn't even have a name,
so maybe inputs will work. No.
I don't even know how to get at this--get element-I-tag name input.
Yeah, that gave me the input, and now I want the 0 to input
and I want to select its value, so that's going to be text.
I had to end up doing get elements by tag name anyway.
There might be some way to select it directly
through form 0, but the nice thing about this is still like I only had to get the tags called input
that were a child of this form; otherwise if I just do that straight up front
this would select all elements on the entire page, in the entire document
instead of just that form and it probably won't even be the one I want.
I don't even know which one it is. I don't know.
I guess the first input element on our page is this little checkbox.
>> [Student] This is pretty unrelated
and possibly kind of silly, but on the answer key it says that PHP--
I don't know whether it's the answer key or notes but it says PHP is server-side
and JavaScript is client-side. What is the difference between the 2?
[Rob] The difference between JavaScript client-side and PHP server-side.
If you have heard of slash/used node js before you would think that
JavaScript isn't just client-side but for CS50 purposes it is--
or at least for this quiz's purposes it is.
PHP being server-side. No JavaScript.
When you write your webpage you will be writing PHP on the server.
You will never be writing JavaScript on the server.
JavaScript ends up getting sent to the browser where the JavaScript code executes.
And the JavaScript code needs to live in the browser because otherwise when I want to
just do any sort of JavaScript-y thing like clicking on this,
I'm not reloading a page. This is just JavaScript re-formatting things for me.
If JavaScript lived on the server, then I would need to inevitably request something
of the server to know what to do.
PHP--there is no such thing as PHP in the browser.
When I request a page--so let's say here I requested this particular page.
That means that this is going to request--
refresh--it's going to refresh this page--
so this request goes out to our server.
It sees that it needs to return this particular thread with this particular ID,
so now that's going to be some PHP that the PHP interpreter is going to interpret that page
and transform it into just HTML, CSS, maybe JavaScript, whatever.
It's PHP that processes this request and retrieves all of the text and stuff
that I'm actually looking for from the database.
But what leaves the server is just HTML/JS/CSS.
There's no PHP which leaves the server because if it actually did
then the browser would have no idea what to do with it because it doesn't know what PHP is.
But in the same thought because JavaScript is client-side,
you can never access MySQL from it.
Because PHP is server-side you do access MySQL from it.
>> [Student] Can you go over some of the security concerns with cookies in HTTP?
[Rob] Those are not things we're going to need to know.
Some of the security concerns with cookies in HTTP.
The big question here is we see here that my cookie is PHP/ID.
That's like the universal PHP your session.
Your session is something that inside of PHP will never need to be validated
because it's the server that has complete control over the session.
You can't touch it at all.
But it's this cookie--this one--
and I guess you could log in as me right now if you wanted to use that--
but it's that cookie that the--inevitably you make a single request to the server.
The server returns the page. The request is done.
It no longer has any idea who you are.
So, the next request you make is going to include that cookie so that it knows
this is the person who made this request before.
This is the session data that is associated with this user.
That's why you don't have to log in for each and every page you use.
The security issue here is that that cookie is sent out over the web.
We're using HTTPS here, so in this case that means that we are encrypting this stuff.
Someone can't come in and just steal my cookie and now the server will think they're me.
But with straight HTTP they can.
Just like this WireShark/FireSheep stuff that you can just listen to all of the wi-fis in the air
and intercept whatever you want, so yeah.
>> [Student] A sort of similar security risk is storing user ID's in post
because that can be freely edited using consoles and things.
[Rob] Yes. There's plenty of issues where like just anything that comes from the user
you need to validate.
There are plenty of cases where it would be useful for like I'm about to make a post.
Blah, blah, blah, blah, blah. Then I hit reply.
It would be very useful if the post request included my ID because
I want to associate this post with me.
But I can't do that because I am free to make a post request--just like manually
come up with my own post request--
that uses your user ID and now it will post as you.
That's why server-side I can't rely on post requests containing the correct user ID.
That's why it has to belong in my session.
So I look up your user ID in my session array and I insert that into my database
as the user who actually made this post.
[Student] And that's based on your cookie?
[Rob] Yeah. It uses the cookie to match up you as the user who made that request.
It pulls out the user ID from that session and that then inserts into the database
using that user ID.
This like button--what that's actually doing is--
I'm not going to find it here. It's going to be an Ajax function
What is Ajax function?
Let me find out what my JavaScript is.
It was a CS50 project a while ago.
I can't remember what it is.
Ajax function--all Ajax function is doing is making an Ajax request to a page with this ID--
with the ID 22453.
It's not even a post request. It's a get request which makes it even easier.
If I knew what the URL is--it's something like like this/ID=22453--
or ?ID=22453--
so visiting this URL will like that.
Which wouldn't be as much of a problem but it's incredibly easy to write a loop
which is just going to visit this URL over and over again, which is why you see
Isawyouharvard post with thousands of things.
And they tend to be CS50-based Isawyouharvard posts.
How do I find the most-liked?
They tend to get deleted pretty quickly, too.
This is not the most-liked. There we go.
Cheaters on the most liked page--that's pretty relevant to this right now.
Oh wow. They've already deleted any of the ones from this year which have been
cheated on. Those have all been deleted.
There will never be a post that gets this high.
This one was obviously cheated on to get on to the most liked page.
>> More questions?
[Student] What should we know about XHTML?
[Rob] Virtually nothing. Just what it is.
The difference between it and HTML being that XML is very similar in appearance
to HTML except in HTML we just have to have a predefined set of tags.
But with XML--XML is just like a general format where you can make an XML document
for whatever purposes you want.
So, for example, if I wanted I could construct an XML for the courses--
and I actually think that CS50 has an API for this.
My XML document could look something like--
courses and of course I need some end courses.
I could have a course and it could have name equals CS50.
And then my end course and I could put inside of here students,
and then inside of students I have a list of one student whose name is whatever.
I end that student and so on.
I just happen to have constructed some arbitrary XML document, but it is valid XML.
XML--all it is is this sort of structure and the nice thing--the reason that we even call it XML
is that this sort of thing is very easy to parse.
It's very easy to take this document and make an array out of it.
And so XHTML is an attempt to get HTML to be valid XML.
Already this looks pretty similar to HTML.
Some of the differences are HTML you are able to do things like input maybe type equals text
which is the default so I don't need to say that.
Disabled.
>> There are 2 things in here that make this invalid XHTML.
The first thing is that all XML tags need a closing tag.
So in the case of input I need to do the--which direction of slash is it?
This direction? That looks wrong.
Other direction.
Self-closing tag.
The second thing is that with XML you need these sorts of like key value pairs.
It needs a value associated with it.
So, even though disabled in and of itself expresses what I want--
this input should be disabled--
that's invalid XHTML.
What I actually need to write is disabled equals disabled.
Now it's valid XHTML.
And these are just these slight differences that transform HTML to an XML-based sort of thing.
>> [Student] XML is about like pull through your own X altogether like why is it (inaudible)
[Rob] The thing of like a CSV--a CSV you have just values separated by--
just think of a spreadsheet. A CSV is basically a spreadsheet.
You have maybe columns and you have a bunch of rows that
associate data with those columns but that's it.
XML is much more versatile in that you can--you have an arbitrary hierarchy of data.
I could have multiple courses that have multiple students within it
where it would be difficult to think of a spreadsheet that--
just that single spreadsheet--CSV especially is like just a single spreadsheet--
so that single spreadsheet having all CS50, 51, and 61 and within those all of the
students related to those times, maybe meeting times and all of that sort of thing.
The other thing is that the tag names give a nice name to all of the elements
so reading a CSV file can be difficult to try and parse what it's actually seeing.
XML is much more human-readable so that's why like--come up to some person who doesn't
really know what a CSV file is or like isn't a programmer or something--
you can give them like a template XML file and they can follow the lines and--
oh, I'm supposed to insert my name here.
It's a much more usable format.
CSV has plenty of uses but XML has different uses.
>> More questions?
Other questions?
[Student] From the previous quiz--vertical scaling versus horizontal scaling.
[Rob] You would not need to know that. I don't think we even discussed that.
I'm guessing it was just a one-off comment.
Oh. Horizontal versus vertical scaling is not something you'll need to know.
I think the difference is just like--oh well, the answer key will say the difference.
Vertical scaling is just like oh, my computer's doing poorly. I'll get a better one.
Whereas horizontal scaling is oh, my computer is doing poorly--
let me get 20 of them to all work on the same task.
>> [Student] Can we go over the linked list way of making queues. >>[Rob] Sure.
That's easier than the array way.
The linked list way of making queues.
First, what does our struct for a linked list look like?
[Student] Are we doing it for-- >>[Rob] Let's do its--yeah.
Int val; then struct node* next;
so that's what we'll use for the example here.
Let's actually type up this stuff.
Let's do linked_list.
Our struct--
Okay. Now looking at our queue we have the--
let's just make a global queue.
It'll be node* queue; and we have a dequeue function.
I guess these things could also overturn true or false--let's do that.
Bool dequeue--and we're dequeueing--oh. Hmm.
Int dequeue--what did we do with this before?
Int dequeue and we have bool enqueue and we need to enqueue some means true.
Let's do enqueue first.
We have our queue. We want to insert something into the queue.
What is the best way to do that?
Over here our queue currently looks like we have some global pointer to start.
There's our queue.
Assuming that we dequeue by taking the first element,
where are we going to want to insert our node so that queues work as they should?
[Student] At the very end. >>[Rob] Yeah. Queues are supposed to be first in, first out.
Which means that the new element should be inserted over here. Okay.
>> Coming back to code,
that means that we will want to loop over our queue.
Let's do node* current = queue; while current does not equal NULL.
I would do--all right, let's do it separately.
First, current = queue.
What do we do if current starts off as NULL?
We'll do this 2 ways. First this way.
What do we do if current is NULL?
Is this equivalent to if queue is NULL?
[Student] It's going to return false. >>[Rob] Should we return false?
What's wrong with inserting something into an empty list?
[Student] Nothing is wrong with that. Sorry.
[Rob] Yeah. So here the only difference is my global queue is being sent to my new node.
And then I have to do my checks of if queue is NULL.
Return false.
And then queue val equals i; queue next equals NULL; return true.
Okay. I'm going to jump the gun right here.
Remember what we did that last time
where we said it was much easier to work with node** with this sort of thing.
So now current is going to be &queue, and coming down to here--
while current--while *current does not equal NULL--
so let me just do current--we'll talk about this in a second.
Current next. Okay.
Looking at it in this way, this is iterating over all of my pointers until I reach a null pointer.
The null pointer is going to be the pointer I want to replace with my new node.
Looking at iPad version--
if my original pointer and the linked list is empty then current is going to point here.
This is going to point to null,
so this is the pointer I end up moving to point to some other new node.
Whereas if the example is this case up here
then current is going to traverse from here--I messed up slightly.
Where current is supposed to be the address of current next.
Is that what I want? Current so *current gives me a node.
Next traverses to the next one.
I'm currently pointing here.
Let's do red--so I'm currently pointing here.
Then *current is going to reference this node.
And *current next references this node, but that's not what I want.
I want this pointer to that node.
So, that pointer to this node is ampersand (*current) next.
>> At this point in time I've officially reached the node that I want to replace.
Let's replace all of these queues current--and now we're done.
There may be typos, but the idea is that with insert in this sort of way
it is easier to work with the pointers that we want to change
instead of needing to keep track of--okay, is my start NULL?
Oh it is? Then I need to create the start node to be something specific
else I'll want to iterate until the next thing I point to is NULL,
and then I'll replace that--what the next thing is--to my malloc node.
Instead of needing to separate those cases, here I only deal with the case of
what is the pointer that is NULL that I no longer want to be NULL,
and that makes life easier except these should all be *current now because--
[Student] Are they still the size of a node?
[Rob] Yes. I'm still mallocing a node.
[Student] Is it going to be the size of a node*?
[Rob] Coming back to here, think of the case if this is our linked list.
This guy points off to NULL.
After that why loop, current points to here
because this is the pointer that is NULL.
Now I want to change this pointer to point to a new node.
First I malloc that new node--so malloc size of node.
And that returns a node* and now changing this pointer is building to *current equals
this new node that I allocated.
So, if current is a node**, then *current is going to be a node*,
and if I'm mallocing something the size of node then this is returning a pointer to a node
so this is a node*--so both sides correctly have the same type.
And so if what I just allocated was NULL, return false;
else finish setting them to what I want them to be--except these need parentheses
because that's not how the order of things work.
Without the parentheses that was being interpreted as
current-arrow-val dereference that.
Instead I want to dereference current which brings me to a node.
Then I want to get the value associated with that node.
>> [Student] I thought arrows allowed you to bypass that and go straight to the value.
[Rob] They do. That's if I have--let's say queue is an example.
I'm allowed to do queue-arrow-val equals i because queue is a node*.
If there were some nice syntax of like current-longer arrow-val or something
which did 2 dereferences, then this would work well.
[Student] So the arrow is only for 1 dereference. >>[Rob] Yeah.
Alternatively I could write this as (**current.val).
Just like I could also write queue as (*queue).val.
So let's insert. Well, that's in queue I guess.
Dequeue is going to be significantly shorter.
Let's put void in here for cleanliness.
So, dequeue. What element am I dequeueing?
[Student] The first one? >>[Rob] Yeah.
If my first one is NULL--return--I don't know what we want to return--INT_MAX;
and then you should do a check to see if INT_MAX was returned.
That's the sort of thing that get inc does else we want to--
can we just return queue val? Is that what we want to do?
Dequeue also implicitly removes the item from the queue,
so let's first say--let's get a tmp to point to the first node of our queue.
Now we want to advance our queue to point to the next thing in the queue.
Now we have tmp left. Tmp val is the thing we want to return.
So, val = tmp->val;
but before we return it we should free tmp and return val.
The order of operations here is important in that we need to grab a tmp
before we move queue to the next element.
We need to get the value before we free tmp,
and then we can return the val.
>> [Student] Should we set the queue to queue next?
[Rob] Yes. That was creating a bad loop/it wouldn't work after freeing it anyway.
Queue = queue->next.
We want to advance the queue into the next element not advance the next element
to what the element currently is.
Stacks would be significantly--like even easier in that dequeue is exactly the same
because we're pulling off the front of the stack.
End queue would be very similar where we just want to allocate a node
and insert into the front of the stack, so we don't even need to loop over anything.
We just insert directly at the front.
Is everyone good on that?
>> Okay. More questions?
[Student] What major things should I keep in mind from the most recent lecture?
[Rob] The most recent lecture.
You do not need to know any code.
You should know the overarching ideas.
Nate's half didn't have any code and so those slides are online.
They're just like look at them and they have the major ideas.
My half--knowing the overall idea of first you can't trust anything.
The fact that like maybe the process of the compiler can be bad,
but it doesn't even matter that the source code looks fine.
Because the compiler might be specifically altered to change the source code
in the process of compiling.
At the same time just like--I think those are like the major ideas of it.
>> [Student] Did you mention that we don't need to know anything related to Firesheep--
or do we need to know that?
[Rob] With Nate's half of things, anything that Nate touched on--
like FireSheep, WireShark--I don't even think he did Firesheep in detail.
You also did something with that--was it Firesheep--last week?
Did you touch on that?
[Student] Yeah, I think we might have-- >>[Rob] Yeah.
We're not going to give you Firesheep output and say interpret this.
It's just going to be--it would be a question like what is Firesheep?
What is it used for?
[Student] I think it only works on version 4 of Firefox or something.
[Rob] It might be broken by now.
I have no idea.
They don't seem to have disabled it manually,
but maybe it doesn't work with the most recent Firefox.
[Student] I actually tried installing it because it said it would be compatible.
[Rob] So, I guess it doesn't work with the most recent Firefox.
But the idea still stands of what it was meant to show.
It was absurd how much of the world was not living in HTTPS at the time.
Even in the last 2 years or whatever, it's still--there's dramatic improvement in the
number of websites which use HTTPS.
>> [Student] Do we need to go over HTTP?
[Rob] The protocol of it? >>[Student] Some of the things that we should know.
[Rob] All right. Basic things are everything you can see in your network tab.
When I request a page--coming back up to the top for the main things.
You can see here the request that I make.
Chrome happens to format it all nicely for us
where the request URL was this, the request method was GET,
and the status code was 200 OK.
If I hit view source, I see more directly that--
and this is--we could show you either of these, but it isn't too difficult to interpret between them.
Here is the direct request I made, so this means that I went to
apps.cs50.net/discuss/threads/inbox/all/HTTP/1.1.
And the protocol it used was HTTP/1.1 which is virtually--it's always going to be that.
Over here we used GET, so this might also be POST.
And then coming down--all the way down to response headers--if we view that source,
it's where we see the 200 OK.
Know the possible different status codes of these.
I think in the review we do say a couple of these,
so 403, 404--those kind of common ones.
That's the major idea of it.
The difference just between HTTP and HTTPS is this encryption.
>> [Student] Are you done? >>[Rob] I think so. Well, yep.
[Student] Will you talk very generally about how encryption works?
Because we talked for example when compressing Huffman files,
you know how to decompress them because you actually sent the hashtable within the file
so how does encryption work?
How do you know how to encrypt information if you haven't actually sent the client
the key to the--and you can actually grab that key from--?
How does the general process work?
[Rob] The general process of encryption--
that is an incredibly detailed question I will answer.
There is a short--well, Tommy and I made the short.
Unfortunately it is like 26 minutes, so it is not a short. It is a long.
But our short was on RSA which is just one example of these,
and this RSA is part of the overall HTTPS protocol.
The idea--RSA is an example of public key cryptography,
which means you have 2 separate keys.
You use 1 key to actually encrypt things,
and you use another key to decrypt things.
This key that you use to encrypt things is the one that's public.
The website can send you this encryption key.
They do send you that encryption key, and when you want to send something back to them
you use that encryption key to encrypt all of your data and send it to them.
So, they are the only ones with the private key.
If that private key became known then anyone would be able to decrypt your data.
But that private key--which is mathematically related to the public key but you cannot
figure one out from the other--so that private key can be used to decrypt the data.
Since they are the only ones with the private key,
they're the only ones who can read the data.
So even though the public key is public,
I use the same--when I go to Google.com or whatever,
they might have multiple, I don't know--but if I go to Google.com,
he goes to Google.com, she goes to Google.com--
we all can use the same public key to encrypt our own information however we want.
But none of us are going to be able to figure out--are going to be able to decrypt
to their information because the public key isn't able to decrypt.
It can only encrypt.
And it's fun/detailed math of--like a bunch of module operators and exponentials and stuff,
that it just works out that the private key is the only thing that can
decrypt the public key's encryption stuff.
Yeah. See the RSA short for more details.
[Student] Is that on the website?
[Rob] Yeah, I think it is at this point. Or at least a YouTube link to it was posted.
Let's see. Shorts. I think it would have been week 2-related. Yeah. RSA.
And it is--we're not going to play this--24 minutes.
It's a long one.
>> More questions?
[Student] Could you talk briefly about the bitmasks? >>[Rob] Sure.
Briefly, the idea is just that like-- >>[Student] What is it, Rob?
[Rob] Bitmasks. The idea is--let's just say we have some--we're using some integer--
int x--so, we start it off at 0.
Now, this integer is 32 bits, so any single 1 of those bits can be used to represent
a specific FLAC.
This is where if you look at operating system codes, they use this all over the place
where maybe up top somewhere they hash-define--
Let's see some examples.
Man-2-open--the open-system call we can see here that one of its arguments is int flags--
what it expects as that argument are some of these flags.
We see O_append, O_ASYNC, O_CLOEXEC,
O_CREAT, and so on.
O_DIRECT. These sorts of flags are hash-defined somewhere.
And all of them are exactly 1 bit.
So, O_CREAT might be hash-defined as 1, left-shift, 4 (1<<4).
That's going to be the--whenever I use O_CREAT that's just going to be--
in binary 1, 0, 0, 0, and 30-ish zeros before it.
It's only a single bit a set, and that bit represents this flag.
And so no other flag is going to be left-shifted by 4.
I'm able to represent up to 32 flags in a single integer by doing--
x = O_CREAT bit wise or O_DIRECT.
You're just picking any 2 of those flags.
Now x is going to have 2 bits set which correspond to the 2 bits
of O_CREAT and O_DIRECT.
The way that then--so then we passed x into the open function,
and open needs to see what flags were actually set.
So, that's where it's going to do things like
if (x & O_CREAT) do something,
or if ( x & O_DIRECT) do something else,
and then there may be some flag that we didn't have set--
if (x & O_--I don't know what the other flags were--
(x & O_RDONLY)--that particular condition is not going to be executed.
Or that block of code is not going to be executed,
but these 2 are because those 2 flags were set.
And notice that in C, any value that is not 0 is true.
So, (x & O_CREAT) will be either 0 or O_CREAT
because O_CREAT only has a single bit set.
If that bit is set next, then this is going to return O_CREAT--
the binary where just that bit is set.
If that bit next is not set, then it's going to return 0, in which case we know the flag was not set.
That's how you use bitmasks.
I think on a previous exam or maybe in class or something--
you can also use bitmasks to print out the binary of a variable.
So I can use--looping over--1, left-shift, 0--and then print if x & that--
if x & 1, left shift, 0--then print a 0 or 1. Or print a 1 else print a 0.
And then I go over once more--if x & 1, left-shift, 2--then that means that the second bit
of the variable is set, so I print a 1 else I print a 0.
And I think we might actually want to do that in the reverse order because
usually you want the left side to be the highest-order bits
and the right side to be the lowest-order bits, so it would probably loop 4 int i = 31 until I hit 0,
then do that exact condition--if x & 1, left-shift, i; print 1 else 0.
[Student] Thank you.
>> [Rob] I think we're out of time.
Any more questions in the last couple of out-of-time seconds?
All right. Good luck tomorrow.
This was the last section where next week's going to be optional.
I'll give back quizzes and we can go over them and maybe go over other things that
you were interested in, or final project things, or future CS classes things or--I don't know.
But this is the last material-filled section.
Bye!
(applause)
>> [CS50.TV]