Suppose that the top-level call to Randomized-Select (page 216) is guaranteed to receive legal arguments, with 1 ≤ p ≤ r ≤ A.length and 1 ≤ i ≤ r − p + 1. Consider deleting lines 1 and 2 of the procedure. Indicate which of the following statements is true and give a convincing argument for your claim:
The procedure would no longer be correct. It would generate a nonterminating computation, access the array out of bounds, or return the wrong answer.
The procedure would still be correct, but would now be asymptotically less efficient: it would take more than quadratic time in the worst case or more than linear time in the expected case.
The procedure would still be correct and, asymptotically speaking, would be unchanged in efficiency. Any change in the time taken would be by at most a constant factor.
This problem is worth 1 grade point.
Do Problem 11-2, parts a and b only, on page 283. This partial problem is worth 2 grade points.
Do Problem 11-4, part d only, on page 284. This partial problem is worth 1 grade point.
Do Exercise 12.1-1 on page 289. This exercise is worth 1 grade point.
Do Exercise 12.2-4 on page 293. This exercise is worth 1 grade point.
Do Exercise 12.3-3 on page 299. You must give your answers in Theta terms together with a justification for each one. This exercise is worth 2 grade points.
Do Exercise 13.1-1 on page 311. This exercise is worth 2 grade points.
Do Exercise 13.2-1 on page 313. This exercise is worth 2 grade points.