all right folks uh i think it's about time to get started uh thank you guys for for making it to our problem session and i guess uh talking to many of you guys virtually given the number of people in the room but that's perfectly fine uh right so we're in uh problem session number two for 6006. hopefully you're all in the right place i'm justin uh i think i was looking i was looking at a little spreadsheet of who's teaching what and i think you guys are stuck with me in a lot of these uh problem sessions which actually i think in terms of hours of video means that you're stuck listening to my voice the most uh so sorry in advance uh but but in in any event it's always fun to do this kind of thing and it gave me the opportunity to do homework which i have not done in a very long time um so last last night i worked through all these problems and came up with my own hacked together uh answers these which thankfully more or less agreed with what was in the the answer key which i have and you don't uh i think that we released on so there's a bit of a there's a known bug in 6006 which is that this instructor has horrible handwriting um i'm working on it i went to the classroom and practiced the other day uh but uh in the meantime there are horrible handwritten notes that are posted in the the learning module at least for the duration of the talk today and we'll decide whether we want to leave them up or not because they're not super exciting um just so you can make sure you can follow along with that i'm writing on the board and as with before if there's ever anything that you can't read just stop me and i'll gladly uh fix cool so uh right so hopefully does everybody have a copy of the uh problems it'll look a little different from this the green stuff is the answers i get i get those and you don't uh or sorry i always ask this question when i'm teaching and you never get to answer does anybody not have a copy of the problems in the problem session fabulous okay if you don't there there's a pile of handouts up here here i'll grab one for you um yeah uh great so you know the the basic goal of the problem sessions is to go over a bunch of example problems which i believe are mostly lifted from past years uh homeworks and exams and and you know work through how we went about thinking about them uh and and a solution or at least just kind of sketch out enough that we're confident you could fill in the blanks of a solution given our limited time together um right and of course uh one of the pleasures of teaching this problem session is this is not normally the class that i teach so these really are problems i haven't seen before uh and indeed in the middle of the night last night i woke up and realized my answer to the last problem was totally wrong uh so if you feel that way sometimes the feeling is mutual so in any event there are four problems on your handout that roughly i think are in correspondence with the stuff we've taught over the last week or so so the first problem involves recurrences the second involves infinity stones the third involves uh some kind of a cue stack structure uh and the uh the fourth involves like all kinds of things talking to each other in a way that i got wrong um so i guess for lack of a more creative thing we'll just go through these guys in order uh and essentially this is supposed to be an interactive session although it doesn't really look that way um but since you guys are the people in the room you have the advantage of being able to stop me the second that i a make a mistake or be say something that confuses you and i'm relying on you to do that okay no that's our deal today some kind of acknowledgement noses out of the laptops maybe for a second cool thank you see thumbs up that's what i'm looking for okay all right folks so uh right so let's start with uh problem number one here so problem number one is solving recurrences which is like our favorite way to torture undergrads and algorithms classes in the first couple weeks uh and in particular applying this uh uh master's theorem so i thought i'd spend about 82 seconds reviewing master theorem um because this is sort of the giant sledgehammer uh for solving recurrences without understanding why you got the answer that you did and then for each of these problems uh conveniently this homework problem asks you to do uh each uh big o thing twice right once using master theorem to kind of get you used to just applying this little set of rules which is sort of the most efficient way to solve our currencies it just gives you a formula to look at uh in addition to that drawing a tree of computation and and kind of counting the number of computations you do so the first two are basically straightforward applications of uh master theorem the third one uh requires a little bit of thinking so naturally i got stuck and wasted an hour yesterday trying to convince myself the answer was right okay so uh for a tiny bit of review i know that you also did this in uh recitation but it can't hurt to bring it up again remember that master's theorem uh i believe that master really is just because it's general right there's not like a guy named master but i noticed that it was capitalized a lot in the course notes uh but in any event uh the basic idea is that i have some recurrence that looks uh like the following which is t of n equals uh a t of n over b uh plus f of n right so for instance uh in merge sort uh for a tiny bit of review remember that we kind of split into two pieces so both a and b and merge short would be two yeah and the amount of work that i do in the merge step is kind of like n so that's how to fill in these different constants there and the question is asymptotically what does this function look like and of course that's not totally obvious from this formula because i've defined t in terms of itself right and that's the sort of annoying part of solving recurrences and so master theorem and and i'll let you guys review your your section notes about precisely how this gets proved uh it essentially divides into three cases uh and and the relevant numbers here are as follows right there's an a a b and an f and so the a is kind of like a branching factor right so if you remember your computation tree right like in merge sort you split it into two pieces right so that number is kind of like a it's the number of splits that you make right uh b uh is the amount of that your problem size reduces when you go to each of those leafs then finally f is the amount of work that you do at each note yeah so hopefully that the basic language makes sense uh and then essentially what you learned from master theorem uh is that there's three uh cases the first is that f of n uh looks like by the way in the recitation notes for some reason it's kind of written backward like they give the answer to master's theorem and then the condition i'm going to write in the other order um right looks like the following which is n to the log base b of a minus epsilon for some [Music] positive epsilon i'm going to try to be very conscientious about reading my writing out loud as i write it down all right and in that case what we find is notice there's something kind of magic here which is that this is just an upper bound there's not a theta here so it's okay if if f is below this thing but in any event um the conclusion then is that t of n is big theta of uh n to the log base b of a it's kind of cool if you think about it you only have an upper bound for f but you get a nice a theta bound for t which is pretty cool the reason for that is essentially the f is sort of insignificant relative to the work of just traversing up and down the tree that's case one case two i'm gonna try and leave this on the board as we actually solve these problems is the following which is f of n is big theta of n to the log base b of a multiplied by log to the kth power of n this is like a super weird form but like for example you can it's perfectly kosher to take k equals zero in which case it starts to look like case one right um for some uh positive k or non-negative k rather in which case uh what we learn is that t of n is uh theta of uh n to the log base b of a uh times log to the k plus one of n you can see why we don't love applying this theorem in this course because i feel like just staring at these formulas is like totally unenlightening but it is a giant sledgehammer for solving recurrences quickly uh and then finally case three i'm going to slide the board up and i'm going to slide it back down because i don't want to bend over okay uh is the following which is f of n is omega right meaning that it's lower bounded uh by n to the log base b of a plus epsilon uh for some epsilon greater than zero and we needed a second case uh what's it called a f of n over b is less than c f n for some c between zero and one and what's the conclusion there then it turns out that the f term sort of dominates and what we get is that t of n is theta of f of n [Applause] okay so essentially uh this covers three sort of major cases that you see in recurrences there are other more kind of generic versions of the master theorem out there where essentially rather than just having one term with a t in it like maybe you saw more than one term with a t in it i don't think those are covered in this class i always confuse the name of the more general one i want to say arzela escuoli but i know that that's from functional analysis aquapasi uh theorem um if you want to google that learn more uh but in the event that's going to be enough for for most of the recurrences we care about in double of six so i've at least written our conditions down and now they're gonna sit on the left-hand side while we do three example problems to show how they show up in practice are there any questions about like what this theorem is telling us about life or how to apply it don't speak at once now yes no problem what's the after sum the last line oh for some c in zero one not inclusive fabulous question any others okay so let's uh let's do an example uh problem here um so let's do part a right so in part a they give you a recurrence which isn't all that different from merge sword or or any of the other ones it looks something like this t of n is equal to two t of n over two uh plus and then they have some other term which they don't tell you anything about beyond that it's big o of theta of a big o of square root of n by the way this might mean that it actually does order one work right like it just has to be upper bounded by square root of n that's the only thing the problem's telling you i'm going to keep kind of driving home that point because i think everybody including myself gets really sloppy about like when is it o when is it theta when's it omega and so every single time you write one of those letters down you should like step back 50 feet and look at it and think like did i do that right or did i just write a greek letter right and and make sure that you're actually thinking through it logically okay so um when i apply master theorem in my everyday life what i like to do is to say okay somehow the really key quantity in master theorem is this this this dude right n to the log base b of a right he just keeps showing up in all these different cases so i might as well figure what that is for my recurrence yeah and then plug it in and check which case i'm in does that make sense so let's do that uh so first of all uh what is a in for this particular recurrence two what's b you're killing me guys on three one two three okay the enthusiasm is overwhelming okay and what do we know about the function f yeah it's big o of root n we don't know that it equals root n but we do know that it's at most upper bounded by something that kind of looks like root eric gave me a whole lesson on this chalk and i'm still failing at it okay so uh right so now uh that gives us everything we need uh to compute n to the log base b of a we're gonna do this one real slowly and then we're gonna do the next one a little more fastly quickly so n to the log base b of a well that's n to the log base 2 of 2. maybe an idea what's what's the log base two of two one okay i'll take it this okay right and so then what does uh what does master theorem tell you well in some sense i want to know what f is which in this case looks like square root of n compared to what this is n to the first yeah now first of all which of these two things grows faster this guy right so what do we know is that f is really kind of upper bounded by this n here upper bounded is not quite the right term because big o allows for some wiggle room but like asymptotically hopefully you guys get this concept okay so uh so in particular let's see so so remember that f uh let's maybe just write it again so f of n is big o of square root of n but let's write that in a suggestive way as n to the one half yeah in particular this is equal to big o of n to the one minus one half it's a beautiful thing about one half yeah but what is n to the 1 well that's n to the log base b of a right that's what we just showed here right so this is really o of n to the log b of a that's a complicated way of writing the number one right minus one half and let's give one half a special name too while we're at it let's call him epsilon or her yeah where we take epsilon equals see what i did there now what does it tell me of uh uh there are three different cases of master's theorem and take a look at what i just showed i showed that f n is equal to big o of n to the log base b of a minus epsilon for sum epsilon that's equal to one-half the beautiful thing about one-half is that it is greater than zero yeah so i think we have somewhat laboriously checked that we are in case one any uh dissidence here fabulous okay so in that case master's theorem basically you're just done right so what is the conclusion exactly so t of n is theta of n to the log base b of a but we already showed that's equal to n so we're done all right any questions about how we uh apply master theorem here okay so now so here's the thing about master swim do we learn anything about like what this recursive function is doing no we just like did a bunch of work plugged in some greek symbols and out came a big theta yeah um so what we might want to do instead uh is to use a method that i'm still learning myself because uh i'm not used to presenting it this way but that's okay uh which is to actually draw out the tree of computation yeah so let's actually do that so let's say that i call my function t of n so what does t of n do well in some sense it does work that kind of looks like the square root of n right and then it makes two function calls each of which has n over two amount of data yeah so so let's draw what this looks like so the first thing that my function might do is work square root of n much we put a little square root of n there and now it makes two function calls and how much work does each of these guys do so when it calls t what goes into t n over 2 exactly so it does square root of n over two amount of work at each of these two notes does that make sense okay so now that's determined by the french you have to be careful so the branching number in this case they happen to be the same the next problem we do they'll be different um so they're both two here the outside two refers to the fact that there's two children and the inside two refers to the fact that i divided by two it's a fabulous question because it's exactly what i got wrong when i did this problem okay so now each of these guys calls uh one of their children yeah and so again the data divides by two right so now i have the square root of n over four like this yeah if you're wondering inside of each of these circles it says square root of n over four okay okay so let's say that uh so so now meanwhile in our function call tree here how many nodes are in just like the first level the very top one right this is just this dude yeah one uh node how many nodes are in the second level two or if we want two to the one nodes here there's four yeah which is two squared nodes and so on okay so now we kind of have some pictorial representation of what's going on inside of our uh recurrence if you look at the courses i wrote out i wrote out one more layer just for for fun and profit um so now let's see how this helps us actually solve our recurrence so what do we know how many levels are in this tree well our algorithm kind of stops when the input to t looks like one right so since this divides by two each time uh the tree has a log base two of n levels in the tree yeah and each level does how much work so be careful so uh each level let's call that level l right so we'll we'll say l equals zero l equals one and so on so there's two different things we have to account for when we account for the work in this level right one is the square root of n over two and a single node the other is the fact that there's two different nodes in the level so in level l so the amount of work in level l is equal to the product of those two things right so how many nodes are in level l two to the l yeah okay and how much work does each one of those nodes do it's like n over two to the l yeah so uh a different way of writing that is the square root of n times two to the minus l like that this is just n over two to the l fabulous so now we have everything we need to actually work out our solution to the recurrence okay yes what does that say this is n times two to the minus l i appreciate this i'm gonna i'm gonna work on this more and that's why i also share it online the handwritten notes is what this is literally a scan of the page that i'm holding in front of you okay so if we want the total amount of work in our tree right if we want to account for all of t of n then what are we going to do well we have to sum starting at level 0. i'm using l instead of i because i'm an analysis person and i is the square root of -1 and i don't like eyes in my algorithms but in any event how many total levels are there in my tree well we know that there's log base two of uh n right and now we have to sum this quantity for all those levels right two to the l the square root of n times 2 to the minus l like that okay and then what do we know secretly from from the master theorem is that we we're suspecting that this is going to be theta then right so that's all we gotta check okay so let's let's do that real fast so first of all notice that n here this n term doesn't depend on the cement so i can just pull them out right so this is really this is the square root of n times the sum over l equals zero to the log two of n of uh what um oh and there's a mistake in my uh notes oh man oh no this is oh all right duh okay so you have 2 to the l and you have a square root of 2 to the minus l so this is really two to the minus l over two so you have l minus l over two and this quantity is really two to the l over two like that does that make sense so this is just properties of exponents from from high school class and in fact uh i don't like this because l over 2 and i want to blindly apply a formula without thinking about it and so of course this is really the same as the square root of 2 to the l power right it's just properties of exponents okay so what is this sum called do you recognize this so there's some constant here you're taking it to the elf power and then you're summing it over else this is called a geometric series right so it would be like 1 plus x plus x squared plus x to the third and x to the i guess in this case log base 2 of n yeah so uh conveniently there's a geometric series formula out there uh it's in i wrote it down in the uh the handwritten notes but maybe uh for now because i'm moving slowly as always so we'll skip that part uh and what you could um is as follows that this is the square root of n right that's just this outer part times uh on the inside you're going to get the square root of 2 to the log base 2 of n plus 1. uh minus one divided by the square root of two minus one and this is just the this is the geometric series formula so i encourage you guys to go back home and google that one if you forgot yes okay why are we doing why are we calculating in some of the series because what we're trying to do is figure out the total amount of work in this tree right so what we've done so far we know that a single level in this tree is this value and now we have to sum over all the levels from zero to log base two of n okay and what is what do we use this number for because we're trying to actually approximate or at least bound t of n right and t of n is the sum of all these values oh okay and theta of n is not a sufficient sound it is a sufficient bound we just got it from kind of a boring way this is a second way that we could have proved the same formula yeah i see a question over here um the root n two minus l part i understand the num the two that l is the number of nodes second part oh okay this is the number of nodes this is the quantity inside of the circle so notice that it's square root of n and then square root of n over two and then square root of n over four and then square root of n over eight right so two to the minus l here is like you know one half and then one fourth and then one eighth yeah fabulous any other questions yes and we started indexing uh boy i hate my bad at this stuff uh no right i think this is like this is correct uh let's see so let's say that i have uh n equals two right um then what's going to happen yeah no this is correct so so as a sanity check uh think about n equals two so how many levels should there be it should go from l equals zero and then l equals one and then i'm done because i have t uh and that i think yeah so the log base two of of two is one so yeah so this this formula checks out okay any other uh questions these are all great questions you guys are keeping me honest okay so we have this giant ugly expression here uh and so our final job here is just to simplify it that's it uh and then and then what we're gonna find is that this is secretly just theta of n a little surprising given you know that this is kind of ugly okay and by the way this is just a constant so this term on the denominator is not going to end up mattering for our asymptotic calculation okay cool so let's see here so remember that the square root of two is uh two to the one half yeah so i can do a little bit of reshuffling on our formula and and what i'm gonna find is that this is exactly the square root of n times one over the square root of 2 minus 1 that's just this constant here now i just have to cope with this funny term inside of here i'm going to do the following i'm going to say well 2 square root of 2 is the same as 2 to the 1 half so i'm going to write this by moving that one half upstairs here right so what am i going to get at the end of the day is that this is the same as 2 to the log base 2 of n plus one and all of that uh oops plus one half right because there's a one-half exponent that got multiplied by the one uh minus one all right so this is just an identical expression to this one all i've done is move the one-half upstairs and finally now there's some order in the universe right because what is 2 to the log base 2 of n n exactly very complicated way of writing n so this is equal to the square root of n times 1 over the square root of 2 minus 1 which is just a constant i see your hand i'm going to write and and then i'll catch up with you and now this whole quantity is n times the square root of two right oops wait um oh i'm sorry that should be right because we moved uh we moved the one-half into the exponent i didn't account for it so this is the square root of n uh multiplied by the square root of two um what's that n over 2 times the square root no i think this is right yeah it doesn't make me nervous okay so finally now we can start to see the big o come out right because now we have the square root of n times itself plus some other stuff which is obviously going to grow slower than the remaining terms here so we're good [Applause] if you're wondering the official solutions are actually incorrect they too get this a little bit wrong i'm going to fix that tonight and then we'll post them for you guys uh and this unfortunately is the kind of thing you do a lot of where you're gonna take your tree write down this giant tree formula here write down a geometric series of some sort and then start bounding terms until you get to the expression you want so now you can see why master theory maybe is kind of valuable because it saves you a lot of headache yes um when we write up our presets and we have to write up trees like this and take pictures yeah i don't see why not it's uh they don't have to like draw it in dixie or something oh you can take pictures of diagram songs the math doesn't take yeah i think i think if you're like just writing out your math taking a photo of it and then like backslash include graphics of your photo yeah but just for the figure i think that's yeah like when i write research papers that's how i do it until the final draft yeah okay so essentially what do we just do in this problem which is part a of one problem uh is essentially just show two different ways of solving a recurrence right one is the sledgehammer that's very efficient but not terribly illustrative the other is really working out all of the work that happens at every level of our tree doing a giant sum and then and just actually deriving the the proper formula and both of these are just different ways to skin the same cat is that a weird phrase i don't know okay so uh right so actually uh part two i believe ends up being easier by a funny fluke even though it looks like it's harder uh so so let's do that uh next here so i'm going to leave master theorem on the left-hand side i really want to say master's theorem but i guess that's not right i'm going to leave the master theorem on the left-hand side and just do the problem over here i'm gonna do this one a little bit quicker because i prefer not to spend the whole session on one problem okay but i do think it's worth spending a few minutes going over this theorem and how to apply it carefully because well otherwise you won't okay all right folks it's a workout up here [Applause] so in part b uh we have a version where the branching factor and the amount of the work reduce uh reduces or not the same so now we have to be a little bit more careful in the way that we apply master theory right so now in part uh b we have that t of uh n here is equal to eight t of n over four [Applause] plus and now in the problem they write big o of n times the square root of n we're all grown ups here that's the same as big o of n to the three halves yeah that's this arithmetic okay so first let's apply the uh the master's theorem so uh let's see so what is n to the log base b of a in this case well what is uh b four what is a eight anybody know log base four of eight through wow you're good yeah so this is equal to n to the three house and notice that these two things agree now yeah so which of the three cases of master's theorem are we in the master theorem are we in are we in the first one where like one of these kind of dwarfs the other no we're in case two right where they both kind of behave similarly yeah so this is case two and what is the value of k uh for case two that's relevant here do i need a log factor no these two terms are just the same right they're both n to the three halves so this is case two with k equals zero yeah and in particular immediately we get that t of n is uh let's see we're in case two so we have theta of n to the log base b of a times log to the k plus one of n so you have to account for that term so it's like that that makes sense how we apply to master theorem in that case yes so how do we apply case two of this video how can we apply case two if f n is big o and not big theta well this is coming from a grad student so why don't i ping it back to the to the the students in the class rather than answering myself can you read the question sure so let's say that we just have a big o we don't have a big theta here or is this at least a simple answer which maybe is the one that you're looking for so what do we know in that case we know that f n might grow more slowly than this function but it doesn't grow more quickly than this thing yeah would you ever just be big o instead of b that's exactly right so you can just replace big theta with big o and that's perfectly fine so i don't know if that's the answer you're looking for but it's a at least you get a loose bound this way yeah oops oh i'm sorry that's i i see we're being pedantic okay you can just tell me if i made a mistake it happens i think it's correct in my notes it is okay so the reason our colleague brings it up in the back is that i made a slight mistake which is that this is a big o not a big theta right in which case the only thing i can draw uh down here is that this is also a big o so i made exactly the mistake i told you guys to avoid before yes so then over there those also be videos uh no yeah now i've managed to confuse you all this is correct this entire statement of the master theory i'm assuming i copied it correctly is is right but there's a bit of a difference remember we wanted to apply case two and look at case two so there's a theta here but in the problem in the homework problem they were sneaky and they only said that f of t is big o of something so remember the what's what's the difference between big o and big theta well intuitively big theta says that my function really does look like this guy that like somehow bounded above and below yeah as i go far enough out in big o there's just a bound above right so this is somehow looser and so the way to apply massive theorem in this case is say well at least f n is upper bounded i think it looks like this so the best that i can do is to replace this guy also with an upper bound yeah it's a great question so the reason you chose to use that one exactly you got to kind of stand back and squint out it a little bit make sure that it fits but certainly it's the case that the other two parts of this theorem don't apply we might as well try to squeeze this part into the right floor all right um so let's uh let's do the tree version of this and then i think what we're going to do is skip part three for now of this problem because it's mostly like a fun combinatorial problem rather than something that like actually is going to help your understanding of algorithms and then if we have time at the end we'll come back to it okay all right so that was the easy way to solve the problem now let's do the painful one where we uh we draw the tree i shouldn't say that because i think it's the one we want to encourage the more enlightening version yeah um so now at the top of my tree i do and to the three halves work and now how many children does this guy have careful do you kind of yeah one in two chances either eight or four eight right so the outer coefficient is the number of children because that's like the number of function calls you make right that's the way to think about it right so there's eight of these guys okay and each one of these guys i'm only going to do one level of these by the way that should not be connected uh does how much work well remember that it's divided by four here right so it looks like n over four to the three halves that makes sense how we kind of got this picture from from uh our recurrence let's switch to another piece chat okay so uh right so in other words uh if i look at level l of my tree assuming we're going to index from zero at the top how many nodes are in level l remember it branches by eight each time so it has eight to the l nodes yeah and uh how much work does each do well in each level i divide by four right so it's gonna look like n times one fourth to the l to the three halves right um right where am i uh there we are so that's n times four the minus l that's fancy notation for one fourth to the l uh to the three halves notice that this is exactly the same pattern as the previous problem i'm just plugging in some different some different constants yes the question of the diagram is if you had like a really large a um and you're trying to do the recovery tree method is that this type of um work okay like where you have like if i were grading your papers it would be but i you should probably check with your tas on piazza on that one um but you know i've learned my license uh you know i'm not sure you guys have yet and also i'm not sure i have either all right folks so now we need to do our our total amount of work here right so how many uh how many levels are there in our tree here well the amount of data divides by four each time and when the amount of data is one then i'm done right so the total number of levels is equal to the log base 4 of n the basic thing to get right in in this problem is just where there should be fours and where there should be eights okay so now uh what am i going to do well again as our colleague in the back points out we only have big o so we can only upper bound our work but our work in the tree is less than or equal to um really there's a proportion here because this is just up to a multiple i guess that's why in the notes they put a little c in front um which i can do let's do c like that uh well we're going to have the sum from l equals 0 to log base 4 of n of exactly the quantity uh this this guy multiplied by the number of of nodes in the rail yes is the reason why we made this work the inequality because of the because of the big o that's exactly right yeah okay all right so what do i uh get here well let's write it out the big ugly way first so this is n times 4 to the minus l this is to the 3 halves and then this is multiplied by a to the l but whoever designed this problem is really sneaky right so what's four to the minus l to the three halves any guesses yeah this is exactly eight to the minus l if you work through all of your exponent arithmetic yeah why does that matter well it exactly cancels this eight to the l term here this is actually exactly what case two in master theorem is kind of trying to capture so this whole thing is equal to of uh really just n to the three halves from l equals zero to the log base four of n all these constants just go away isn't that beautiful yes um good question no problem uh-hum so do people ever use these for like optimization in terms of trying to write a better algorithm like try to minimize the work per per level yeah i'm just curious if that's like a application that sure i guess so i mean this is somehow a visualization of how your algorithm is making function calls right so like every node here kind of looks like a call to your piece of code right so every time you make a new one it's like making a call and then the divide here is kind of like how much data goes into that function call so i think this is a useful way to kind of visualize what's going on inside of your code and then if you're trying to optimize your code you're trying to basically reduce the number of nodes and or the amount of work that each node does right yeah so this is just like a nice way to kind of visualize what's going on in a recursive algorithm yeah great question all right so here's a here's a really nice thing does n to the three half depend on l no right so this whole thing is equal to c times n to the three halves and my colleague in the back is going to catch me if i don't if i don't make the off by 1 error here so uh this is log base 4 of n plus 1 because my sum started at zero yeah and notice that this is exactly big o of n to the three halves log n which agrees with what we did in a much more easy case with the master theorem that make sense yeah so we found an exact balance so could we say that it's theta of n oh great question this is where this notation is going to be misleading this expression in a vacuum is theta of this value but the reason that i wrote big o is because i only have an inequality all the way up here so if i'm worried about bounding this work there's no reason to write a theta there because it's just telling me some kind of intermediate piece of information yeah okay fabulous so uh yes does the base of the log matter ah this is a nice formula here um so remember that log base b of a is the same as log a over log b if i got that right yeah so the base of the log when it comes to big o doesn't matter because it's just a constant factor yeah okay so that's part two of this problem part three is a little bit annoying because it has two branches in it i wrote out a careful solution um it does not apply the master theorem because it's irrelevant at least the version that we know in this class um so we're going to kind of skip that for now because i don't think it's terribly relevant to most of the algorithms that we'll see in 6006 but we'll come back to it if we have time uh yes can we make that a lower bound and an upper bound using master's theorem using knowing that t of n over four are smaller than t of n over three i'm gonna refer you to the solutions rather than talking about that problem uh right now yeah uh okay cool all right so that's how you apply master theorem which is mildly painful the good news is the rest of this problem set is actually i consider it to be much easier than the first one which is why i think it's okay to spend a little bit extra time here because i think this stuff is confusing to get right mostly for me and hopefully i've conveyed my confusion to the rest of you okay so let's uh erase this and while we're doing that why don't you guys all give problem number two a read so one of the big skills that we need to cover in 683 not 6837 6006 uh is uh the and 6837 but i'm not quite as evil about it in that class is as follows which is you read a problem and for some reason your instructors have some sick sense of humor and they encode it in this totally weird goofy language which somehow to a theoretician makes your problem feel more practical um so in any event uh you know when you read all of this paragraph the very first skill that you have to do is to figure out like okay like this is cute notation it's about infinity stones and if i watch star wars or whatever i would know what that was what that meant but um in any event uh what really matters is understanding like okay but algorithmically like what are they asking yeah so i'm gonna try and talk about this problem as i erase the board so i believe um what like mickey mouse or whatever has a bunch of uh it's like some planet that he's looking for uh i'm gonna open the problem now and uh right she's a super villain on a quest she's looking for a stone on a planet and the planet has some index k and unfortunately for us there are the number of planets is is quite large it's infinity in fact because it's the infinity stone um or sorry did i say that i think it's the infinity phone or something i i forget but but in any event um the only thing that you can do when you land on a planet is ask an oracle is the index of my planet bigger or smaller than the index of the planet that i'm standing on right and then the question is in log k time where k is the index of the planet notice that's already a little weird because it's like not the size of your data quite um can you find the the planet now what does this kind of problem like what is it screaming out for you to use like you see a log k you're looking for something by section right or binary search that's absolutely right those are both great answers but there's a bit of a problem which is that the number of planets is unbounded we don't know how many planets there are in um this this little universe that problem 1.2 sets up yeah so our intuition is that we want to use binary search but in order to do binary search i need to have a left and a right hand side and divide and i have no right hand side so what can i do how's a how's a super villain to solve this problem well remember that each planet has an oracle on it telling me like is there something to my left or my right yeah so i could start at planet number one and i could just start walking from planet one to planet two to planet three planet four and asking like am i there yet am i there yet how much time is that going to take potentially actually it won't take infinite time i got you how much time will it take when will i stop when i hit planet k right because i know that planet k is out there somewhere the truth is out there and when i find it and i step on it i stop and i took exactly k steps maybe k minus 1 depending how you count but we need a log k algorithm yeah so what could i do um if you start at some k then right you can multiply by another case multiplied by another k it's actually like proceeded by another k minus yeah so okay so you got the right you're the right church wrong pew here so the the basic intuition here is that stepping one planet at a time doesn't step fast enough um if you work out the details in that one you're going to find that you'll end up with a run time that still grows a little bit too quickly in in in k here right in some sense you one way if you were to reverse engineer this problem which isn't really a great way to problem set you really do expect there to be powers of two in every step of your algorithm yes the binary search of like start in the middle and [Music] this is the right intuition but there's i have a philosophical question for you which is what is the middle of an infinite set of planets infinite exactly that's a problem yes um we could use like um i don't know who it was back there who was suggesting using doing i squared verbs instead for doing i squared replace it with 2 to the i that's exactly right that's a great intuition so let's let's formalize that a little bit which is like i could do binary search if i had a right-hand side i have left-hand side because it's one so what i'm going to do i'm going to keep trying right hand sides and the oracle is going to tell me is this a valid right-hand side right because the oracle is telling me is there a planet to my left yeah so here's what i'm going to do again i don't like the index i in the official solution there's an i but i use the letter m because i can um which is the following i'm going to visit i hate teaching no that's not true i like teaching i just don't like chuck um i'm gonna visit planet two to the m for each m um you know starting with m equals zero from and uh essentially until uh remember that k is the index of the planet i'm looking for so eventually i'm going to reach the point where k is less than or equal to 2 to the m and i know that i can query my oracle and they're going to tell me when that's the case so how much time does this take right so i'm going to try planet 1 and then planet 2 and then planet 4 and then 8 and 16 all the way up until k so it's going to take log k time yeah you also have a stronger lower bound now to that minus one yeah that's sort of right so so right so eventually what's going to happen when you stop here is that 2 to the m minus 1 is going to be less than or equal to k less than equal to 2 to the m right because then then because this is the condition for stopping this is the condition for not stopping so when you stop k this little sandwich is true yeah so if i take the log essentially what i've shown is that i've taken right because m is like the number of steps in this part of my algorithm so if i take the log i'm going to find that i took log k steps yeah now that's acknowledgment yeah okay uh and then well now um now i have an upper bound and a lower bound so now what can i do yeah now i can binary search and that also takes log k time that's exactly right oops so now i have step two is also binary search and it's also a log k time and our problem is solved so problem number two is not so hard anybody with me any questions about that one that's a quick one okay now problem three really spoke to me as a computer graphics professor so uh right so now i am running for dobie um i have some i've collaborated a lot with adobe free search um right so uh fidobi is trying to make a piece of software uh for image editing and what does my piece of software do well uh my my uh my image or i guess my document consists of a bunch of images that are overlaid with one another okay and essentially what's happening inside of the software is i want to keep all the images in order from like top to bottom okay because when i render uh my photo what do i do i render the bottom one and then the next one and so on and just layer them on top of each other like if you've ever played with powerpoint or photoshop or i guess whatever fake name they're giving here that's a pretty common uh user interface to encounter and so what they've asked you to do is to come up with essentially a data structure and your data structure has to support a few different operations in particular you have to be able to make a document import an image and then stick it on top uh display which returns all the ids in the order uh that you store them and then there's a real kicker which is that you need to be able to take one of the the thing one of the layers and stick it underneath another one but you have to do that in log in time it's that butt that makes this whole problem kind of a pain in the took us yeah uh so right so again uh here are operations we've got to make an empty dot this is supposed to take order one time we're going to uh import which adds an x on top and that this should take order end time notice that this is already a little suspicious if i were like trying to psychologically diagnose my my professors i would look at this this order end with some like with a raised eyebrow right because probably like what would you have in mind if you're like talking about stacks of photographs would be like a you know a stack or queue or some data structure like that but then insertion would be like order one time you know so there's clearly something a little more complicated going on okay uh what's number three is um display uh this has to happen in order end time this one kind of makes sense right because in order to display n things you kind of expect to take at least end time uh and then finally we have to move below and this has to take order login time uh and this is going to be the kicker right because we really uh this is this is somehow not totally obvious from from the way that we set up our problem so everybody understand the problem set up so far we just keep adding objects with ids and we need to be able to insert them on the top and then kind of reorder them and the problem has given you run time for each of these different operations okay right so here's the thing there's like kind of a sequence aspect to our problem and kind of a set aspect to our problem does that make sense like the sequence aspect to our problem is that we're going to have to display stuff in order end time right we've got to iterate over our whole list put stuff on top and so on and the set aspect is that we'd like to move stuff on top of each other in log end time and the reason that i say that this is somehow set aspect is that i need to be able to put any x underneath any y which means that i need to be able to quickly find what layer the x and the y is in any ideas how we could solve this problem how about some from some folks i haven't heard from you yes yeah that's a really great idea so maybe i'm going to maintain so remember we've talked about uh let's see in in my lecture two lectures ago we kind of thought of a sorted list as like a set data structure so yeah so that's that's a fabulous idea why don't we for the set part of our problem we're going to store in particular a sorted array of uh and for now let's think about like a sorted array of x's and so this is going to be able to help us answer questions like you know is this id in my my set of images or not but there's also going to be a second part of my problem which is in addition to that i need to be able to keep a different ordering other than being just ordered by x which is the ordering that they're being like drawn on the screen right that's different than the ordering of their ids so for that um good question we're gonna be building a sorted array with nothing in it and it's gonna be o of n log n time but that's undefined so we can we actually go to this one we're gonna write it with nothing hmm okay uh no i'm not sure i quite follow uh um it's uh building an empty sort of array of n log n time which is o of zero log zero time and log zero is entered array yeah building an empty anything takes one time oh yeah okay cool cool all right uh so in addition to this we have a sequence aspect of our problem right and for that uh maybe we'll use a linked list right that's a pretty reasonable sequence uh uh data structure and in fact let's think for a second now we're gonna need this move below operation right so our links list is gonna store the order of the images in our document in order to move something below something else we're going to kind of splice an image in between two other guys so for convenience maybe we have a doubly linked list so that we can like move backward and forward so that we can insert stuff yeah so we'll have a doubly linked list okay right so let's start uh solving our problem and then uh thinking about where uh things are gonna go wrong here uh with with our setup here so first of all i don't think we really have to write anything for the for for part one because making an empty anything is a pretty easy algorithm on your homework of course you should write that and tell us that it takes order one time now how about uh importing an object remember so that puts it on the top of the uh it puts that on the top of our linked list and we have to insert it into our sorted array right so when we do that [Applause] our insert algorithm is super simple right we're going to add x to the set which we talked about in class for a sorted array how long does this take for a sorted array to add something exactly order end time but that's actually okay because wait that's our criterion for number two yeah and in addition to that uh we'll put x on the top of the the linked list right let's order one time that's easy i'm adding space because we're going to see that we made a slight mistake and that we're going to need to modify our algorithm a tiny bit to solve this problem okay so how do we uh how do we display i think that's the simplest one right i'm just going to iterate over the entire linked list and just one by one output the order because remember the whole point of the linked list is to keep track of all of our documents in in order huh so uh display all you have to do is loop over the linked list okay and the real kicker is the last part right which is how do you move something below so so let's think for a minute what what's what's moving below going to entail so is it going to affect the set of keys that are in my document no actually right they're just changing their ordering but both of those keys were already there yeah the only thing it's going to do is affect where they are in the sequence but there's something really really annoying how do i find something in this sequence like let's say that i tell you the document 75 has to move below document 352. well so far in my data structure what's my only option does the set tell me anything about where stuff is in the links list no so how much time is it going to take for me to find a key order n right because i've got a link i gotta loop over this whole linked list and and find the item that i'm missing is that allowed no the problem tells me that i have to do this in order log and time so somehow on our head we should be thinking like okay we're gonna we want to kind of use this set here to help us find stuff in the doubly linked list does that make sense that intuition so here's how we're going to do it actually before i do that any any ideas how can we solve that yes [Music] that's a fabulous idea so here's what i'm going to do remember that when we make a set we don't have to store the keys we can attach data to our keys yeah and in particular i am going to attach a pointer into my linked list it's a really sneaky answer yeah so let's say that i have let's do a quick example so let's say that i have my documents are one five three two and seven like that so my linked list is gonna be real simple it's doubly linked see there's two arrows here just like that right and now my sorted array is gonna store all the keys in order let's see if i can do this with me one two three five seven all right so this is my this is my linked list and here's my uh sorted array is going to be one two three five seven but then what i'm going to attach to each of these guys is a pointer to the element of the linked list right so he is going to additionally contain an arrow here the two will contain an arrow there the three will contain an arrow there the five uh this is ugly i'm sorry now here's the thing let's say that i remove this three here does that actually affect seven's pointer no right so these pointers remain valid even if i like edit other parts of the list really sneaky trick okay so that is going to be our solution to this problem is to store not just assorted array of x's but x's and pointers so now we have to modify a tiny bit you're right and now uh what can we do to move something below well it's going to happen in sort of three steps right so our first step well we gotta first find keys x and y right so we're gonna find x v x and y v e y in the set how long does this take well now we can do it in binary search right exactly so this is like oh like that and now uh what's my next step well remember the move below operator sort of removes x from where it currently is and then puts it underneath y right and both of those are like linked list editing operations right so i'm going to kind of like you know if i have a linked list like one two three four right and like let's say i want to erase the two right i think you guys have all coded this up at some point in your lives then like what i'll do is you know add links like that which i can do because i can move forward and backward in the list right and similarly if i want to add something then i'll like erase the links put it in there and update the links how much time does that take let's just order one time right because now that i have the pointers to these two locations i'm just kind of like doing a lot of rewiring in my my linked list but it's all kind of local stuff if you're coding in c this is where your memory leak happens and your company gets hacked okay so uh right so that is uh what we're gonna do next is update the linked list and that takes order one time on your homework if you're writing out your answer you should have an answer closer to what i've written on my page than the two words that i've written on the board here and then finally in step three well actually there is no step through the way written in here sorry if we think of there there's actually two sort of parts to updating the linked list right one is to remove the old x uh position and then insert in the proper position right and when i do that my whole uh my whole update happened notice that there's something kind of interesting about this move below operation which is that did i actually edit the set at all no right that kind of makes sense because the set is just a set of keys in my document and just by changing the ordering it doesn't affect what's what's in my document so somehow it was a sanity check that that works out so this entire algorithm takes how long well there's order log n there's order one and there's another order one so the whole thing is log n and life is good for our problem here yes um so how can we input such pointers in real life how do we input such points like a set with pointers in real life got it so i only know the c plus version of this i'm going to get it wrong for python um but i'm not sure that i quite understand the question so it's just like pointers anywhere else in real life uh so i guess in in in python you know um what you'll do is you'll create a new right as you add these guys to your set you'll create a new object here and in addition to that you're going to create a new vx that you add to the linked list and then the pointer is just an address in memory right so essentially what you'll store notes are the are the second l the pointers are pairs they're a pair of an x value uh and a oh i'm sorry yeah actually i guess this right um no the linked list just contains a long list of x's right um but they don't have to be in contiguous memory that's the only difference so you make them one linked list item at a time but it's just like constructing any other linked list yeah in fact there's pseudo code in the uh the solutions that are are distributed so you can take a look there yeah speaking of which um for these for like implementing these database operations can we pseudo code the like algorithms for them i think the official answer is no that you really are supposed to write out in words what your your thing is doing now there's a weird gray area of course which is that the words that you write are going to look an awful lot like pseudo code but uh you you should make an effort to try and write down a little bit in paragraph form and b be descriptive about it this is a good skill to learn at the beginning of this course i think it's it's it'll feel a little pedantic at points and and that's good because it should and you should deal with it yeah no but really yeah try and write things out in a way that like captures your logic rather than just like python code yeah cool all right so let's see we've got we've got approximately 17 minutes left in class which is approximately one-eighth of the time it took me to figure out the solution to this last homework problem but we'll get started uh and i've written out a careful answer um because essentially in problem four i found myself getting stuck in a few little details and so i figured the way that i'd write out my little hand scribbled chicken scratch answer online was to just basically give you an internal dialogue of my brain and how i went about solving these things and all the stupid missteps that i made yeah um because i think that's actually quite valuable essentially it's often you see in these problem sessions just like oh here's a problem here's the answer here's a problem here's the answer but the reality is even your professor especially because he's used to thinking about rendering um occasionally gets confused about these these algorithms problems especially when they're frankly written in a bit of a confusing way uh and i heard some some war stories about this problem actually being on the homework apparently i i'm in good company so let's take a look at this last homework problem 1-4 so this is on brick blowing and this is a great exercise in taking a problem that is described in really long nasty useless language and then extracting like the two words that matter um by the way like i'm making a joke about that i can tell you that about 82 percent of my time as a professor is spent with like people from industry visiting my office with exactly this kind of scenario where like you know they have some really complicated thing they've been thinking about their you know construction problem for like years and they have all these details and tables and flow charts and then it turns out that their problem is like can be captured in about two sentences but so it's a good skill to have and one that can get you a lot of money as a consultant so it's one that's worth practicing in this class even if we're doing it for pork pork land with a wolf that blows only to the east okay so what's going on in this problem there's there's a wolf and the wolf can blow on houses but for some reason um the wolf likes to blow to the right and to make matters even more complicated whoever wrote this problem occasionally ordered things from east to west and other times ordered them from west to east if i were instructed of your instructor at the time that i would have at least gotten rid of that's just that's just mean um but in any event i believe the story goes as the apocryphal uh uh uh houseblowing pork wolf uh story that we all know and love from our childhood is uh there's a row of houses each of which has a different number of bricks yeah and now there's a wind which is blowing from west to east i remember all this because i was staring at it this morning in my office and essentially the wolf being the the big bad wolf that he is says aha if i to blow from west to east i can knock over more houses more efficiently yeah because i'm the wind is helping me you don't want to blow into the wind it gets you know you're spitting your face okay so uh the wolf does that and then what happens is that the wolf not only knocks down the house upon which the wolf blows but also all the houses to the east of that house that have fewer bricks why you might ask i don't know because whoever wrote this problem was being a goofball but that's the basic setup of this problem and you can see that essentially this is just a long convoluted way of describing something pretty straightforward yeah and so at the end of the day the wolf being kind of an adversarial uh wolf wants to blow down as many bricks as possible and we are providing the wolf with the analytical tools needed to do so yeah so in case you didn't think we covered anything practical in 6006 uh now you know that we we actually are doing state-of-the-art wolf brick blowing pig analysis okay so uh right so let's uh let's do an example because this is like weirdly complicated so the first part of the problem asks you to just do an example out and i think if i were psychologically diagnosing the person who wrote this problem probably the reason is that they stood back and they said nobody's going to understand this unless i force them to do an example by hand right and so the basic problem is asking like you know i could choose to blow on each house which one should i choose to cause the most damage or in fact they actually ask a slightly different problem which is if i were to blow on each house how much damage would i cause okay so let's step through the problem so they give you an example uh a set of numbers 34 57 70 19 48 actually let's just stop there i don't think there's any reason to do like a list of a million numbers like in the problem that was just like you know the more times you do it the more you convince yourself how useless 6006 is okay so so uh right so so how much damage does blowing on house number one cause well let's make a little table so if i blow on house number one just by default house number one false i'll pull x there meaning i blew it over and then the rule is any house to the right which has fewer bricks the physics of this problem drives me nuts i thought about it for quite a long time and i i can't think of a wind that actually has this property uh but any house that has fewer bricks and is to the east also gets blown down so 57 does not right that's bigger than 34. similarly for 70. aha the 19 goes with the wind uh 48's bigger and the two goes right so the element number one of my array would be three right three things get blown over okay for the next guy right so the 57 gets blown over it does not blow over the 34 because my wolf only knows how to blow to the right uh so it does not blow over the 70 it does blow over the 19 doesn't blow it does move over the 48 it does right so here there'll be a four these numbers do not match the ones in the notes because this is a shorter list of numbers i should point out okay let's do one more and then we're going to stop because this is laborious and boring so the 70 blows over everything yeah but only everything to it's right because as we all know holes only blow to there okay i'll shut up uh so there's uh there's four uh there's four things that get blown over here but you guys get the point right and so essentially this problem is asking you to fill in arrays that look like this for your problem everybody on board with the problem now notice that just by virtue of doing this example let's think about this abstractly because i think this is a problem that's just coded in so many words and made up like weird ta garbage but like at the end of the day like this problem as an algorithmic problem is not so bad right essentially what i'm asking you to do is i look at that 57 and i look to the right and i count how many things are smaller than 57 and i add one to it and that's the number that should go in that element of the array so notice that like those three paragraphs that's what they're communicating you didn't need like wolves blowing and winds and and trees and houses and dorothy and all that kind of stuff yeah so uh right so so at the end of the day that's the problem we can think about and we no longer have to think about pork land ever again okay so maybe in the in the remaining 10 minutes here i think we can feasibly do part b uh and then part c is a sort of an extension of part b i got myself confused on part c so the handwritten solutions have an incorrect answer and then an oops and then a correct answer in it so you can see where my logic went wrong to be fair i i wrote i already knew the full answer and wrote out both because i thought that it was useful um okay so in case our our problem wasn't contrived enough we're going to add a little bit of condition to it and then what we're going to see in part c is the that's somehow a stepping stone towards solving the bigger problem so in part c they say that a house in in pork land is special if it has one of two properties either it has no easterly neighborhood neighbor meaning that's just like the rightmost house yeah or its adjacent neighbor to the east contains at least as many bricks as it does right so what does that mean in terms of this list of of numbers which one of these guys is is special so the easterly guy is special we just know that by default and other than that this special property is saying that the guy immediately to the right has a bigger number than the guy or at least you know equal to or larger to the one uh right before it yeah so 57 is bigger than 34 so this guy's special by the way the problem doesn't ask you to do this on the example but i totally would if i were solving this yep um 70 is bigger than 57 so it's special 19 is smaller than 70 so it's not special i'm sorry uh 48 is bigger than 19 and i guess two is special just because things on the right are special okay so do we all get the definition fabulous so in this problem now what we're given is that i guess uh what our our evil uh wolf takes a walk down the block and takes a look at you know counts the number of bricks at each house and he or she makes an observation which is at all but one house is special now let's think about what that means let's think about the structure of our array so what happens as i walk along my right if the house is special what do i know about the next house get blown if you blow a special house down that's true but we're already solving the problem they're listening qualitatively for a second like just in terms of the number of bricks right i'm walking down the street i'm looking and the number of bricks increases until i get to the one house that isn't special and then it decreases potentially or it's the last one and then it starts increasing again yeah so in other words my array kind of looks uh like the following which is that it's basically has two different pieces that are both sorted yeah that's what this long paragraph is saying is saying suppose that the list of houses is sorted except for one thing yeah that's how you could have said it okay so uh here's an example so maybe we have one two three four and then i don't know two three four five so all of these is special with the exception of this guy sadly for him and so uh there's kind of like a little dividing line that happens to the left of which it's sorted into the right yeah okay and then the question is can we predict the damage for each house uh based on this information um so i want as output to my code an array that says like this guy causes so much damage this guy causes so much damage and so on and i want to get it in order end time let's think for a second so yeah we're going to do that so order in time means that i can't do i can't afford to do like sorting and all that kind of fancy stuff right so basically all i can do is kind of walk up and down the array so we should think a bit about like what's special about special oh you say uh what's special about this configuration that we wouldn't normally have anything before the non-special node should have the same or not sorry anything not quite everything after the non-special node causes only one damage yeah so so let's think about this carefully i think that's right but i i'm bad at parsing sentences um remember that i always blow to the right and i only blow short stuff so if i blow on uh like this two here will anything before that vertical line ever get blown over no because by property of being special we know that the list is increasing but it has to decrease to blow something over that make sense so for each one of these guys the only stuff you can blow is in the second array does that make sense so we made an observation notice that it is special to the structure that we gave to our problem yeah and moreover so in both parts of this problem we're going to kind of look at two parts of an array and then merge them together in a smart way let's look on the right hand side does any of these things like if i blow on any of these houses what's the damage that i do what you see that because this is an increasing list i only blow to the right and it has to get shorter yeah so for what partial credit on my homework problem probably very little partial credit but you know spiritually it's half of your credit um we know the second half of my array is just a bunch of ones incidentally one detail which i bet would get a minus one on your homework we didn't tell you that all we told you is that there existed one house that wasn't special but we didn't tell you which one but notice that i can find it in order end time right i can just walk along my array and find the first place where it decreases and that's the special house yeah so i can kind of assume that i know where this line is that's that's that's kosher so then the only question is how do i fill in my array here right like how do i count and so so let's think about this mathematically because how like porks and blowing and stuff is kind of confusing so let's think about it in terms of this array essentially what am i trying to do so for this two i'm trying to look in the second half of my array and find all the numbers here that are less than 2. right that's essentially what this problem is asking you to do you see that okay i'm going to make one so here's a simple kind of n squared algorithm right which is i could iterate over every item here and just loop over here and count the number of things that are less than that right that's a double for loop each of which could be up to n so that's n squared those against the rules can't do it so we need one more additional observation okay let's think about this for a second let's say i'm the wolf the pork blowing wolf and i walk from one house to the next and i keep track of what houses get blown over here now what happens as i walk from one house to the left on the uh to one house to the next on the left-hand side they're only getting taller right that's what it means to be special so the houses that get blown over here the set of those only grows larger does that make sense right because as these guys get taller more stuff falls over on the right hand side it's like a total goofball talking about this problem moreover these guys are in sorted order yeah so what's going to end up happening is that always there's just some interval of houses that gets knocked over so for example the four goes over the two and the three i guess notice that that always starts on the left-hand side and that's because these guys are sorted right the three just blows over the two which is kind of a subset of the four this isn't a great example because those first two guys don't blow over anything that makes sense any ideas how could i use that observation to make an order n algorithm for counting blowiness damage heard a lot from you let's hear from some of our other colleagues here another person yes binary search tell me more what would i search for so let's say you have four and you will buy your shirt for the ride it's an interesting intuition and it's like 82 right so uh the the to repeat our colleague suggestion which is a good one and we'll make your code a lot faster in fact in practical terms would probably be about the same would be i'm going to move from the left to the right-hand side unless there's a very large neighborhood of pigs i'm going to move across this array i'm going to binary search this other side and find sort of like the first house that shouldn't get blown over or something and now i know that the total number of things that get blown over now unfortunately for you what's the wrong time of that algorithm n log n right because for every single guy here i incur a binary search there which is log n time so you're in the right church wrong pew here but there's an observation we haven't used yet which is as i move to the right these numbers increase yeah so what's going to happen to the index of the stuff that gets blown over it's always going to move this way is it ever going to move to the left no so there's a term that we used in the two lectures ago which is a term i never heard before but i kind of like it it's called a two-finger algorithm yeah what does a two-finger algorithm do looks like this two fingers yeah so what i'm gonna do is i'm gonna keep my finger on the right pointing at the very first thing that doesn't get blown over okay so here right the one doesn't blow over anything so it stays here i'm going to iterate to the next guy does the 2 blow over anything no by the way the problem is written now i'm going to move this guy here well now the 3 blows over the the two here so i'm going to move my right finger one thing to the right and move the guy to the four the four also the lower or anything and then i guess i'm done but the basic point here is that i'm always going to be incrementing two different pointers and moving to the right and so what am i going to do i'm going to if i call this finger i and this uh finger j will i or j ever decrease no so if my algorithm is looping over all of these guys and they only ever touch each of these indices once i'm going to get an order n technique yeah and that's going to be the basic trick to solving this problem now i've managed to talk myself out of time but basically that's it so what i'm going to do if we have 10 extra seconds is i'm going to initialize essentially for each eye i'm going to increment j until the number of bricks at j is uh greater than the number of bricks at i because that should be greater than or equal to right and the reason to do that is that now the number of houses that get blown over is just this index j minus the index of the first guy right and then i'll increment i and and continue that make any sense fabulous so i managed by some miracle to make it to almost the end of this problem set minus one part of one problem of course that's the hardest part of the whole problem set uh but there's an answer written out where essentially now the question is can you do exactly the same algorithm but i don't give you this special assumption right that it increases and then decreases and it's going to be basically an extension of this idea as we're going to use this plus a little bit of merge sort okay so with that we'll see you guys next week it's always a pleasure and yeah have a lovely weekend