According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data.

The specific question:

A fellow student wants to compactly store A1 and A2 to support efficient range reporting queries on both arrays using a single binary search. He suggest using fractional cascading (as described in the lecture). Explain why this will not work.

I cannot understand why this will not work.

If we want to search for a specific key in both arrays, why does it matter if the data is related or not? If we have built a relationship between the two arrays, s.t. we can follow a pointer to a predecessor for a given index in A1, is it not irrelevant?

  • $\begingroup$ The wording of the question suggests that the fractional cascading you were taught in class differs from what Wikipedia describes as fractional cascading, and indeed, in the second part of this question, you are supposed to come up with the actual fractional cascading. Compare the description in Wikipedia to what you learned in class, and let us know whether they match. $\endgroup$ – Yuval Filmus Jun 29 '15 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.