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.

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....

This is only a preview of the solution. Please use the purchase button to see the entire solution


or $1 if you
register a new account!

Assisting Tutor

Related Homework Solutions

Benchmarking Bellman-Ford's Algorithm
Homework Solution
Bellman Ford
Single Source
Shortest Path
Critical Operation
Test Plan
Lessons Learned
Get help from a qualified tutor
Live Chats