Transcript
the following content is provided under a Creative Commons license your support will help MIT OpenCourseWare continue to offer high quality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu everyone today we are going to look at dynamic programming again so I think I have mentioned several times so you should all know it by heart now the dynamic programming its main idea is divided a problem into subproblems and we use the results of the problems you've already solved right and of course in 604 6 we always care about runtime so those are the two are our big themes for dynamic programming now let's start with a warm up example it's really simple let's say we have a grid there's a robot from say coordinate 1 1 and it wants to go to coordinate MN so at every step it can only either take a step up or take a step on the right so how many distinct paths are there for the robot to take is the question clear so we have a robot at coordinate 1 1 it wants to go to coordinate MN and it every step it can either take a step up or take a step to the right how many distinct paths are there that can take the robot to its destination any ideas how to solve that but problems as at some point yeah yeah yeah does that one get that so it's very simple I know I have only one way to get to this points why I need to go all the way right and only one way to get to these points I need to go all the way up so for all the intermediate nodes my number of choices are discarding just a number of distinct paths I can come from my left plus the number of distinct paths I can come from bottom and then I keep going for every node I'll just take a sum between like the two numbers on my left and on my bottom and go from there okay it's got clear so this example is very simple but it does illustrate the point of dynamic programming very well as you are use of subproblems and ask how many distinct paths can I come here and you reuse the result of for example this subproblem because you are using it to compute this number and that number if you don't do that if you don't memorize and reuse the results and while your runtime will be worse so what's the runtime of that let's pick up it's just an M times n right why because I have this many unique subproblems one at each point and and I'm just taking a sum of two numbers at each subproblem so it takes me constant time to solve to merge the results from my cell problems to get my problem so to analyze run time usually we ask a question how many unique problems do I have and what's the amount of merge work I have to do at every step that's the toy example let's look at some more complicated examples our first one is called make change as its name suggests we have a bunch of coins as one as to all the way to say SM so each coin has some values like 1 cent 5 cent 10 cent and then we're going to make it make change for a total of incense and ask what's the minimum number of coins do I need to make a change event and cents so to guarantee that we can always make this change will set as one to be 1 otherwise there is a chance that if the problem is solvable any ideas oh it's the problem clear go ahead what least these numbers they are input they are also inputs it could be one seven five seven ten cents or three cents seven cents though the smallest one is always one okay I need to find a combination of them for each of them I have infinite number of them so I can find two of these three of those five of that two such that their sum is n is the problem tree okay any ideas how to stop that let's just use naive or very straightforward algorithms god okay great yeah let's just do exhaustive search let's pick si if I pick this coin then my sub problem becomes n minus the coin value right and of course I use the one coin right that's a tie so then I take a mean of this for all the ice and that's the solution so far so good okay so what's the runtime of this algorithm it's not immediately obvious then we ask how many unique subproblems are there and how much work do I have to do to go from my subproblems to my original problem so how many subproblems are there so to be clear for this one we have to call this recursive core again right and - si probably - SJ and if you cannot compute how many subproblems are there let's just give a bound any ideas jump right I yeah correct so this may not be a very tight bound but we know we cannot have more than this number of subproblems right actually I don't need to even put the order there I know we can have no more than n subproblems they'll just make change of N and minus 1 and minus 2 all the way to them to make change 1 and actually this bound is pretty tight because we set our smallest coins 1 so we will make a recursive call to make change n minus 1 right if I pick the one coin a one-cent coin first and then from there I will pick a 1 cent coin again that gives me a subproblem but minus 2 so indeed I will encounter all the n subproblems right ok so having realized that how much work do I have to do to go from here to there Yeah right right because well I'm taking a mean of how many terms M terms so that's all run time any questions so far okay if not let me take a digression so make change this problem if you think about it it's very similar to knapsack as anyone not proud of this problem knapsack means you have a bunch of items you want to pack these into a bag and the bag has a certain size and you want to sew each item has a certain value and you want to pack the items that have the largest combined value into your bag so why is it why are they similar because if so in some sense n is our size we want to pick a bunch of coins to make the size N and each coin here actually has a negative value because we want to pick the minimum of it if you do that then this problem is exactly knapsack and knapsack is np-complete that means we don't know a polynomial solution to it yet however we just found one right this our input is and stuff and then our solution is polynomial 2m and polynomial to the N right if this is true then I have found a polynomial solution to one NP problem so P equals NP so we should all be getting Turing Award for that so clearly something is wrong no but there's nothing there's no problem with this solution right this covers all the cases and our analysis is definitely correct so yeah does anyone get what I'm asking so what's the contradiction here we'll probably discuss this later in later lectures when we get to complexity or reduction so but to give a short answer the problem is that when we say the input is n its size is not n so I only need log in this to represent this input right make sense therefore for log in length input my runtime is n that means my runtime is exponential it's not polynomial okay now that's end of the digression okay now let's look at another example this one is called rectangular blocks so in this problem we have a bunch of blocks say 1 2 all the way to N and each each of them has a length width and height so it's a three dimensional block so I want to put blocks stack them on top of each other to get a maximum height but in order for J could be put on top of them I require the length of J could be smaller than length of I and width of J is also smaller than with a pie so visually I just meant so this is a block I can put another block on there right they are smaller in width and length but I cannot put this guy on top of it because one of them one of its dimension is larger than the underlying block and to make things simple ah that's not allowed rotating so okay I can rotate it now it's still doesn't fit but you see the complication sorry that you allow rotate then there's more possibility so L and length and width are so one of them is north/south the other is east/west you cannot change that okay is the problem clear we want to stack one on one on top of each other to look at the maximum height any ideas again let's start from simple algorithm say let's just try everything out okay go ahead funny you're going too fast let's write the algorithm first so I want to solve my rectangle block problem say from 1 to N what are my subproblems okay that's true as one block so I get his height and then I have a sub problem what is the sub problem and then I'll take a max Y right so the difficulty here is ah this sub problem so Andrew right so Andrew said it's just everything except I is that a case go ahead right you get that yeah not only with we have to exclude I we also we also have to exclude everything longer or wider than I so that's actually a messy problem so let me define now this uh broad problem to be a compatible set of Li and Omega s sorry WI and let me define that to be the set of blocks where the length is smaller than the required length and therewith sorry it's also smaller than the required width so this should remind you of the weighted interval scheduling problem where we define a competitive compatible set once we have chosen some block question Optum up maximize h we want to get as high as possible I choose a block I get its height and then I find out the competitive remaining blocks and I want to stack them on top of it okay everyone agrees this problem this solution is correct okay then let's analyze this runtime so how do we analyze run time what's the first question I always ask yeah I not sure who said that but how many subproblems do we have at most an can you explain why is that case it's just a gas and if the compatibles nothing in the canal and will not be in the compatible okay that's very tricky I didn't get that can say I can like you to start with and then everything that's in the compatible set and won't be in the comparison okay I think I got what you said so if we think there are only n sub problems what are they they have to be compatible set L 1 w 1 then our 2 W 2 right these artists and unique subproblems you are thinking of thinking about right now is there any chance that I will get a compatible set like something like L 3 but W 5 right if I ever have this sub problem then well my number of subproblems are kind of exploding yeah I see many of you are saying no why not because if we have subproblems say compatible set of Li and WI and if we go from here and choose a next item choose the next block say T it's guaranteed that T has aa is shorter and narrower right that means our new subproblem or new compatible set becomes our new subproblem need to be compatible with T instead of I right so the only subproblems I can get are these ones like I cannot I cannot have one of these okay so subproblems are the number of subproblems are n and how much work do I have to do at each level and yeah yeah because I'm just taking the max right and there are n potential choices inside my max so runtime and square okay we're not fully done because there is an extra step when we are trying to do this we have to figure out what each of these are right because once I go into into this sub-problem I need to take a max on all the blocks that's in this set right I have to know what blocks are in that set is the heart so how would you do that okay so I check all of them that's over then I get I'm pretty sure you just been scanning scan the entire thing and pick out the compatible ones right but that's for this sub problem you have to do it for everyone oh there may be a better way so I think the previous tier is telling me there is a better way to do that so in order to find the entire compatible self he claims you can do it in and login but I haven't checked that so I'm not sure this is a folklore legend here yeah we'll double-check that offline but assuming if I if I don't have this then figure out all these sub problems we'll also take n square right then my total runtime is n square plus n square and still n square I started the ammonia solution keeping a sort of yeah I think it should be something along those line but yeah I haven't figure out whether you sort by length or you by width or you can only sort by one of them so after sorting say let's sort by length then after this after sorting I may get something like this right and if I am asking what's the compatible set of with this guy I still have to kick all of them out yeah so it's entirely not entirely clear to me how to do it but I think you can potentially consider having another say binary tree that's sorted by width and you can go in and just delete everything larger than a certain width so that's the yeah okay okay okay but constructing that graph already takes all 10 square correct okay let's move on I don't have time to figure this out no let's think about so this problem is remotely similar to interval scheduling weighted interval scheduling right in in a sense that it has some compatible set and in the very first lecture and recitation we have two algorithm for weighted interval scheduling and one of them is better than the other this one looks like the naive algorithm so does anyone remember what the better algorithm is for weighted interval scheduling instead of checking every one as my potential lowest one it really doesn't make sense to do that because for the very small ones I shouldn't put it put them as my bottom one I should only try I should try the larger ones first yep crap so just in the same line of thought as weighted interval scheduling let's first assault them but then his a little tricky because do I sort by length or width so I'm not sure yet but so let's just sort by length and then with so this means if they have the same length than our sort them by with so I can create a sorted list let me just assume that it's a in place sort and now I have the sorted list so once I have that so I should the question also the possible solutions I should consider is that whether or not or not I put my first block as the bottom one right it doesn't make sense for me to put those later ones down so my subproblem i sorry if my original problem becomes taking a max and whether or not i choose block 1 if I do then I get its weight a high story and my sub problem is the ones compatible with it correct if I do not choose it let my subproblem is what and reverse step from - all the way to it so why is this correct so I claim this cover all that covers all the cases like either h1 is chosen as the first bottom one or it's not it's not chosen at all it's impossible for h1 to be somewhere in the middle right because it has the longest largest length okay so how many subproblems do I have still n so there all of these compatible set of L 1 W 1 now 2 W 2 but looks like I do have some new sub problems right these do not exist before however there are only n of them right there just a suffix of the entire set right so I still have o of n subproblems under each step I'm doing constant amount of work there just two items so we found the order in solution I'll be done is it really order n ok nope yeah I still have to find all these seeds and first I actually have have a source step right that sort step is and login yeah then again what if we do it naively then it's again n square because I have to find this compatible set each of them but if there is analog in solution to find these compatible sets then my final runtime is n log N make sense any questions so far okay so now we actually have a choice so we can either go through another DP example I do have another one but then see one of the lecture suggested that it seems that many people have some trouble understanding yesterday's lecture on universal hashing and perfect hashing so we can also consider going through that well of course the third option is to just call it a day and so so let me just take a poll how many people prefer we go over the hash stuff okay how many people prefer another DP example okay sorry guys how many people just want to leave it's fine okay great that's it okay so so much for DP and we do have another example we are releasing recitation notes for those of you who are interested you can take a look so well you know you all know that we haven't go into DP in my lectures yet so this is really just a warm-up and to prepare you to go to the more advanced PP concepts and also DP will be covered in quiz 1 but the difficulty will be strictly easier than the examples we cover here okay now let's review universal and perfect hashing so it's not like I have a better way to teach it on our advantage here is that we have fewer people so you can ask questions you have so let me start with the motivating example so why do we care about hash it's because we want to create a hash table of say M it has m things and we will receive input say K 0 K 1 all the way to can K n minus 1 and keys and we'll create a hash function to each of them to map them to one of the bins and the hope is that if if n is Theta M or in the other way and they see the N then each pin should contain a constant number of keys so to complete a picture all the keys are drawn from a universe that has size you and this you is usually pretty large let's say it's larger than M square it's larger mine than the square of my hash table size but let me first start with a negative result so if my hash function is deterministic then there always exists a series of input that all map to the same thing we call that worst case we don't we don't like the worst case why because in that case the Hajj is not doing anything we still have all of the items in the same list ah why is that why is that llama true because by a very simple teaching whole argument so imagine I insert all of the keys in the universe into my hash table I will never do that in practice it's just a thought experiment so by a simple pigeonhole argument if u is greater than M square then at least something will contain more than M elements right well if it just so happens that my input are these M keys then my hash will hash all of them to the same thing make sense so this is the problem we are trying to solve we don't want this worst case and did that say that if H is deterministic we cannot avoid that right they always exist the worst case so what's the solution then the solution is to randomize H however I can't really randomize H I so if H take some key if my hash function maps a key into a certain being well the next time I call this hash function it better give the same thing right otherwise I cannot find that item so H needs to be deterministic so now our only choice is to pick a random H make sense every hash function is deterministic but we will pick a random one from a family of hash functions so in some sense it is this is cheating why because all I'm saying is I will not choose a hash function beforehand our wait for the user to insert inputs if I have too many collisions I'll choose another one if I have too many collisions out with another one okay I think I forgot to mention one thing that's important so you may ask why twerk here why do I care about that worst case what's the chance of it's happening in practice it's very low but in algorithms we really don't we really don't like making assumptions input why because if you imagine you are running or say a website web server well your code has some hash table in it so if your competitor or someone who hates you wants to put you out of business and if he knows your hash function he can create a worst case input right that will make your website like infinitely slow so what we are saying here is I don't tell him what my what hash function I'll use I'll say I choose one if he figures out the wrong input the worst case input I'm going to change my hash function use another one okay make sense now the definition of universal hash function is that if I pick a random H from my universal hash function family the probability that any key I map to the same thing as any KJ should be less or equal than one over m where m is my hash table this is really the best you can get if H function is really evenly distributing things you should get this property so we have seen one universal hash function in the class I'll give just I'll just go over the other example which is a k plus P modulo P and then modulo n so P is a prime number that is greater than the universe size we will see why this is a universal hash function so to do that we just need to analyze the collision probability so if I have two key that k1 k1 and k2 then map to the same beam that means they must have this property right after taking a mod M their difference should be a multiple of M right because if this is true after I taking the modulo M they will map to the same B make sense now I can quickly write it as a time's the difference of the key equals a multiple of M mod P now k1 and k2 are not equal so they are nonzero and in this group we are based on some numbers degree we have an inverse element for it so if if this happens we'll call it a bad a how many bad days do I have so that's a bad one one of a will make this equation holds with I equals one another a make the equation holds by I with I equals two but how many such is do I have at most like because this equation can hold with M 2 M 3 M all the way to P over m floor M right this is the total number of possible ways this equation can hold so how many bad 8 the bad days do I have I have P over m over the total number of A's which is P minus 1 well yeah I forgot to mention that so a is from 1 to P minus 1 okay so I can always choose my pee to be not a multiple of em if I do that this floor so then P and P minus 1 do not cross the boundary of multiple m right then this is true and this is less than 1 over m so this is a universal hash function family so what's the randomness here the randomness is is a our picker a to get my one of my hash and if it doesn't work now pick another day huh P is a prime number I choose yeah be our B is I think it's also a random number so yeah so actually it's not needed but I think there's some deep reason then they keep it in the hash function I'm not sure why now once we have that once we have universal hash people also want perfect hashing which means I want absolute absolutely zero creation so how do I do that let me first give a method one I'll just use any universal hash function but my choose I choose my m to be n square I claim this is a perfect hash function with certain probability why because I want to calculate probability no collision it's yeah one minus probability I do have a collision and I can use a Union bound that's the probability that any pair as a collision any pair of H x equals H y how many pairs do I have yeah n choose 2 which is this number right and based on so if it's a universal hash function then any collision any two colliding the probability is 1 over m right so I choose my M to be n square so this one is larger than 1/2 so what I'm saying so to get a perfect Hogg hash function I'll just use the simplest way I select the universal hash function with M equals n square I have a probability more than 1/2 to succeed or if I don't succeed I'll choose another one until I succeed so this is a randomized algorithm and we can make it a one-color up with them or Las Vegas algorithm so I can either say if I choose alpha log n times then what's the chance that none of my choice studies fights perfect hashing these probability is my failure probability is less than this right by each chance I have a half success rate and I try this many times what's the chances of all of them failing this is one over N raised to alpha right of course I can also say I'll keep trying until I succeed then I have a 100% success rate but my run time could potentially go unbound it make sense okay this sounds like a perfect solution the only problem is that the space complexity of this method is n square because I choose my M hash table size to the N square so this is the only thing we don't want in this simple method our final goal is to have a perfect hash function that has space over then and also run time are some polynomial Union and failure probability arbitrarily small and the idea there is this two-level hashing so I choose a h1 first to hash my keys into into beings and for each pin say I get our 1 elements here our two elements here so on so forth I'll choose each of the pins to be a second level perfect hashing so we can use the method 1 to choose this small one right if I choose M 1 which is the hash table size of this guy to be l1 square then I know after our for login trial this one should be a perfect hashing right after after another half a login trial I should resolve all the conflicts in l2 to make it a perfect hashing make sense so after n log n trials I will make all of these I will resolve all the conflicts in my second level hashing questions let me think about that offline I am not sure about that okay so the only remaining problem is we need to figure out whether we achieve this space of n what is the space complexity of this algorithm is n plus Li square because each table each table size is the square of the elements in it and finally we have that markov inequality things something like that to prove this is this is the case with so my space is all then also with the probability of greater than 1/2 then I can keep going I'll try our for log n times on my first level hash function until my space is all then right once I get get to that point I'll try choosing universal hash functions for my smaller tables until I succeed ok that's it for hashing and DBT so it's mentioned that it's only study