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
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse 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