1) Divide and Conquer This problem has two options to answer, ONLY ANSWER ONE. I
ID: 3668865 • Letter: 1
Question
1) Divide and Conquer
This problem has two options to answer, ONLY ANSWER ONE. If you change your mind on which problem you want to attempt after you have written the solution to one, be very clear about which solution you want us to grade. Question a) is more difficult, and worth full credit. For partial credit (60%), you may answer question b) if you cannot solve a). Please be clear which of the two you are answering.
Suppose you have a set of n coins. All of these coins have the same weight, except for one, which is fake. The fake coin weighs less than the real coins. In addition, you have a scale that you can use to weigh any two piles of coins. Given two piles, the scale will either report that the two piles or the same weight, or which of the two is lighter.
a) Give an algorithm that uses the scale no more than log3n + 1 times. Note here that we are not asking for O(log3n), this is a more exact requirement.
b) Give an algorithm that uses the scale no more than log2n+1 times.
2. Greed
You are a ski rental store with n customers, each with their own distinct individual height hi, and n pairs of skis, where ski j has distinct height Sj. Ideally, you'd like to match everyone with a pair of skis exactly their height, however, this may not be possible. As such, your goal is to minimize the squared error between matched heights across all of your skiers. That is, you want to minimize across all of your assignments. Design an efficient algorithm to generate an optimal matching, argue its correctness, and analyze the running time. (Hint: If a<b and c<d, then (a-c)^2 + (b-d)^2 < (a-d)^2 + (b-c)^2 )
3. Minimum Spanning Tree
Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph G, with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost Ce with its square, c^2e, thereby creating a new instance of the problem with the same graph but different costs on the edges.
Is T always a minimum spanning tree for this new instance? If yes, argue why it must remain a MST. If no, provide an example where T is no longer the MST. (Hint: Consider the operation of the algorithms discussed in class on each of the two versions of G)
1 Divide and Conquer This problem has two options to answer, ONLY ANSWER ONE. If you change your mind on which problem us to grade. Question a) is more difficult, and worth full credit. For partial credit (60%), you may answer )you want to attempt after you have written the solution to one, be very clear about which solution you want question b) if you cannot solve a). Please be clear which of the two you are answering. Suppose you have a set of n coins All of these coins have the same weight, except for one, which is fake. The fake coin weighs less than the real coins. In addition, you have a scale that you can use to weigh any two piles of coins. Given two piles, the scale will either report that the two piles or the same weight, or which of the two is lighter a) Give an algorithm that uses the scale no more than loga n +1 times. Note here that we are not asking for Ollogs n), this is a more exact requirement. b) Give an algorithm that uses the scale no more than log2 n1 times. 2 Greed You are a ski rental store with n customers, each with their own distinct individual height h, and n pairs of skis, where ski j has distinct height s. Ideally, you'd like to match everyone with a pair of skis exactl;y their height, however, this may not be possible. As such, your goal is to minimize the squared error between matched heights across all of your skiers. That is, you want to minimize across all of your assignments. Design an efficient algorithm to generate an optimal matching, argue its correctness, and analyze the running time. (Hint: IfaExplanation / Answer
First check whether middle element is Fixed Point or not. If it is, then return it; otherwise check whether index of middle element is greater than value at the index. If index is greater, then Fixed Point(s) lies on the right side of the middle point (obviously only if there is a Fixed Point). Else the Fixed Point(s) lies on left side.
int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
/* Return -1 if there is no Fixed Point */
return -1;
}
another method
The integer are distincts and sorted.
Given i such that array[i] = i you have array[i] - i = 0.
For each j < i you have array[j] - j <= 0 and for j > i you have array[j] - j >= 0 because j vary of 1 at each step but array[j] vary of at least 1 (distinct and sorted numbers).
So on the left it's <=0 on the right it's >= 0.
Using dichotomy you can easily find the correct position in O(log n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.