Algorithms Lecture 18: Dynamic Programming, 0-1 Knapsack Problem

so today we would be talking about a new algorithmic technique which is dynamic program so we will discuss two problems one is a relatively simple problem which is the Fibonacci number calculation it should be familiar for most of you this problem illustrates the difference between the dynamic programming approach and other approaches so everyone is familiar with Fibonacci numbers you know Fibonacci of 0 equals 0 Falacci of 1 equals 1 Fibonacci of 2 equals 2 Valachi of 0 plus Fibonacci of 1 and in general Fibonacci of n equals Fibonacci of n minus 1 flow plus Fibonacci of n minus 2 okay now and many of you have probably written a recursive algorithm for computing for Bonacci numbers long let's say and it's going to return for for the base cases if N equals 0 or N equals 1 return n else return fabu nachi of n minus 1 plus energy of n minus 2 so this is a recursive algorithm for computing Fibonacci numbers now if we try to analyze the asymptotic complexity or analyze the behavior of this algorithm we'll see something like this you know from Bonacci of I FM not G of n is going to call from Gracchi of n minus 1 and Fibonacci of n minus 2 and Fibonacci of n minus 1 is going to call Fibonacci of n minus 2 and Fibonacci of n minus 3 and this is going to call Fibonacci of n minus 3 and Fibonacci of n minus 4 and this is gonna call Fibonacci of n minus three and four Bonacci and minus one and we would continue until we get to the Bonacci of zero and Fibonacci of 1 which are the base cases now what's the running time of this algorithm based on this tree based on this tree what's the running time of the algorithm so what's the what's the height of this thing yeah so the height of this tree is gonna say to be theta n because you will get you know you go from n all the way to 1 or 0 so the height of this theta of n now if there's a tree with height take of n how many how many nodes will the tree have what's the what's the mathematical relation between the number of nodes in a tree and the height of the tree it's exponential right so assuming that it's a complete binary tree it's not it's not complete this is not complete because some end at one some end at 0 but assuming that it's for a good approximation assuming that it's a binary complete binary tree if the depth or the height is n then we have two and plus one minus one no so remember this formula when we analyze complete binary trees so in summary the relation between the number of nodes in a tree and the height of the tree is exponential so that number of nodes is an exponential function of the height or the height is a logarithmic function of the number of nodes so here what's our input size our input size is n which is the height of the tree so our input size is n with which means that the number of nodes is going to be exponential so this is going to be an exponential algorithm so if you try to compute this if you write this you know innocent function this function that looks very innocent if you write it and you give it large sufficiently large values of n you know and based on the calculations that we did earlier this semester you should know what is large and what is small for an exponential so if you do fifty for example that's large so 50 is not it's not going to finish we're gonna take forever okay now so we know that it's exponential but now let's try to think about the algorithm and see why it resulted in such an a huge running time you know where is that where is the problem in this algorithm hmm yeah exactly it keeps solving the same subproblems over and over so for example you know this is a big problem that God divided into two subproblems the sub problem of finding n minus 1 and the sub problem finding n minus 2 but then we keep encountering the same sub problem multiple times for example you know n and n minus 2 so here's n minus 2 and here's another n minus 2 if you look at n minus 3 here is an n minus 3 and this is another n minus 3 and this is a third n minus T so the problem here is overlapping subproblems so in fact this problem has the optimal substructure the problem itself has the optimal substructure property in the sense that you can use solutions to the subproblems and build solutions to the original problem of course you know remember that this is not an optimization problem at all so it's it has the optimal substructure but it's this is not an optimization problem at all this is just a computational problem we will see the zero-one knapsack which is an optimization problem in a minute but the problem with the algorithm is that the sub problem is is encountered multiple times and is solved multiple times so there is a lot of duplication now how can we avoid this we can avoid this by solving each sub problem only once so what if we just instead of taking a top-down approach to the problem instead of taking a top-down approach starting with the big problem and dividing that problem to smaller subproblems what if we start from the bottom of the tree and solve that the the smallest problem is the base size is first then use the solutions to the base problems to build solutions to bigger problems and so on we go in a bottom-up approach as opposed to a top-down approach this can be then easily done for the fibonacci as follows so we can write well instead of this we can write Fibonacci of long n so we can create an array a of size n plus 1 y n plus 1 because you know this is because we need to go from 0 1 2 through n so we need n plus 1 so we can just solve this bass problem solution is 0 this bass problem solution is 1 then given these two solutions we can solve this problem so it's just the sum of 0 and 1 which is 1 then this subproblem is the sum of the solutions to 1 & 2 and that gives us 2 & 4 4 we just add 1 & 2 and get 3 so this looks easy so instead of starting with the big problem and going top-down we're going bottom-up by solving the basic or the base sizes the problems with the base sizes first then using these solutions to these small problems to build solutions to bigger problems and so we keep going until we get to the to the whole problem of size n this means or not easy recursion well it's not it's not it's not just a matter of recursion versus non recursion here using recursion resulted in these overlapping subproblems but it's not you know it's not you know anything that you can do with recursion you can do it without the culture so you can you can implement the same approach without recursion but the idea here is that there is the algorithmic technique which is instead of thinking top-down think bottom-up solve the smaller problems first and then use the solutions to the smaller subproblems to build solutions to the bigger problems but yes recursion you know when you use recursion that will tend to give you a top-down approach to the problem and in this case it gave you all of these overlapping subproblems so here if we were to just try to create an array a of size n plus 1 and then set a of 0 0 a of 1 to 1 and then go for I equals 2 for I equals 2 to n a of I equals what a of I equals I minus one plus a of I minus two okay and then what should we return what should we return every yeah we return over okay so now you know by doing this we are solving the smaller problems and we are storing the solutions to the smaller problems in a table you know this array you can think of this array as a table so we are storing the solutions to the smaller subproblems and whenever you need a solution to a sub problem instead of recomputing it you just look it up in the table solve subproblems store the solutions to the subproblems in a table and instead of recomputing a solution to a sub-problem you just look it up in the table and use it and if you do that in the right order you will get this algorithm so the running time of this algorithm is this is exponential this is an exponential algorithm while this what's there anytime of this yeah this is just take our best so we managed to to replace this exponential algorithm with a linear time algorithm so this is you know very much you know as slow as it can get and this is very much as fast as any game so this is linear one of the fastest and this is exponential one of the slowest algorithm and we managed to do this by looking at the problem bottom-up solving smaller subproblems storing solutions in a table and reusing them so this is this is the idea of dynamic program now let's apply this to the zero-one knapsack problem and the zero-one knapsack problem is the problem that we could not solve using greedy algorithms so let's now see how we can solve it using dynamic programming how can we use the same idea to solve the zero-one knapsack problem well let's first look at the example that we will be using this is the example 2 kilogram and $3 3 kilograms for 5 kilograms and 6 dollars and then the knapsack has a capacity C equals plus Big C equals 8 kilograms okay so this is the example that we will be using now how can we apply dynamic programming to this the idea is to start with some base case that we can solve easily what is that base case that base case could be you know for example having item two what if you have only one item so that's a base case I only have item one all the item one and I have a capacity and C equals one if you have item one and the capacity of one what would the solution be 0 because item 1 has a a weight of 2 kilograms so I would not be able to take it so it's just the solution is 0 so this looks you know trivial but as we will see later in this lecture we will be able to use these trivial solutions to these easy sub problems to build solutions to bigger subproblems and we will keep computing solutions to bigger and bigger subproblems until we eventually build the solutions the solution to the whole problem so it's even though we will start with trivial solutions to trivial base cases we will end up building a solution to the big problem now we can increase the size of the sub-problem now remember that now we are thinking bottom-up so we are starting with smaller subproblems and we are building bigger instead of starting with a big problem and creating smaller problems now we're starting with smaller problems and making them bigger and bigger now how can we make this bigger this problem has two dimensions it has the item the number of items and it has the capacity so we can grow the problem in either dimension we can grow it by either including more items or by increasing the capacity so let's try to grow it by increasing the capacity so item what if we have item 1 only and we have a capacity of 2 now with the capacity of 2 and item on only item 1 is going to fit in this knapsack and it's going to give us a value of 3 ok so we can keep growing the problem by increasing the capacity on the other dimension we can grow the problem by adding more items so we can look for example at item 1 and item 2 and the capacity of one okay what's the solution in this case zero but if C equals one C equals two with the same items item one and two then the solution is going to be three and so forth now we will draw eventually we will draw a table that will show all the subproblems we will show you know we'll start with sizes of zero and then we will grow it in both dimensions until we get to the complete problem but before we draw the table the key idea here is that we know how to do base cases you know base cases are easy and trivial but how can we use base cases or smaller subproblems to build solutions to bigger problems the idea is that given any item X item X you have two possibilities either take it or not take so either take X or not take X so this is basically what the zero-one knapsack problem is for each item you are trying to decide whether to take it or not how does this relate to smaller subproblems well if I have a given capacity see if I take X then this is X and X has a certain weight so this is you know the weight of X if I take X then the space that is left in the knapsack if the if the entire capacity is C this is going to be C minus W of X right so if I take X I will have C minus W of X left in the knapsack and then you know I can fill this with some of the remaining items now deciding or determining you know the best subset of other items that I can put here in the remaining capacity is a sub-problem that is smaller than the current problem that I'm trying to solve so the problem that I'm trying to solve is a problem that includes X with capacity of C now if I know the solution to this subproblem which is the optimal value that I can fit in a knapsack with capacity C minus W of X the remaining capacity here and using other the other items okay then I know what you know what's the best that I can put here and that's going to give me an optimal solution to this sub-problem now this is the option of taking X the other option is not taking X if I do not take X I will just have the entire knapsack available right but this is also a smaller sub-problem that if I have if I have solved before solving the current problem I will know the solution to this subproblem remember that we will start with the smallest subproblems and we will build solutions to larger problems so if this is opt to up to is the maximum value that I can fit in a knapsack with capacity of C using items other than X the items other than X the item that I considered before now how can I determine if taking X is better or worse than not taking X I'm trying to determine if taking X is good or bad well if I just compare this up to the solution for you know using the the hole capacity and items 1 2 3 through X minus 1 you know I'm assuming that I'm ordering the items in a certain order and as we will see it doesn't matter in which order you can just number the items in any order you want so considering items 1 2 3 through X minus 1 what's the optimal that I can fit in a capacity of C and using the items 1 2 3 through X minus 1 what's the best that I can fit in a capacity of C minus W of X so I take optimal 2 optimal one and add to it what the value of x yeah not the weight of X the value of X so if I take X I will get this I would get the value of x because I will take X then whatever I can fit in the remaining capacity of the knapsack that's what I will get if I take X this is the first option the second option is if I don't take X then I will have the whole capacity available and I will just take the best solution you know they take the best subset out of other items that I can fit here then I compare these so if this is you know for example you know let's put some numbers if opt one is 30 and op 2 is 40 and the value of x is 15 then in this case you know 30 plus 15 is going to give us 45 compared to 40 then I much rather take X you know taking X is a bit better deal but if we change the numbers you know what if this what if this was 50 instead of 40 then in this case not taking X would be a better deal so we're trying to choose between taking X and not taking X okay so now with this with this description let's now draw the entire table because dynamic programming is based on a table that has the solutions to all the subproblems and we will see how this can be put together to construct a solution to the zero-one knapsack problem okay so my table is gonna look like this now I'm gonna it's going to be for this example so I'm going to grow the the solution in two dimensions in one dimension I want increase the number of items in the other direction I will increase the capacity so here I have okay so the capacity is gonna go so it's going to go from zero one two three four five six of course it's gonna get to the maximum capacity here which is eight seven and eight then here I have no items this is a trivial subproblem in which no items are considered here I consider item one only then here I consider items 1 & 2 and then items 1 2 & 3 so which square in this table is gonna have the solution to the whole problem yeah the lastly so this is the solution considering all items with a capacity of 8 while you know let's look at this for example this solution so this square here will have the optimal solution to the sub-problem of considering only items 1 & 2 so I can see is not considered only considering items 1 & 2 with a capacity of 4 this is a subproblem so basically here in this table we are storing the solutions to all the subproblems to avoid resolving a subproblem multiple times so each sub problem gets solved once and because the problem exhibits the optimal substructure we can use that we can use solutions to the subproblems to build solutions to the bigger problems so remember that the zero-one knapsack problem has the optimal substructure property but of course it doesn't have the greedy choice property if it had the greedy choice property we would have been able to you to solve it using a greedy algorithm remember to solve a problem using a greedy algorithm you have to have both optimal substructure and greedy choice property this problem the zero-one knapsack version of the problem has optimal substructure and this is something that we will be capitalizing on in in building this dynamic programming solution but it does not have the greedy choice property okay so now by looking at this table so let's or let's try to in general you know what each entry in the table means in general T of I and J in the table means optimal solution for a knapsack a knapsack of capacity J capacity is J using items 1 2 through I so the entry T of I and J in the table will have the optimal solution for a knapsack with capacity J using items 1 2 through I so now this is easy when you have no items what what will the solution be so even though this looks like a trivial base case but we will be able to build on it we will be able to use it to build solutions to bigger subproblems now when we have item 1 considered with 0 capacity what would the solution be 0 because we will not be able to fit it so item 1 has a weight of 2 right there's a weight of 2 and of course with one that's that value is 0 because we won't be able to fit it when the capacity is 2 we will be able to fit item 1 and the value of our solution will be 3 which is the value of item 1 then obviously will we be able to get something greater than 3 with item 1 only so in this row we would not be able to get anything greater than three because we are only considering item number one this is the subproblem that were considered so even if you increase the capacity with only item one considered you're not going to get greater than three so it's going to continue three three three now we're considering both items one and two so basically the new item that we are adding or that we are considering now is icon - now when will things start to make a difference when we get to what capacity capacity 5/3 because when we get to capacity three we will have the option of taking item two before we get to capacity three we don't have the option of taking item two because it won't fit so we need at least a capacity of three in order to consider item number 2 before 3 we do not consider item - it won't fit so what we do before we get to 3 we just we have to stick to the original sin the solution that we have previously with item 1 so just copy what we have and the previous row now with a capacity of three we have the option of taking item two but remember taking item two will not necessarily give us a better solution so we have to compare two options take item two and don't take item two now if I take item two I will get a value of at least four which is the value of I 2 2 then I will add to it what I will add to it whatever I can fit after I take item 2 now what will be the remaining capacity at this point what will be the remaining capacity after I take item 2 0 now with a capacity of 0 and using the items that are that the items before item 2 which which is in this case on the item 1 the solution is here this is the solution so I already have it you know this is the best solution this is the best that I can fit in the remaining capacity after I take item 2 using the previous icons so this is going to give me 4 plus 0 now if I don't take item 2 what solution what's a problem solution should I look at at the previous one because if I if I if I don't take item 2 then I would have the entire capacity of 3 right and what can I fit in a capacity of 3 using other items it's this the answer is already I have already computed the answer here so what I can fit with the capacity of 3 using previous items is this 3 so if I don't take it I get 3 which is better now four or three so 4 is better than 3 so I would choose to take item 3 item 2 so I choose to take it and get a 4 ok so this is the idea now when I get to a capacity of 4 again I have the option of taking item 2 if I take it I will get 4 plus what Plus what I can fit with the capacity up yeah within a capacity of 1 which is still 0 so it's still 4 plus 0 and if I don't take it I will still get a 3 because that's the previous solution and again 4 is better than 3 here if I take it I will get 4 plus 4 plus whatever I can fit within a capacity up yeah which is 5 minus 3 a capacity of 5 which is the current capacity minus 3 because I will lose 3 when I take item 2 so 5 minus 3 is 2 so I will look at this so it's going to give me 4 plus 3 and the 3 came from this ok so if I take it I will get 7 if I don't take it I will get 3 and clearly 7 is better than 3 so I will take it then since I have already taken both items it's not gonna get any better right so on this line on this row things are not gonna get any better than taking both items okay now this the last line the last line is probably the most interesting line the most interesting you now I should keep copying whatever I had on the first in the previous row until I get to a capacity of yeah capacity of five before five taken item three is not an option because it won't fit so just until I get to five I just copy whatever I had previously so I have 0 0 3 4 4 now I consider taking item thing and I'll have to compare the two options taking and not taking taking will not always be the best choice so if I take item 3 I will get a value of I would get a value of 6 but how much remaining capacity will I have 0 so in 0 I can get 0 right so I would look at this so this is what I can get with a capacity of 0 using the previous item so I would get a 0 so if I take it I would get 6 plus 0 if I don't take it I will get 7 so which is better 7 which means don't take it so now I just take the 7 and I will not take the I will not take item 3 now when my capacity becomes 6 again my options are 6 plus what I can fit within a capacity of 1 yeah which is a zero so if I take it I will have one more kilogram that I can take but with one more kilogram I can fit 0 of the previous item so it's gonna still be six plus zero compared to seven and seven is gonna win again but here I will have 6 plus and remaining capacity of what's the remaining capacity here - so the remaining capacity of two I look at this square with a mini capacity so it tells me that with a remaining capacity of 2 you can fit a value of 3 so then I can get 6 plus 3 and 6 plus 3 is better than 7 so now I take it and get at 9 and here it's 6 plus what I can fit with the capacity within a capacity of 8 minus 5 which is 3 so I can fit 4 so this is 6 plus 4 which is 10 and 10 is better than 7 okay so this is the you know this is the dynamic programming algorithm okay and obviously my solution is gonna be in the last square but this square tells me the value of the solution it doesn't tell me which items have been taken and which items have not been taken so how would I know which items have been taken and which items have not been taken okay so when I look at this square does it tell me whether item three has been taken or not if I compare it with the surrounding squares will I get a clue whether item three has been taken or not so what happens when you take the item when you take the item the value of the current throw would be different from the items in the ayah the value in the previous row when you choose not to take the item like we did here when we did not take the item we just you know the same value the value of the current row was the same as the value of the previous row so by comparing the value in the current row with the value in the previous row we can tell whether the current item has been taken or not and in this case because 10 is different from seven then I know that item three has been taken but then I have to decide about other items so now to which square should I go so this solution is based on which square for the you know for which solution for the remaining items items one and two so I have to go to which square it's based on the remaining capacity so the remaining capacity is eight minus the weight of item three eight minus five and that's three so I go to the previous row and column three which is this so now I go to this now I do the same thing did I take our item to or not I compare it with the previous row and this told me that this tells me that the values are different so I have taken item 2 okay so I came to has been taken then I go to which square 3 minus 3 minus 3 right 3 minus 3 is 0 so this will put me here now I compare 0 with 0 same value so I did not take item 1 okay and then since I'm at item 1 that's it so by tracing back I can decide which you know whether a certain item has been taken or not okay so let's now write the write the pseudocode for this dynamic programming algorithm so it's gonna be dynamic programming zero-one knapsack and then I get W V and M and C and these have the usual meaning so what's V this is an array of values W is an array of weights n is the number of items and C is the capacity oh so now this algorithm is just going to construct this table so first it create a two-dimensional 2d array with what's the number of rows plus 1 right because you have a no item row so with n plus 1 rows and C plus 1 columns inside will recall that array ah okay yeah a two-dimensional array t yes t for table then we will fill the first row with zeros so all what we do for J equals zero to see T 0 and J equals what T of 0 and J equals 0 so this is fill the first row with zeros then I will start filling the rows from 1 to N for I equals 1 to n now for I equals 1 to n and for J equals 0 right or J equals 0 to C so I goes from 1 to N and J goes from 0 to C now I have two cases remember that first I had to determine whether the item is an option or not so if the item is not an option I will just you know I would not have to compare taking against not take so if the item is not an option how do I detect that if what if the item doesn't fit weight is greater than capacity if the weight of I or J no I see I is the item number right so let's put a comment here I is the item number J is what capacity the column is the capacity so if weight of I if the weight of I is greater than what the capacity so what's the capacity at that point T of Ecology J sorry sorry the value J itself J is the capacity the weight of I is greater than the capacity J right then the item doesn't fit so this means that item does not fit so it doesn't fit I will just take the previous solution and the previous solution it means that T of I and J equals J minus 1 or I minus 1 when I go one row up I minus 1 I is the row number so it's going to be T of I minus 1 and J take the solution from the previous row take solution from previous row what I take from previous row because the current item doesn't fit so it's not an option so this is the less interesting case the more interesting case is the else if it fits if it fits then my T of I and J is going to be the maximum of T of I and J is the maximum of the cake and the not take now what's the take what's what's going to be the value if I take it hmm if I take it then I will have its value what is its value vo by its values D of I plus what I can fit in the remaining capacity now how do i express the best that I can fit in the remaining capacity how do i express that it's going to be T of something in the table T of is it in the current row or previous row previous row which means I minus one now what's the column number yeah exactly J minus the weight of I J minus the weight of body okay so this is basically this is the remaining capacity this thing here this is the remaining capacity this is the remaining capacity and if I don't take it so this is take I so this thing is take I now if I don't take I what's the option what would be the value T of the previous row what is the previous row T of I minus 1 and what J did we change the column no when you look at the previous solution its previous row same column so biggest row same column is this so we're taking the max of take and not take so this is don't take okay so this is the algorithm okay so basically you go through the items so first set the first row to 0 the second 4 rows 1 through n you go from J equals 0 to C if W bar is greater than J just take the previous value which is T of I minus 1 and G if the item fits then you have two options take it or not take so you compute the value for taking it and the value for not taking it and get the bigger value so in order to get the value for taking it you have its value plus the best that you can fit within the remaining capacity this is very many capacity and this is the previous row using the previous items and this is that what you can fit if you don't take it so obviously here you have a bigger capacity the whole J here you have J minus the weight of the item okay alright so this is the algorithm for building the table but what's the algorithm for identifying the items that have been taken so let's let's write it here it's gonna be an easier algorithm so we started from so let's call it it will find items or decide items so the decide items we start from you know I equals I equals N and J equals C I equals in the last the last square and we go for I equals n 2 1 or don't want to emphasize that we're going down if what how did we decide if an item is taken or not if T of I and J is what is greater than T of previous row same J is greater than the value in the previous row then take item I take item I and when I take item I I have to go to this square so how did I decide what the square is I change J J equals J minus weight of I and in fact that's all what I need that's it and I will get decremented automatically because it's the loop counter so I'm starting from n all the way to 1 so each time I go one row up I may change the column I change the column if the item is taken but if the item is not taken I do not change the cop look so this is the this is the algorithm now what's the running time of this thing and square NC yeah and C so this is M and this is C so the running time here of T of n is Theta of NC and what's the only time of this thing this is Theta of n this is easy this is just theta of n this is Theta of n C okay any questions so far what do we take for the columns here you will have to cover all the weights or all possible weights whether they are integers or fractions but you know if there are fractions you can find a you know the the smallest common factor or you know number that an integer uniform for example if you have halves I so you multiply by two you have thirds you multiply by three but you know the idea here is that you will have to cover all possible weights and all possible combinations of weights all the possible weights that you can have for the knapsack okay so now okay so there are a couple of things in fact a couple of important points first point is you know what proves the correctness of this where is the proof of correctness here so here the proof of correct yeah in fact we did not solve all possible combination if we if we solve all possible combination we will get an exponential of a algorithm that is exponential in the number of items so we did not look at all possible subsets of items we looked at all possible sub problems not all combinations so these are two different things combinations are subsets of items and the number of subsets of items is explanation which is the power set but we looked at all possible subproblems but that alone doesn't prove that this is correct the proof of correctness here is implicit in the way dynamic programming works in fact there is an implicit inductive proof here you know recall that for induction to prove something by induction you have to have a base case and then you have to prove that if this theorem is true for n it's true for n plus 1 so if it's so you have to prove the continuation or the induction so you just prove as a trivial base case then you prove that if it's true for n it's true for n plus 1 or for larger values and this is exactly what you are doing here so we are starting with a trivial base case that is clearly true you know for which clearly if we have no items then the value is gonna be 0 so this is our base this is our trivial base but then our inductive step is these equations these are in fact recurrences the currency's in the sense that they define the value for I and J in terms of smaller boys and G's so the value of this square for this I and J is defined in terms of this square so in fact you know the correctness of this follows from the correctness of this equation so this equation is saying okay if it doesn't fit I will have to take the previous solution that's clear here if it fits I have only two options take it or not take it and I'm considering these two options take or not take and I'm looking at the value of take and the value of not take and taking the value that is larger the larger of the two take and not take okay so here the proof is implicit the proof is implicit in these equations that I'm using but it's a it's an implicit inductive tool so induction is used a lot in proving the correctness of algorithms because in algorithms we tend to repeat things but see this is a different kind of repetition compared to what we were doing in greedy albert greedy algorithms we were taking a top-down approach we were making a decision making the greedy choice then with the greedy choice we were left with a smaller subproblem and then solving the smaller subproblem so in greedy we were starting with a big problem and making it smaller here we're starting with small problem smaller problems and building solutions to bigger problems okay so this is this addresses the correctness now one important subtlety here is the question of whether this is polynomial or not is this polynomial in fact surprisingly the answer is not so this looks polynomial but indeed it's not polynomial why isn't it polynomial so in order to understand why this is not polynomial we have to think carefully about the input size so let me try to explain this now we have to think carefully about the input size as opposed to the magnitude of the input what do I mean now think of an input file that has the input to an instance and input that you know represents an instance of the zero-one knapsack problem so that input file will have n you know for example a thousand N is a thousand and C is probably ten thousand or yeah let's let's do it the other way around so it doesn't matter in fact so this is let's say that this is C this is N and then if n is ten thousand we would have the weights and values of a ten thousand items so we will have you know weight one value one way to value to wait three value three until we get to wait ten thousand value ten thousand think about the size of this input fine now if what is the asymptotic complexity of an algorithm the sympathic complexity of an algorithm is there a mathematical relation between the number of times or the number of operations and the input size now in terms of input size for n you will have you know n lines in the input file so in fact the relation between this and this is polynomial it's even linear or even it's at worst linear because I have n items so I have a big input and this is n but the relation between C and this this relation is not linear why because if you look at the size of this input not the magnitude of this now the magnitude of this is a thousand right but what's the size of it in terms of the number of characters how many characters do we have four I have four characters and with four characters I got C so with four characters if we point it to this slot this loop this loop is executing C times well in fact yes in fact I should point these to the loops it will be clear you know so this goes to this loop and this goes to this new so that's important you can think of that synthetic complexity of an algorithm as an as an amplification factor to what extent you know it takes a small input and amplifies that or magnifies that and does a lot of computation for such a small input so if an algorithm does a lot of computation for a small input it's a complex algorithm if it doesn't do a lot of computation for the size of the input then it's not complex so here you know for only four characters we ended up executing this loop a thousand times why here for you know ten thousand lines we executed the loop ten thousand times so this relation is obviously linear this is not we do not have a big amplification factor but here we have a big amplification factor because this is just a number so if you look at this relation if you draw a table like this the value of C value of C and here input size and here loop iterations if you look at this if the value of C is a hundred the input size is just three characters one two three and the loop is going to execute a hundred times if the value of C is a thousand then the input size is what four characters and the loop is going to execute a thousand times if the value of C is 10,000 then the input size is going to be 5 and the loop is going to execute 10,000 now the complexity of an algorithm is the number of operations which is 0 by the number of iterations of the loop as a function of input size so if you plot this column the numbers in this column versus the numbers on this column what kind of function will you get this is an exponential function it's an exponential function because you know it it's basically this is you know it's 100 is 10 power 2 and a thousand a thousand is 10 power 3 and this is 10 power 4 so basically the relation here is 10 power n minus 1 so it's exponential so this is the hidden exponential relation and the cause of this is that this input is just a number and our input size is not the magnitude of the number our input size is the number of characters that encode the input so think of you know the input size is this which is the number of characters that encode the input as opposed to the magnitude of the input now this doesn't apply to n because with n where not the input is not just a number we have an actual list of n items so here the input is so big the input size is big and this does not amplify this why this while this loop the number of iterations of the loop is a big amplification of such a small input size it's exponential okay so this is that's why this solution is technically is not a polynomial time solution this is an exponential solution and but in practice from a practical point of view this algorithm will will behave like a polynomial time algorithm most of the time it will behave like a polynomial time algorithm as long as si is not huge as long as si is reasonable this algorithm is going to behave like a polynomial time algorithm so strictly speaking mathematically speaking this is an exponential algorithm it's exponential in the input size but from a practical point of view it's practically polynomial in fact it's you know it's referred to as pseudo polynomial so this is considered a pseudo-polynomial algorithm pseudo polynomial and as we will see when we talk about np-completeness the zero-one knapsack problem is an np-complete problem but because it has a pseudo polynomial time algorithm it's a weekly np-complete problem so it's not it's not strongly into np-complete its weakly np-complete because of it has this algorithm that is mathematically exponential but practically polynomial

Channel: Ghassan Shobaki Computer Science Lectures

Views: 4,082

Rating: 5 out of 5

Keywords:

Id: P0_VC8_uaXw

Length: 74min 42sec (4482 seconds)

Published: Sat Jan 05 2019