Give a decision tree lower bound for the (worst case) number of weighings that must be performed by any algorithm solving this problem. b. Design an algorithm that solves this problem with (worst case) number of weighings equal to the lower bound you found in (a). Present your algorithm by drawing a decision tree, rather than pseudo-code. c. Alter the problem slightly to allow the possibility that all 12 bars are pure gold. Thus there is one additional possible verdict: "all gold". Make a minor change to your algorithm in part (b) so that it gives a correct answer to this more general problem.

Assume that two parallel arrays have been declared and initialized: healthoption an array of type char that contains letter codes for different healthcare options and annual cost an array of type int. the i-th element of annual cost indicates the annual cost of the i-th element of healthoption. in addition, there is an char variable, best2.write the code necessary to assign to best2 the health option with the lower annual cost, considering only the first two healthcare options. thus, if the values of healthoption are 'b', 'q', 'w', 'z' and the values of annualcost are 8430, 9400, 7050, 6400 your code would assign 'b' to best2 because 8430 is less than 9400 and is associated with 'b' in the parallel array. (we ignore 'w' and 'z' because we are considering only the first two options.)