Guidelines for writing pseudocode C Java Python instructions are fine But do not write object oriented additions Do not declare or use any class Declare only procedures (if necessary) and explain in words what each procedure does, and what is the use of each parameter One instruction per line Match the brackets with a horizontal line Number your lines Write down if your array is indexed 0 n1 or 1 n If you decide to use procedures functions methods from the class (such as, say, DELETE MAX(S) for S a max heap), explain clearly what they do and in what running time Explain the data structures, if any Question Suppose that you have a black box worst case linear time median subroutine Give a simple, linear time algorithm that, given an array A 1 n and a positive integer i n finds the i th smallest element of A Present pseudocode using procedures from the textbook or notes give complete specifications and state the running time of the procedure in terms of its parameters

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 25, 2024

Guidelines for writing pseudocode : C/Java/Python instructions are fine. But do not write object-oriented additions. Do not declare or use any class. Declare only procedures

Guidelines for writing pseudocode:

C/Java/Python instructions are fine. But do not write object-oriented additions. Do not declare or use any class. Declare only procedures (if necessary) and explain in words what each procedure does, and what is the use of each parameter.
One instruction per line
Match the brackets with a horizontal line
Number your lines
Write down if your array is indexed 0...n1 or 1...n.
If you decide to use procedures/functions/methods from the class (such as, say, DELETE- MAX(S) for S a max-heap), explain clearly what they do and in what running time. Explain the data structures, if any.

Question: Suppose that you have a black-box worst-case linear-time median subroutine. Give a simple, linear-time algorithm that, given an array A[1..n] and a positive integer i n finds the i^th smallest element of A. Present pseudocode using procedures from the textbook or notes; give complete specifications and state the running time of the procedure in terms of its parameters.