Question 1:
The linear time median find algorithm of the set for which the median is to be found into groups of 5. Why does this not work with groups of 3 elements?
Question 2:
How can we get a list of post order numbers in sorted order without sorting? We want linear time not Nlogn.
Question 3:
Do a breath first search proof using a loop invariant to show that a breath first search is capable of computing all layers of a graph.
Question
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
Question 1:We try to apply the same approach as in the case of 5 and 7 elements per sublist.
Since there are 3 elements in the created sublists, at least half of them have 2 elements which are greater or equal with the value of the pivot. More than this, in the current estimation we need to exclude 2 sublists: one containing the pivot and the last sublist (which might have or not precisely 3 elements). This means there are roughly 2*{1/2* ([n/3]-2)} ~ n/3 -4 elements which are either greater or less than median of medians....
By purchasing this solution you'll be able to access the following files:
Solution.docx.
Return to homework library