Homework 1 solutions continued Question 5 CLRS 4 6 a If more than n 2 chips are bad then a subset of the bad chips can act like good chips The number of black chips that do this can be the same as the number of good chips which is less than n 2 making it impossible to discern between these black chips and the good chips both sets of the same size This means that it is possible for a subset of the bad chips the number of black chips in this subset is equal to the number of good chips to report accurately whether the other chip is good or bad Assuming that these bad chips always do this it would be impossible to tell the difference between the good chips and these bad chips That is there does not exist a method by which to determine which are the good chips Here is an illustration below that illustrates this point Bad chips subset of bad chips acting like good chips good chips b The answer to this question lies in the two questions that are asked by Professor Kahng on the discussion board The first question is 1 if you put two chips on the tester and the result says that one of them is bad what happens if you throw both of the chips away In this case if you throw both of the chips away then since you know that at least one of the chips is bad then you are still left with a set of chips that have a majority of good chips The second question is 2 if you have K pairs of chips each of which is an identical pair i e X X where X can be either Good or Bad you can t tell and the 2K chips together have a majority of Good chips is there any way that you can come up with a smaller set of chips which still have a majority of Good chips The answer to this question is yes You can easily do this by throwing away one of the chips from each pair Then you still have a majority of good chips Therefore combine the two questions so to speak If you are given n chips begin a pairwise comparison If one or more is labeled as bad throw them both out If they are both labeled as good store them in a pile but at the end of the pairwise comparisons of all the chips throw out one chip from each pair which said that the chips were both good If you do this then you are guaranteed to have a set of chips with a majority of good chips where the size of the set is half the size of the original set After finishing this algorithm you will be left with one chip which will be good c The recurrence relation corresponding to this solution is T n 2T n 2 n 2 which according to the master method is equal to n
View Full Document
Unlocking...