For part (b), the discussion referred to \'after Example 1.9\' is on Page 37. Fo
ID: 3882589 • Letter: F
Question
For part (b), the discussion referred to 'after Example 1.9' is on Page 37.
For part (c), SUPPORT YOUR ANSWER by drawing the DECISION TREE for the algorithm you described in part (a). [See the end of my Chapter 1 notes for an ilustration of how decision trees should be labelled: DON'T emulate the uninformative format show at the top of page 60 (Figure 1.8). Use ovals for decision nodes, and rectangles for outcome nodes]
For part (d), note that an optimality argument is required.(Part (E) of Problem 1.23 is not in the textbook, but answer it anyway :-) Problem 1.23 E: The parameters of the problem have simplified things so that there are no ties, and your answers to the first four parts can assume that this is the case.
In part (E), assume for a moment that ties are allowed. If your (unwritten, and you do NOT have to write a new one) algorithm were to discover that the first two entries you compared were equal to each other, what can you say about the median of the entries in this 3-element array?
1.23 The median of an ordered set is an element such that the number of elements less than the median is within one of the number that are greater, assuming no ties. a. Write an algorithm to find the median of three distinct integers a, b, and c. b. Describe D, the set of inputs for your algorithm, in light of the discussion in Sec- tion 1.4.3 following Example 1.9 How many comparisons does your algorithm do in the worst case? On the average? How many comparisons are necessary in the worst case to find the median of three numbers? Justify your answer. c. d.Explanation / Answer
(a)
The median is the element is array which devide it into two parts.
Idea is to traverse through array and find the element which is in between other two.
For int i 0 to 2
If( E[(i+1)%2] > E[i] && E[(i+2)%2] < E[i])
Return i
(b)
Suppose input is 4 6 2
So 4 is in between other two element so it is median of array.
(c)
Worst case occurred when median is at last index.
As 2 8 5
In Every step we are doing 2 comparison.
So total comparison is 6 in worst case.
In best case it will do 2 comparison if we find median as first element. And if our median is second element the comparison is 4
So average case comparison is (2+4+6)/3= 4
(d)
In worst case it will do 6 comparison as in each step we are doing 2 comparison.so for three numbers we have to do 2*3 comparison.
(E)
In 3 element array if first two element is same then median is this element only.
Because it doesn't depends on third element .either it is big or small the first or second which is same is going to be median of this array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.