CLRS solution seems meaningless as one line make me skeptical

Question

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)

Taction

The solution makes no sense without the code that it's talking about. Can you show the code as well? – Blackstone

I have edited my question. Hope this will help you to understand where my confusion is. – Taction

Answer 1

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:

Calling a 0-length array would mean that the second argument is larger than the third argument by 1. So, if the call is made on line 8, we would need that p = q - 1 + 1 = q.

However, i is assumed to be a positive number, and to be executing line 8, we would need that i < k = q - p + 1 = 1, which means that i ≤ 0, a contradiction. The other possibility is that the bad recursive call occurs on line 9. This would mean that q + 1 = r + 1. But if line 9 runs, it must be that i > k = q - p + 1 = r - p + 1. This would be a nonsensical original call to the array though for i should be in [1, r - p + 1].

Ballistic

Thank you for sharing the links. I have a doubt, I am confused with the meaning of 0 length array. Is that means, the array is an empty array? Like there is no element in the array? If so, then second argument should be equal to the third argument right? – Taction

If I am not wrong A[q] is the pivot. So elements p to q-1 should be less than A[q], For example there are 10 elements in the array and indexing staring from 1. The q index let's say 6. So the elements on index 1 to 5 should be less than element in index 6. Now, p=1 and q-1 = 5 as per my example. Now you said for a 0 length array second argument which is p should be 1 larger than third argument which is 5. So as per my example p should be 6 and q-1=5. Then how will it work? – Taction

Lastly, Can you please take a look #71137157 – Taction

@encipher: In CLRS, arrays are indexed starting at 1 and array ranges are inclusive, so "A[1..j] indicates the subararry of A consisting of the j elements A[1], A[2], ..., A[j]" (page 20, Pseudocode Conventions). So A[i..i] has one element, A[i], and thus A[i..j] can only be empty if j<i. (It's correct that qis the pivot.) – Ballistic

What the person who filed that bug said (not me!) is that in order for the recursive call to indicate an empty array (range), it is necessary that the parameter p be greater than (not equal to) the parameter r. In the call RANDOMIZED-SELECT(A,p,q - 1,i), that would mean that p > q - 1, which is impossible since q - p + 1 (k) is greater than i and i is at least 1. – Ballistic

(Actually, I have no idea how CLRS intends to represent an empty range, because the book doesn't use them afaik, but [i..(i-1)] is a pretty common representation.) – Ballistic

I still did not get you. If I take an example like i=1 and j=5, You said A[i..j] can only be empty when j<i. That means j should be 0 because i =1. But the array indexing starting from 1 then how can be j=0? It is not a legal indexing and bit confusing. – Taction

@Encipher: I'm not to argue that. I wouldn't normally use inclusive indexing. But the textbook does, and I can't change that. It's clear in the text that A[1..1] is a range of A containing 1 element. Certainly, A[0] is not a valid index. But the fact that it would be meaningless does not in itself prove that RECURSIVE_SELECT(A, p, r, i) cannot be called with r = 0. (Or, in general, with r < p.) That's what the exercise is asking you to prove. I think you can probably prove it, and you're just wasting your time trying to understand some random internet person's erroneous proof. – Ballistic