Problem: Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array. Hint: Don't assume that the input array is empty, i.e., p>r. Rather, show that if an empty (sub-)array is ever generated by RANDOMIZED-PARTITION, then a recursive call will not be made on such an empty (sub-)array
This is the exercise problem of Cormen's Introduction to Algorithms Chapter 9. Median and order statistics exercise No. 9.2-1.
The answer should be:
Calling a 0-length array would mean that the second and third arguments are equal. So, if the call is made on line 8, we would need that p=q−1, which means that q - p + 1 = 0.
However, i is assumed to be a nonnegative number, and to be executing line 8, we would need that i < k = q - p + 1 = 0, a contradiction. The other possibility is that the bad recursive call occurs on line 9. This would mean that q + 1 = r. To be executing line 9, we need that i > k = q - p + 1 = r - p. This would be a nonsensical original call to the array though because we are asking for the ith element from an array of strictly less size.
This solution can be found this link
The algorithm it's refer can be found Cormen's Introduction to Algorithms Chapter 9. Median and order statistics section 9.2 Selection in expected linear time
Line number 8: of the algorithm says return RANDOMIZED-SELECT(A,p,q-1,i)
The solution says 2nd and 3rd argument should be equal, So, p=q-1 which means p-q+1 =0 but in the solution it was given q - p + 1 = 0. How could they get that?
Then again for line 9, they calculated q - p + 1 = r - p. As I cannot figure out how did they get q-p+1=0 the equation q-p+1=r-p also meaningless for me.
Can anyone please clarify my doubts?
Thank you.
Algorithm 1: RANDOMIZED-SELECT
RANDOMIZED-SELECT(A, p, r, i)
1 if p == r
2 return A[p]
3 q = RANDOMIZED-PARTITION (A,p,r)
4 k = q - p + 1
5 if i = = k // the pivot value is the answer
6 return A[q]
7 elseif i<k
8 return RANDOMIZED-SELECT(A,p,q - 1,i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
Algorithm 2: RANDOMIZED_PARTITION
RANDOMIZED-PARTITION(A,p,r)
1 i = RANDOM(p,r)
2 exchange A[r] with A[i]
3 return PARTITION (A,p, r)
Yes, I think you are right that the proposed solution is incorrect.
The solutions you are looking at are not part of the textbook, nor were they written by any of the textbook's authors, nor were they reviewed by the textbook's authors. In short, they are, like this site, the unverified opinions of uncertified contributors of uncertain value. It hardly seems necessary to observe that the internet is full of inexact, imprecise and plainly incorrect statements, some of them broadcast maliciously with intent to deceive, but the vast majority simple errors with no greater fault than sloppiness or ignorance. The result is the same: you have the responsibility to carefully evaluate the veracity of anything you read.
One aid in this particular repository of proposed solutions is the bug list, which is also not authored by infallible and reliable reviewers, but still allows some kind of triangulation since it largely consists of peer reviews. So it should be your first point of call when you suspect that a solution is buggy. And, indeed, there you will find this issue, which seems quite similar to your complaint. I'll quote the second comment in that issue (from "Alice-182"), because I don't think I can say it better; lightly edited, it reads: