>> jason hirschhorn: welcome,everyone, to week 10. this is an exciting week becausetomorrow is quiz 1, which we will get to in a second. today in section, we are going to goover some resources for the quiz, and then i will answer any and allquestions you guys have. and we will finally end withsome practice problems. >> we can spend the entire sectionanswering questions. we can spend the entire sectiongoing over practice problems. we will just expand to fill thespace and time we have.
>> so i put this list up every week, butit's particularly important this week. for studying, if you haven'tstarted already, oh boy. but hopefully you've started already. and you are going through the materialsand resources listed here. i would highly recommenda number of these. >> in particular, lecture notes areincredibly important and helpful. the study.cs50.net providesa great primer on a lot of the topics we covered. it also has some greatpractice problems.
and then, google is great, too. i don't know what you'd use it for. but use google, as well. >> reach out to me if you have anyquestions, comments, or concerns. look over the review sessionslides from last night. or, if you have some time,watch the video. they provide a lot of helpfulmaterial and information. and try and cover if not all, many ofthe topics we've covered and that you might see on the quiz.
>> speaking of the quiz, thatwill be tomorrow. it's 75 minutes long. many of you are taking it at 1o'clock, and some of you are taking it at 5:30. for the time you're taking it and thelocation you're taking it, make sure you check out the documenton the cs50.net homepage. >> remember that you can get one 8 1/2by 11 sheet to take with you. oftentimes, people don't use thissheet at all during the quiz. but really, it is an incrediblyhelpful study tool.
so putting together that sheet is whati spent probably three or four hours doing when i was studying for cs50, andthat was easily the most helpful way i could study for the quiz. so even if you have some other people'sstudy guides to look at and use as references, i highly recommendmaking your own study guide, putting that stuff together. that really helps you learnall of the material. >> last but not least in this section,after the quiz tomorrow there's one more lecture--
next monday. there's one more section, not nexttuesday before thanksgiving, but the tuesday after that. we'll be meeting together for a finalgoodbye party and also doing some cool things to get you guys excited aboutfurther studies in computer science. >> there's one more project, one morefair, one more hackathon. we're nearing the end of cs50,which is exciting-- but also, if you're likeme, a little sad. before i move on, does anyone haveany questions about what
we've covered so far? >> ok, well let's go over some questionsthat you have for the quiz and topics we might cover. so this is a list that i put together. it is by no means exhaustive, buthopefully will jog your memory if you have some questions about any of thesetopics, or if you have questions about practice problems from quizzesin years past. >> i had a couple questions that wereemailed to me, but i want to hold off on those for a second.
does anybody have any questions,problems they didn't understand, answers they didn't understandto get us started? avi. >> audience: can you just go overdom and ajax really quick? like, what we need to know or shouldunderstand about them? >> jason hirschhorn: i'm going to answergenerally this question of, what do i need to know about given topic x? because i have a feeling many of youare going to ask me that, or are curious about that.
so to the extent that the topic wascovered in lecture, or section, or on study.cs50.net, a problem set, youshould be familiar with it. >> so you don't need to know every typeof tag that's available in html or every type of attribute or propertyyou can give something in css. but if you saw it in a lecture example,if you saw it in a problem set, you should probably be familiarwith it, particularly things you saw in lecture. so we discussed the documentobject model a bit in section, more so in lecture.
you should be familiarwith that much of it. >> and you should be familiar withajax to the same extent. we never saw incredibly advanced orcomplicated examples of ajax, so you're not going to be asked dosomething incredibly complicated. but you might be asked, how do imake an ajax call using jquery? which is something you've seen a numberof times before, both in the review session and in lecture, andit's only two-ish lines of code. >> so that is something you shouldbe familiar with. but again, for all these topics,if you've seen it
before, it is fair game. and we might ask you-- obviously, we'regoing to ask you things you haven't seen before. coding something you haven'tseen before. which isn't to say you haven'tseen the tools to solve that problem before. you have seen those tools. >> for example, on quiz 1, ifyou need to code strlen. we haven't coded strlen before.
but you know how to use a for loop,you know how to use if conditions. you know how to write variables in c.it's going to be the same thing here. you're not going to be asked to doanything you haven't seen before, but you might be asked to, like, putsomething together in a novel way, or solve a different type of problem. >> sorry, that wasn't specific to yourquestion, but i can't answer about every single topic what youdo or do not need to know. but also, sorry, last thing on that. we have spent significantly more timeon link lists than we have on ajax.
you didn't use ajax in a problem set. one of the central features of thatproblem set that was link lists. and we spent a lot of time in lectureand section using it. >> so, odds are link list will come up moreoften on the quiz than ajax will. or the questions having to do with linklist will be worth more points. so you can certainly focusing and narrowin on things that are more likely to come up because we havespent more time on them. >> ok any other questions? yeah.
call it a bunch of times. we're just saying this documentalready takes a function. a couple of things to do. >> and we don't want to spend the timegiving it a name or save it for perpetuity. we just want to run some things. so an anonymous function sortof serves that purpose. when you're not going to use somethingover and over again, so you don't need to give it a name-- you justwant to use it once--
you would just say function, forexample, in this case, and you're just defining something thatyou could give a name. >> like, we could pull this function outand give it a name and then call that function here. but we don't need to because we don'twant to waste time giving it a name or wasting something in our name space. and you'll see that a lot. for example, we see that a lot in thiscode, but you've seen this before when you click something--
run this type of code. >> we could define the code that we wantto run when we click, in this case, this id, as a separate functionand then run that function. but in this case, we're just skippingthat step and moving it into here and just to defining everythingthat we want to happen and not giving it a name. that still might not haveanswered your question. >> audience: no, it does. i mean, i guess i just don't reallyget why it would be a
function at all, though. because it's not really being called. it doesn't really have a name. >> jason hirschhorn: it's a function in thesense that it's a series of steps, like you would put in a function. and then that's why we callit anonymous function. we're not going to give it a name. we're not going to waste tryingto name it, but we could. >> anonymous functions, youcan always give a name.
so for example, this code right here,we could put this code inside a function and then callthis function here. instead, we say, we're not goingto bother with that. we're just going to writeit all right here. >> it's like sometimes when you're writinga four loop in c-- you guys have seen this before-- maybe you'reiterating through a forloop into i equals 0. i is less than strlen. or you're going through somearray, you can save array
index i in some variable. and you use that variable. so you don't need to rewrite arraybracket i over and over and over. >> and that's sort of likea dummy variable. it's not serving much purpose other thanto make your code a bit cleaner and easier to read. similar function here. just makes it a bit easier, butfunctionally there's no difference. does that answer your question?
>> audience: yes. >> jason hirschhorn: ok.. mario? >> audience: yesterday they often putfunction parentheses event. does that mean something? or is it for things likethat they would do document.ready function event. >> jason hirschhorn: we've seen this, andagain, these are smaller things that probably i don't want tospend too much time on.
because sometimes i don't want peopleget freaked out that they haven't heard about these things that much. but we talked a bit aboutevent handlers. so something happens, and thenthis function is executed. and then we also want to knowsome details about what happened in this event. >> so think back to problem set 4. that's probably the easiest way tounderstand that in break out. there was some code--
like an event would happen, butevent can mean many things. if could mean the mouse is clicked, itcould mean you hit an arrow key, et cetera, et cetera. >> but it's all saved in this genericthing called events. and then we can say, isthis event this thing? or is this event this thing? or, what sort of happenedwith that event? so that's why you create that variablethere to save that extra information about what exactly happened thatyou're going to want to
utilize in the function. but again, that's probably one of theless important things to be super familiar with. >> ok, what other questions have peoplehad, or stumbling blocks they've encountered while reviewing? we'll back to that list. what about during practice quizzes, ifpeople have taken those already? what were some problems thattripped you guys up? i know for a fact that last year'squiz was really hard.
>> audience: can you explain whatan sql injection attack is? >> jason hirschhorn: ok, great. so we talked about this a bit. there's a lecture on security. and again, as i mentioned earlier,this is an aside. but you will be frustrated on the quizwhen you read some small two point question, and you're like, whendid i ever learn that? >> all of those things in those lecturesthat you didn't think you needed to know, or you could gloss over becausethey didn't have to do with the
problem set, those will likelycome up again on the quiz. so, cool, fun things that you justthought david was telling for you to enjoy, he was telling you for you toenjoy and to make you just be super excited about learning everythingthere is to learn about computer science. those things also come up on quizzes. so, even these small things that didn'tdirectly relate to your problem set, as you guys are familiar with fromquiz 0, will probably come up. and this is a good exampleof something.
>> so a sql injection attacks is when youget some information from the user and you want to insert it into a table usinga sql insert statement, but you didn't sanitize the inputahead of time. so, obviously we've seensql statements. i'll just open up-- let's go-- we'll go to the review-- i think, who covered it? i think samala did.
so we can get-- >> audience: where did you find this? >> jason hirschhorn: so if you go tocs50.net, quizzes, and then you can scroll over and get slidesfrom the review session. but you can see this is a good exampleof a sql injection attack. we take some information from the userand they give us a string, and then we want to insert that stringinto a database. generally we are going to sanitize thatinput, which means there are some characters that are dangerous.
>> for example, in sql strings,these quotes-- single quotes or double quotes-- mean something. they mean end this string here. and so if the user gives you a singleor a double quote, they could be trying to trip up your sql query andinsert some bad stuff into it. and if they do that, they could gaincontrol of your database or do some things that you don't want them to do. >> so that's why whenever we take sqlqueries, we sanitize the input before
putting it into the database, whichmeans we escape those characters. we'll talk about that in a second. but long story short, a sql injectionattack is if you don't do that-- if you don't take care of the inputthey gave you before putting your database, they can, as you see downhere, run a query that, in fact-- they put in their code down here andthis select line down here will select everything from the table regardlessof what the password is given. because you have the or 1 equals 1. >> so it's basically, long story short,a way to take over the database.
the question, then, for you guys, iswhere in p sets 7 did you sanitize all the inputs to your sql queries? where did that step happen? where do you prevent sql injectionattacks from happening in p set 7? >> audience: crypt? >> jason hirschhorn: so it wasn't crypt. we didn't make you do this for thisparticular problem set, but it happens in the query function. we actually wrote it for you,and we took care of the
sanitizing inputs for you. but in years past, students have hadto type the inputs on their own. in p set 7, a lot of you-- let me open up one other file. >> so you'll notice up here a lot ofpeople, in problem set 7, did not call this function on strings. this function, htmlspecialchars,again-- this string might have some thingsthat in html mean something else. like a brace, a square, or an anglebracket mean something in html.
>> and so if you print that out to thescreen or if you just take that and print that out to your html, that mightdo something you don't expect. so htmlspecialchars goes over all thosecharacters that have special meeting and escapes them. so it gets printed out as the textyou want to see, rather than screwing up your html. we called that function in the header. and a lot of people forgot tocall that function in the code you were writing.
>> so, for example, if a stock name had anangle bracket in it and you forgot to call this function, that anglebracket could have thrown off what your html looked like. but calling this function will escapethat so it actually prints out as an angle bracket and doesn't throwoff your html code. >> the same reason we've seen, sometimes,slashes before double quotes in a printf line because we don't want thedouble quotes down the string. we want to print themout to the screen. so all of this is the same idea.
>> audience: kind of. >> jason hirschhorn: do youhave a follow-up? >> audience: i guess the sql injectionattack has to do with that? i don't understand howthe two are related. why would you do the specialchars? >> jason hirschhorn: ok, so the sqlinjection attack is when you inject some malicious strings into somebody'sprogram, and they just take it and run the sql query with a stringyou gave them. as you can see down here, thatcould be problematic.
so the way you prevent against that isyou take their string that they give you-- so this string right here-- and you sanitize it. you escape all the things thatare potentially problematic. so you don't interpret them as somethingthat means something. >> and an example of that withhtml is this function. so it's the same idea here. and i was just showing you otherexamples of when you've seen this idea before.
of escaping user input before printingit out to a screen or putting it inside a sql statement. >> audience: so in this case, the useris messing with the programmer. >> jason hirschhorn: yes. with all of these security attacks,that's always generally the user, or somebody, is trying to messwith you, the programmer. and these are ways you canprevent against them. >> audience: so i have a questionabout hash functions. in quiz 1 from 2011, there are twoquestions about one-sided hashes.
and i was just wonderingwhat that meant. >> jason hirschhorn: ok, which quiz? 2011? >> audience: yeah. >> audience: quiz 1? >> audience: [inaudible]. that's like hashing a password. that's not putting things-- >> jason hirschhorn: what page was it?
>> audience: i think it was9 or 10, or both. >> jason hirschhorn: all right,go ahead, curt. you can answer while we look. >> audience: i think it's talkingabout hashing a password. like, when someone enters a password,you turn it into an encrypted thing. that's the password hash, which isdifferent from a hash function that puts something into a hash table. >> jason hirschhorn: let's see. let me pull up what theygive as the answer.
and then we'll walk through it. >> so curt gave a great exampleof a one-way hash. when we've seen this before, wetake the password and turn-- remember, in p set 7, somebody mighthave a password that's just password, but then it gets encrypted intosome really long thing. the one-way hash means it is very easyto go from one way to the other, but it's very hard to go fromthe other way back. >> and so you know, when you were checkingpeople's passwords in problem set 7, you would take their--
so, for example, say they wanted tochange their password, you ask them for their old password. you took their old password. you encrypted it. and then compared the two encryptionsrather than unencrypting the original one, because it's reallyhard to go that way. >> audience: how in depth does ourunderstanding of telnet have to be? >> jason hirschhorn: if it was mentionedbriefly in lecture, just a brief understanding.
again, back to the answerto avi's question-- the more things come up, the more likelyit is you have to be super familiar with them. if they've only come up in lecture,that's just one place. but if they come up in lecture, section,and a problem set, then you probably have to be superfamiliar with them. >> so i had a question fromearlier about-- is was fall 2010-- quiz 1, let's pull up--
this question on stacks and queues,which we did spend a fair bit of time talking about in lecture, eventhough we didn't really ever hit it in section. so this question is giving you a seriesof commands and asking you what gets printed in this case. so this is a totally reasonable questionthat could be asked of you guys, and then you guys shouldbe able to answer it. >> so why don't you look at it for 30seconds, and then if anybody wants to propose the answers to me, andthen we'll walk through it.
all right, who has an answerto question 27? >> audience: is it 1, 2, 3, 3? >> jason hirschhorn: that's right. 27 is 1, 2, 3, 3. so let's look at how we got that. >> first, we are saying, if s isa queue, what gets printed? so a q is first in, first out. we've seen that before. we saw the picture of the peoplewaiting at the apple
store to buy some product. the first people in arethe first people out. the first things in a queueare the first things out. >> so if we push something into a queue,you push the 1, then we pop the 1. pop just means take out. in this case, just take something out. we take out the firstthing, that's a 1. so we'll put things weprint down over here. this is no longer in our queue.
>> then we push on a 2 and a 3, andwe pop off the first thing. again, because it's a queue. so we get a 2, then we put on another3 and call pop again. our 3 is first. >> and then we had a whole bunch ofother things and call pop. but again, since this is a queue,first in, first out. we take out the first thingthat was ever put in. that's our 3. and, in this case, we don't worryabout all those other things.
so that's if this is a queue. any questions about a queue? >> a stack's different. what is the acronym we havefor understanding a stack? >> audience: last in, first out. >> jason hirschhorn: lifo, i think. last in, first out. so we saw an example of a stackof trays in a dining hall. whatever tray is on topgets picked up.
and then if new trays comein, they get put on top. and then whatever is ontop gets picked up. so those trays on the bottom mightstay there for awhile. >> in that case, again, we'lldraw this out. we push on one, so oneis first in line. and we pop something off. and there's only one thing in there,so we move 1 down here. then we put on 2 and 3 andwe pop something off. >> but again, since this is a queue--
or this is a stack, rather-- we take whatever was in last. whatever is in last comes out first. and 3 is in last. so we put the 3 down there, thenwe put on another 3 and we pop something again. finally, we put on the 4, 5,6, and 7, and here we pop. and because it's a stack, we takewhatever was put in last and write that down here.
so we end up with 1, 3, 3, 7. does anybody have any questions aboutstacks or queues, or this example? >> ok. let's go back to the list of topics. not that way, this way. what other questions do people have? >> audience: i don't know how importantthis is, but i was confused by the difference between different types oflanguages like markup, compiled, interpreted.
we would always run a compiler. and then where are your errorswhen you run the c compiler? where does it show you theerrors in your code? how do you know there's anerror in your code in c? >> audience: it shows youin the terminal. >> jason hirschhorn: it shows you in theterminal as you're compiling. and if there are errors, itwon't actually compile it. so you know that there are errors rightaway, ahead of time, before you even run your code.
>> of course, you might run your code andget a segmentation fault, but that was probably because you didsome silly logic thing. but your code with technicallyall correct and could run. so c code gets compiled ahead of time. what about php code? where were errors in your php code? how did you know you had errorsin your php code? >> audience: run time? >> jason hirschhorn: yeah, when youwould run it, you would run the
php code in the back. and then you would display a screen. you might see some things on the top,but then you would see, like, some orange, ugly table. and it would give you a line number andsay, blah, blah, blah, this stuff didn't work. >> so php is interpreted line by lineand executed on the server. and then the result issent over to you. great.
>> so there's some of the biggestdifference in terms of how these languages, or how the programming codeyou write are actually evaluated. there are also other differences interms of-- the biggest difference we've seen in terms of variablesin the different languages. so can anybody give me a differencebetween variables in the three languages? yes. >> audience: in c, they'restrictly typed. in the other two, they'reloosely typed.
>> jason hirschhorn: andwhat does that mean? >> audience: that in c, you have to declarethe type of the variable when you declare the variable,like interbool or char. >> jason hirschhorn: excellent. in c, we always had to puta type of a variable. and we couldn't really mix types. you couldn't do an integerplus a string. but as we've seen in these otherlanguages, you actually can mix types, and you never really have to givesomething a type, ever.
i think those are probably, off thetop of my head, the two biggest differences between thesethree languages. but, yeah. >> audience: and the scope of c variablesis restricted to the curly braces, where the other ones, it's just like,it dies if it's in a function only, but otherwise, it's-- so scope is slightly different in c. asyou remember, curly braces define the scope of variables. so if it was defined inside an ifcondition, which is inside a for loop,
>> audience: can we go into ajaxand talk about what that is? >> jason hirschhorn: talk to avi after. he asked that question earlier. >> audience: my bad. >> jason hirschhorn: no worries. >> audience: what exactly is json? >> jason hirschhorn: what is json? what's your question? >> audience: just really quickly,the difference between
why do you even know the word json? when have you seen it? >> audience: when we were gettingstock quotes for finance. >> jason hirschhorn: so you sawit when you were getting stock quotes for finance. and why did you see it? >> audience: when we were retrievingall the information that came in that format. >> jason hirschhorn: so you would get--
yeah. go ahead. >> audience: [inaudible] informationout of an object? >> jason hirschhorn: both of thoseput together is the answer we're looking for. you want information fromthis other webpage. and you would hope that when you'regetting that information, it would be presented to you in some typeof standardized format. >> everybody is probably familiarwith comma-separated values.
and then we know, because it'sa standard, what it's going to look like. so we can iterate through the arraythat's returned to us, the array of objects that are returned to us. >> we do probably need to know the keys,but they generally give you documentation in the website whenyou're fetching some json notation for them. likewise, you can jsonencode an object. so there's a function jsonunderscore encode.
and so you can take an object thatyou've created, json encode it, and pass it on to somethingelse, if you want to. and json decode also exists fora similar purpose, or for the opposite purpose. >> audience: do we need to know codingfor hash tables and tries? or do we just need to understandhow they're used, conceptually? >> jason hirschhorn: so, raise your handif you did a hash table for p set 4 with a link list. or p set 5.
so that was a vast majority of people. p set 5, 6, who knows. a long time ago. >> so the vast majority of you didhash tables with link lists. and because that's probably the morecommon approach, and because we spent a lot of time doing link lists and hashtables, you should probably be pretty familiar with how to codea hash table and a link list. >> and if you think back to that problemset, it wasn't really as hard as you expected.
and there was a lot lesscode than you expected. i would say you should know how tocode a hash table or a link list. not that you'd be asked that,necessarily, but you should certainly know that. >> also, if you look through past quizzes,there have been a lot of questions about writing functions onlink lists or doubly-linked lists. that seems to come upevery single year. right insert on a link list, rightdelete from a link list, right insert for a doubly-linked list, et cetera.
so that, i feel pretty comfortablesaying you should know that. >> for try, i would say you shouldcertainly know how it works, and maybe give some pseudocode for howto code it and set it up. but it would not be the worst thing inthe world if you didn't know how to code it in c. it would be great if youknew how to code it in c, but i think probably pseudocode for a try wouldbe the most you would need to know for a try. >> audience: extra credit? >> jason hirschhorn: and same with, if wego into binary search trees, you might
need-- and you've seen in the past,we've done a lot of-- you know how binary search tree works. you should probably be able toset one up in pseudo code. but because the vast majority of peopledidn't do that on the problem set, i'd say it's probably lessimportant that you know how to code and set up a tree like that. >> any other questions? also, we can ask them throughoutas we go through some problems. ok, we're going to move on.
skip that slide for now. >> speaking of trees, that is the firstquestion i have for you guys. because this is a problem. i would say it's highly likely you'llget a problem like this on your quiz asking you to code some type of insert,delete, search, for one type of data structure we've seen. >> that comes up every year and we spent alot of time the second half of this semester going over these data types. so right now, i've defined a nodein a binary search tree.
and what i would like you to do is givena binary search tree that starts at this node star root, complete theimplementation of the function below, which happens to be a find function. and do it with and without recursions. >> so i want you to write two functions. one doing this with recursion, onedoing this without recursion. and do not assume that theroot will be non-null. so we're looking for the integer i inthe tree starting at root, and we need to write this recursivelyand iteratively.
>> audience: so you want us to return trueif we find it, and false if we don't find it. >> jason hirschhorn: how did you know? how did you know that? >> audience: i was asking first, but i wasassuming, because it says bool at the beginning of the function. it says bool, so i don't even need totell you what i expect you to return because it says right there. but that's right.
return, true or false. >> so before you begin, i would recommend,if you are unfamiliar with binary search trees, quickly drawinga picture of it to get your understanding, right. that will also help you when writingyour code and checking it. again, you also don't have that muchtime on the quiz to do all the things that we ask you to do. so writing pseudo codeis very helpful. >> and we generally give about--
if the pseudocode is perfectlycorrect, that's generally 50% on a question. so it's not a hard and fast rule, but ifyou just write pseudocode and it's correct, it's generally 50%. so i'd always recommend-- if you're pressed for time, or even ifyou're just trying to figure it out-- starting with the pseudocode. and finally, if you could write thisall in c, that would be fantastic. >> so let's take three minutesto work on this program.
and then we are going to writepseudocode for it just once, and then we're going to code it recursivelyand then iteratively. >> if you have any questions, feelfree raise your hand. happy to walk around and answer thembefore we start as a group. >> let us resume, and we're going topseudocode the recursive version of this, and then we will code it. so a recursive functionneeds two things. this might be a question thatyou could be asked. needs two things.
who can raise their hand and tell mewhat the two things a recursive function needs? by definition it has two things. what are those two things? new hands. yes, alden. >> audience: so i'm not exactly sure ifthis is the terminology, but-- >> jason hirschhorn: i'm gladyou're raising your hand. >> audience: it needs a base case,and it needs a recursive step.
>> jason hirschhorn: perfect. it needs a base case anda recursive step. so what's our base case here? >> audience: f root equals equals null. sorry, just in pseudocode,if it's null. if root is null. >> jason hirschhorn: if root is null. that's excellent. that's our base case.
that's what we're goingto check every time. and base case is thefirst thing you do. if you hit the base case, you're done. >> now we need our recursive call, and i'dbe willing to bet we need a couple recursive calls here. because it's a tree, and wecould go multiple ways. so if root is null, we're good. >> what do you propose? and now i'm going to start calling outon you guys, because i know you guys
all know this. but annie, what shouldthe next line be? what if we found it? what do we do? >> audience: if we found it? >> jason hirschhorn: or whatshould be that-- give me the pseudocode for theline where we found it. >> audience: if i equals root i? >> jason hirschhorn: andthen what do we do?
>> audience: return true. >> jason hirschhorn: great. so if i is i-- oh, they're both called i. that gets confusing. but if i is i return true. that's probably the nextthing we should do. makes sense. >> ok, now we haven't done our recursivecall yet, though, because a recursive
call would call this function again. so what should the nextline of pseudocode be? anna. >> audience: the left side. >> jason hirschhorn: be specific, though. this is a binary search tree, so whatdoes checking the left side entail? >> audience: so node-- i'm sorry, root. and then arrow left.
node, node, sorry. i'm not reading it properly. it's called node, right? >> jason hirschhorn: it will be called rootin that function, but either way. the left side-- yeah? >> audience: if it doesn't equali, then we're going to call the function again? if it doesn't equal i, we're goingto call the function again. but what side of the tree are we goingto call the function again?
>> audience: on the left side. >> jason hirschhorn: we're not alwaysgoing to call it the left, if it doesn't equal it. >> audience: oh, sorry. call on the right. >> jason hirschhorn: we want to knowspecifically, though-- remember, in a binary search tree, everything tothe left hand side is smaller. everything to the righthand side is greater. so it's just not-- yeah, go ahead.
>> audience: if it's less than i, then-- if it's on the left-- >> jason hirschhorn: so ifri is less than-- so if our number is less than i,what side do we want to go to? >> audience: we want to goto the right side. >> jason hirschhorn: we want to go-- let me draw a quick tree. if this is 5, this will be 3. so if ri is less than five, whatside do we want to go to?
>> audience: sorry, what? >> jason hirschhorn: our number isless than the number we're looking at right now. >> audience: oh, then we wantto go to the left side. sorry. >> jason hirschhorn: exactly. no worries. in the binary search tree, everythinglower is to the left, greater is to the right.
so if our number is less thanthe i we're checking-- because you see in thenode, it has an i-- then you want to go to the left. >> and this is an easy one. what is it the other line of pseudocodewe need to write? carlos? >> audience: same thing, you just switchit to a greater than sign and go to the right. >> jason hirschhorn: can yousay it one more time?
>> audience: if our number is greaterthan i, go to the right. >> jason hirschhorn: excellentjob on the pseudocode. let us do this in real code. and again, this pseudocode willprobably get you, because it's correct, 50% on this question. but this pseudocode also translates oneto one, essentially, into code. >> so let us do this in c. who can giveme the first line of code? actually, first, before i dothat, let me pull over-- >> audience: i have a question.
why did you indent theline i gave you? >> jason hirschhorn: becausei couldn't write. i don't know. you're right. that line should be over there. >> ok, here is our function. and let me pull over, also,our definition of a node. what happens if we didn'twrite typedef? does anybody know?
>> audience: it wouldn't compile. >> jason hirschhorn: it wouldcompile, yeah. >> audience: would it just declare oneinstance instead of making it a new type you could declare multipleinstances of? >> jason hirschhorn: so it wouldn'tknow-- it wouldn't just declare one type. you could still make a lot of nodes. >> audience: but wouldn't we have towrite struct node every time? you would have to write struct nodeevery time, instead of just node.
but with typedef, you can justwrite node every single time. ok, who hasn't given-- yeah, avica. >> audience: if root equals equalsnull, return false. >> jason hirschhorn: great, andthat's our base case. next line of code. somebody who hasn't givenme a line of code yet? >> audience: root arrow iis equal equal to i. then return true. next line?
someone else? and then you can go next. >> audience: else if root arrowi is less than i return function called find root-- >> jason hirschhorn: sorry. >> audience: return find rootpoints to left comma i. >> jason hirschhorn: so if ri is greaterthan the thing in the tree, we want to go to the left? >> audience: no, i had that switched.
>> jason hirschhorn: which one? >> audience: no, yeah. i have a less than sign there. >> jason hirschhorn: right, if ri isless than what's in the root-- our current root-- then wewant to go to the left. and what's the last line, you? >> audience: basically the same thing,except switch the greater than or equal to less than and left to right. does anybody have any questionsabout this?
so some other things that wouldhave been correct is that could be the -ltiff. guess, technically, none of thesereally also need to be -ltiff. >> also, there's probably onlyone case down here. so that's probably your last case. you don't even need that -ltiff. but probably good to writeit, to be clear. >> audience: so you don't think the quiz--if we make errors, for example, in syntax--
little syntax errors-- how does that get taken in the quiz? >> jason hirschhorn: generally on the quiz,small syntax errors or small style errors don't lose you points. so if you forgot a semicolonhere, it would be ok. if you forgot to close this parenthesis,that would be ok. >> huge syntax errors that alter thefunctional meaning of your code dramatically, you might gettaken off points for. or generally, just grading youon whether or not your
code functions, even-- not its design so much,and not its style. >> let's now code an iterativeversion of find. so it's going to be pretty similar, butthere are certainly going to be some key differences. however, our pseudocodecan probably go-- we can still take one line of thepseudocode and figure out what the line is in this case. >> so in an iterative version, whatdo you think, julia, should
be the first line? >> audience: again, in iterative boolean,you need to set up a for loop, right? >> jason hirschhorn: ok. >> audience: so for like, k, for xequals 0, x is less than i. or no, x is less than thesize of the tree. >> jason hirschhorn: the tree. so we don't really know the size of thetree, and we don't really know for how many times we can go, so what's adifferent type of loop that might be better in this case?
>> audience: if else? >> jason hirschhorn: if elsecannot be a loop. so what's a type of loop we can justgo until some case is met? what's the only other type of loopin c besides a for loop? >> audience: while. >> jason hirschhorn: while, exactly. in a while loop, don'tneed to know how-- a while loop and for loop can do theexact same thing, but the nice thing about a while loop is we don't needto know how big our tree is.
so we're going to go until what? >> audience: until it equalsthe size of-- >> jason hirschhorn: well, it's verysimilar to our recursive case. so-- >> audience: while rooti does not equal i. >> jason hirschhorn: that's really close. while root i-- let's try it. i don't think [inaudible]
where root i does not equal i. we might need to change it in a littlebit, but that sounds like it's pretty good, for now. so we'll do that. >> also, remember, we can't assumeper the question. you do not assume that theroot will be non-null. so what do you think the veryfirst thing we should do is? >> audience: just do the samething as before. if the root equals equalsnull, return false.
so it could be null. so we want to get ridof it right away. and then we're going check ifroot i does not equal i. so, say we're searching in this treefor 3, root i does not equal i, now we're in our while loop. what do we want to do? and again, it's going to be prettysimilar to our recursive version. >> audience: so you'd want to iterate, orkeep going down the tree as long as the root is not equal to null.
>> jason hirschhorn: as long as theroot is not equal to null? >> audience: the root dash iis not equal to null. just the root, yeah. as a long as the root isnot equal to null. >> jason hirschhorn: so you wantto change this into root does not equal null? >> audience: we could combinethese, right? we don't need the if, initially. >> jason hirschhorn: ok, so if we don't--
if we combine them, so we're going to dowhile root does not equal null, and if the root happens to be null at thebeginning, what do we do down here? >> audience: return false. so both ways probablywould have worked. this is a different way,and this combines it. but again, if you did either way, we'renot going to take off design points on the quiz. but this looks good. >> so while root does not equalnull, what is the first
thing we want to check? somebody else? null, what's the first thing? >> audience: if ri is less than-- oh, i guess, if we alreadyfound it in the root. so if root arrow i is equal to i-- >> jason hirschhorn: sorry? >> audience: if root arrowi equals equals i-- >> jason hirschhorn: what do we do?
and what's next? jeff, what's the next line of code? >> audience: if i is less than root arrowi, then root equals root arrow left. >> jason hirschhorn: root equalsroot arrow left. so that's probably the biggestdifference here in this iterative version as opposed to therecursive version. the recursive version, wecall the function again. we'll be updating root whenwe call the new function. here we're not calling a new function.
we're simply just updatingroot in this function. and what is the last line of code? yeah, mario? >> audience: else root equalsroot arrow right. >> audience: root equalsroot arrow right. >> jason hirschhorn: could you alsowrite something like this? >> audience: i have no idea. >> jason hirschhorn: you can't. you can't do plus equals.
ok, so this looks good. why don't we just do thatto clean it up. this looks great, and this would work. and we would break out. >> if root left was null or root rightwas null, we would come up here. root would be equal to null. we'd break out of our loop,and we'd return false. so when we break out of theloop, we return false. >> and again, the a while loop was perfecthere because we don't know how
big our tree is. we tried to write the for loop, but werealized you've got to figure out how big it is ahead of time. >> audience: if this weren't a binarysearch tree, it would be real math-y to write it iteratively, right? like, if it was a tree,but not necessarily-- so it wasn't all smaller on the left,and all bigger on the right. it would be really difficultto iterate over it, right? we'd have to save what was earlieron in the tree and go back,
and stuff like that. >> jason hirschhorn: if it wasn't a binarysearch tree, if it was just a tree and things weren'tsorted like this-- and we realized earlier when annawas helping us that making it sorted helps us a lot-- we would need to, yes, always savewhere we were previously. but there could be a lot ofwhere we were previouslys. there could be a lot of parent nodes. >> probably the best way to do that wouldbe to keep pushing things onto some
type of stack or queue. you would never need to code thisbecause it's a hard problem. but you push some things onto a stackor queue and then pop them off, and then evaluate them. >> and then have some other thing whereyou're actually putting the nodes, and then create that, and thensearch through that. that might be the best way to do it. ok, any questions about this problem? >> audience: this is on a related note.
will we have to compare run timesfor hash tables, binary search trees, et cetera? >> jason hirschhorn: probably. so let's do that really quickly. run time for hash table-- what are the others? binary tree? >> audience: link lists. >> jason hirschhorn: ok, let's do insert.
what is the big o of inserton a hash table? what are the assumptionsyou're making? >> audience: you're inserting at thebeginning of the link list. >> jason hirschhorn: probably the firstassumption is there are no collisions. if there are no collisions, thenthe insertion time is one. if there are collisions, and you'redoing separate chaining and inserting at the beginning of the link list,then insertion is also constant. >> if you're doing a hash table but youhave a different method of dealing with collisions, what'sa different method?
what's is a different methodof dealing with collision in a hash table? >> audience: linear programming. >> jason hirschhorn: linear programming. so we're going to keep lookingfor the next open spot. that is not constant insertion time. you could have to go throughthe entire table, so that could be big o of n. >> audience: otherwise just chaining?
>> jason hirschhorn: we didseparate chaining. that was the first one. that's what the link list. the fancy name is separate chaining. it could be any type of list structurewe happen to do in link list. >> so again, insertion on a hash tablecould be constant time. what about insertionon a stacker queue? >> audience: isn't that constant? >> jason hirschhorn: it's constant time.
you're just pushing it on. ok. insertion, what were the other ones? on a try? what is big o of insertion on a try? >> audience: length is constant. length of the longest-- the length of the wordyou're inserting. wait, so what did i hear?
you said-- what did you say? what was your answer, marcus? >> audience: the length of the wordyou're inserting in characters, assuming it's a character try. >> jason hirschhorn: ok, sothe length of the word. we'll make an assumption thatit's a string of characters. you said something different, though. you said length of longest word. >> audience: that's just constant, right?
>> jason hirschhorn: why wouldit be constant? >> audience: like, if you use big onotation, then it doesn't vary based on the number of things thatare already in the try. >> jason hirschhorn: so we wouldsay it's constant time. it is constant insertion, andthat's because this idea-- say we have a word that's 45,or a word that's 60, that has a constant number. and it would just be insertedin constant time. >> in practice though, it would not be,obviously, happen in one millisecond,
for example. but we would say big o isconstant for a try. and that's one of itsbiggest advantages. >> what about insertion into a link list? just a generic, sorted link list? >> audience: i had a question. on the test, would they ever ask us theinsertion time that's four steps, or something? or is it just--
when you say insertion time is one,that just means constant time? >> jason hirschhorn: yeah, they wouldalways ask, is it big o of n? big o of log n? n squared constant. those are really the onlyones you need to know. what about insertion ontosorted link list? >> audience: i had a question-- a question-- >> jason hirschhorn: what is the answerto that question, though?
>> audience: wait, what did you ask? >> jason hirschhorn: what is big o ofinsertion into a sorted link list? >> audience: one? no wait, no wait, n. >> jason hirschhorn: n. besidesthe link list. and what was your question? >> audience: so would you writeo of k or o of 1 for the-- >> jason hirschhorn: oh. i would write o of 1, probably.
there was one other data structurethat would have been good. tree, binary search tree. what's insertion on abinary search tree? >> audience: login. >> jason hirschhorn: so, what is the worstcase in a binary search tree? so if we happen to start at 5, and everynumber is greater than 5, then we've got 5, 7, 9, 11, et cetera. in this case, it's basically just a linklist, and we need to insert all the way at the end.
so it's big o of n. >> that could be our worst caseon a binary search tree. obviously, you would never constructa binary search tree with 5 in the middle, knowing 5 wouldbe the lowest number. but it could be, if you'restarting from scratch. any questions on this before imove on to another question? that was a good question. i would know big o of-- >> audience: what about searchingfor those four?
>> jason hirschhorn: definitely wedid searching and sorting. we did all those algorithms, right. wait, was that for quiz 1? was that covered-- did you already have thatquestion on quiz 1? the big o runtime of binary search,insertion sort, bubble sort? >> audience:yeah. >> jason hirschhorn: if you had thatquestion on quiz 0, odds are you won't get the same exact question on quiz 1.
might be still good to know those. you should hopefully know gh already. >> but other logarithmic runtimesare probably good to know. things that weren't covered on quiz 0. like all these operators onthese abstract data types. >> ok, let's move on. this one should be pretty quick. and this is a new language we haven'tactually coded in before. this is a question askingto code in php.
so consider the php array below. write php and/or html codes such that itoutputs a two-column table with tfs names and houses. >> you've never done this before,this specific problem. but this should be very familiar towhat you did in problem set 7. so i would be willing to bet you will beasked to code something in php that is very similar to what youdid in problem set 7. >> firstly, array is not that specific. what type of array is this?
>> audience: associative. >> jason hirschhorn: it'san associative array. and what's the difference between anassociative array and an object? >> audience: an object array has an indexof integers, and an associative array is an index of a string,or something like that. >> jason hirschhorn: so an array ofobjects would have indices of integers, but an object has fields. it has those fields names likename, house, student. do you have an idea?
>> jason hirschhorn: what do youmean, coded under the hood? >> audience: we were told that associativearray was technically a hash table. so is object also technicallya hash table? >> jason hirschhorn: i'm not goingto answer that question. i'll get back to you on that. but i wouldn't think of eitherof those like that. but, in any way, associative array andobject, generally, people use those terms interchangeably.
in this case, the cool partis you can use keys. strings as keys, rather thanjust simple numbers. >> so i've been talking aboutthis for awhile. hopefully, some people havegotten started on this. we're going to write some php and htmlcode, such that we get a two-column table with tfs names and houses. >> ok, i also would like a headerrow on this table. so i'm going to get straightinto this. we're going to file, new,and we're going to--
how do i start a table? what's the tag, michael,to start a table? >> audience: table. >> jason hirschhorn: table. and if i open a tag, whatelse do i need? >> audience: a head? or, i guess, class. >> jason hirschhorn: so, sorry. assume that we've already writtendoctab, html, all that stuff.
but if i open this table tag, whatelse do i need to write? for validate html? >> audience: close it. >> jason hirschhorn: close the tag. how do i write a close-table tag? >> audience: dot slash table. >> jason hirschhorn: slash table, great. probably makes sense to write bothof those together because you've got to do it.
ok, if i want a header row, how doi write a header row with titles? >> audience: is it lessthan 10 hr close-- tr, yeah. >> jason hirschhorn: tr? >> audience: then same thing,the slash, yeah. >> jason hirschhorn: ok, andgive me two columns. >> audience: t d? i want two columns. does this give me two columns?
how many columns is this? one. so let's copy and paste this. >> so actually, on the quiz, all this codethat we've written so far was actually given to you. but you should probably stillknow how to write it. >> audience: your houseis between the two. >> jason hirschhorn: boom. it should go right there, right?
good call. so again, all this code is actuallygiven to you on the actual quiz. but it's fun to write it, and youshould know how to write it. so this is where you needto start your code. what do we need to write right here? >> sorry, i need to changethe name of this file. so we saved it in a .html file,not in a .php file. these things would mean nothingin a .php file. so we're in a .html file.
what is the first thingi need to write? i want to put some phpcode in an html. >> audience: php, like another carrotand question mark php, right? and how do i end that? >> audience: with a question mark. >> jason hirschhorn: that's great. that's the first thing i need if i wantto put some php code in here. >> audience: i thought a .phpfile could take html. >> jason hirschhorn: yeah.
a .php file can take somehtml and be displayed. that was my bad. i was just trying to mimicwhat it was on the quiz. >> ok, sorry to confuse you. yes, practice.html. now we're going to putsome php code in. what is the first line ofphp code i should write? i'm going to go through this arrayand make it into a table. >> audience: you can either usea for h loop or a for loop.
>> jason hirschhorn: ok, whatdo you want to use? >> audience: i would use a for loop. for, and then you do dollar signi equals 0 semicolon dollar sign i less than 2. and then semicolon i dollarsign i plus plus. >> jason hirschhorn: how doyou know to use a 2? >> audience: because there were twoassociative arrays within the bigger associative array. >> jason hirschhorn: so the big thing'snot an associate array.
the big thing's just a normal array. but you're right, there aretwo associative arrays inside our larger array. that's why you use two. i feel uncomfortable assuming thatthey're 2, so what's a way to write this without assuming that they're 2? >> audience: [inaudible]? >> jason hirschhorn: ok, howdo you write that? >> audience: foreach dollar signtfs or like dollar sign tf.
>> jason hirschhorn: ok, so for eachtfs as tfs, i want to, now again, have my table. so who can give me thenext line of code? >> audience: print, and then inquotations, bracket tr end bracket, end quote. end parentheses, semicolon. >> jason hirschhorn: ok, andwhat's that going to do? >> audience: it's going to say, new row. it's going to put thetag for a new row.
>> jason hirschhorn: right, this php, likewe talked about earlier-- this php is going to be evaluated, and thenit's going to print out to this file a table tow, and then thathtml will be evaluated. we're just copying thishtml we had up here. it's right here. fall 2012. don't look at the answers,let's solve it together. so we print table row. so you're probably inthe swing of things.
what's the next line ofcode we need to write? assam, give me the next line of code. >> audience: you need the tf's name. tf open brackets quotation markname closed brackets. >> jason hirschhorn: give me their name. >> audience: you need to print that. >> [interposing voices] >> jason hirschhorn: ok,how do i print it? >> jason hirschhorn: i'm missingsomething now.
what am i missing? >> audience: you need a dollar sign. >> jason hirschhorn: whatelse am i missing? all we've printed so far is the tr. >> audience: close the tr after it. >> jason hirschhorn: so we needto close the tr after. who sees what we're missingon line 16? yeah, anna. >> audience: you need to opena td and curly braces.
>> jason hirschhorn: and wheredo we put curly braces? >> audience: around the tf name. >> jason hirschhorn: like this? and then close the td. >> jason hirschhorn: like that? >> audience: do you need double quotationmarks next to the curly braces? >> jason hirschhorn: right here? no, you don't. so that's exactly right.
who can give me the last lineof code we're missing? >> audience: just the exact same thing,just with house instead of name. great and your syntax is exactly right forgetting things in an associate array. so in the actual quiz, you areactually given up until here. so this code was given to you. all you had to write were thesefour lines and remember to close the table tag. you guys actually didall that and more.
>> audience: so it would be functionallythe same if you just had that all in one big print call, right? and then just concatenatedit on, et cetera? it just wouldn't look good if you werelooking at it when you're inspecting the element on your website, right? >> jason hirschhorn: i agree. if i loaded this webpage, would i beable to see this php code, ever? >> audience: no. >> jason hirschhorn: no.
and actually, i wouldn't. >> audience: this isn't html, right? so you might be able to-- >> jason hirschhorn: so this php wouldbe evaluated server side. php is always evaluated server side, soyou're never able to see php code. >> audience: but you'd be able tosee the result of the prints. and it honestly might notput it all on the line. it might format it nicely for you,or it might put it on one line. unclear.
but yes, good point. >> audience: how come there'sno text highlighting for any of the php commands? because i remember seeing that. >> jason hirschhorn: because it's a.html file up here at the top. there you go. >> audience: if we did the initial methodwith the for loops, right, if we wanted to access a tfs, would wedo tfs bracket 0 bracket, then [inaudible]?
>> jason hirschhorn: you would-- so you're saying for the for loop, youwould do in dollar sign tfs bracket 1 or i, right. or dollar sign i close bracketand then square bracket double quotes, yeah. >> ok, excellent. we have one more quick one. seven minutes, so i wantto go over this one. this is another example.
we're now a totally other language. >> we have some html code. it's kind of small on the screen, buti want you to look through it really quickly, and can somebody tell me,if i were to load this web page, what i would see? describe everything aboutthis webpage. noah? what would i see? >> audience: code at the front end ofgoogle with a feel for text and a
submit button. >> jason hirschhorn: and whatwould the button say? >> audience: submit. oh, search. i'm sorry. >> jason hirschhorn: it would say search. remember, name. what do we use name for? this name attribute, what'sthat used for?
>> audience: that's its namefor when it's clicked? >> jason hirschhorn: that could be. but what do we generally see-- whyare we giving this name queue? why do we see that? >> audience: doesn't that become indexof the super global variable? >> jason hirschhorn: yeah, generally whenthis form would submit, and then where would this submit to? what page? noah, what page would this submit to?
>> audience: i'm not sure. >> jason hirschhorn: wherecould we can find it? where do you find whatpage it submits to? what line of code? >> audience: form action. action. so it submits to the search page. backslash search. what method?
>> audience: get. >> jason hirschhorn: get. exactly. so we read this. this is going to be a form. you're exactly right. two things on the form, the title of thepage and the top would be google. >> so here are two questions you shouldbe able to answer about this page. if this html lives at this website andthe user inputs bug into this text
field right here, what url willthe user find herself upon submitting the form? >> so we have this right here. i'm going to go back tothis page, though. i'll write up this first part. can everybody see over here? ok, mario, you think you know? >> audience: backslash search. >> jason hirschhorn: i'm goingto move down here.
ok, backslash search questionmark q equals bug. anybody have a different suggestion? >> so how do we get this? well, we've seen this before. and you came up with this earlier. you were right, noah, that theaction is telling us what page we're going to. >> we also know what method. we're doing get.
and the difference between get and postis that get displays in the url and post doesn't. so if i wrote post right there in themethod, what would be different? >> audience: it would justbe slash search. >> jason hirschhorn: it wouldjust be slash search. nothing over here would happen. but because it's a get, the urlis displayed as follows. first we see a question mark andwe see the name and the value. say there was one other text field andi gave it a name of r and i input a
value, caterpillar. what would this now look like? i have one more text field, i give aname of r and a value of caterpillar. >> audience: after bar you'd havethe ampersand caterpillar. >> jason hirschhorn: that'snot ampersand. >> audience: or just whateverthe and symbol. >> jason hirschhorn: yeah, no. you were right, i was wrong. that's like a g.
>> audience: caterpillar. r equals caterpillar, sorry. >> jason hirschhorn: is thereno r in there? >> audience: no, there is. >> jason hirschhorn: we'll talkabout that after class. that's exactly right. so the and is correct. and then you could have many of these,and they would all be concatenated together with that and.
>> there's one more question. sketch this html's dom, startingwith document. we could do that in two minutes. we'll do it over here. i'll go back to this webpage. ok, we start with document. >> what's next? so when you're reading through-- >> audience: html.
>> jason hirschhorn: html is next. we're going to go tag by tag. what's after html? >> audience: head. >> jason hirschhorn: head. what's after head? >> audience: title. >> jason hirschhorn: title. and title has a value of google,but i'm not going to
write that in for now. ok, where does body go? >> audience: also coming off of the html. body comes off of here. does everybody see whythat's the case? you should probably be able to figurethis out, too, even if i didn't have this nice indentation. >> the indentation sort of gives it away,but you can see that the head tag has been closed, which means we probablycan't go down here.
we need to go back up to whateverwas right before the head tag, or under that. we're even with the head tag. >> and under body goes form. under form, there are two inputs. that's all i got. quiz 1 is tomorrow. i'm so excited for you guys. it's going to be a blast.
>> if you have-- >> audience: [applause] >> jason hirschhorn: oh stop, stop. but no, i'm kidding. if you have any questions, rightafter section, i'll be outside. if you have any questions tonight,feel free to call, email, gchat, carrier pigeon me. good luck tomorrow. have a wonderful thanksgiving break,if i don't see you before then.
and i will see you after thanksgivingon tuesday for our final section party ever. ok, i'll see you guys nextweek, or in two weeks. and good luck tomorrow.