Talk:TADM2E 3.9

From Algorithm Wiki
Revision as of 16:51, 3 May 2020 by Matt (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This problem statement is confusing. I'm not sure that the assumption made by the current solution is correct, due to the problem's difficulty being an '8' in the textbook. Is it possible that the intent of the problem statement is for the phrase "every key in $ S_{1} $ is smaller than any key in $ S_{2} $" to be interpreted as "There exists some key, $ k $, in $ S_{2} $ such that all keys in $ S_{1} $ are smaller than $ k $?"

This interpretation makes the problem significantly more difficult than the interpretation used by the current solution.

The interpretation used by the solution is the interpretation I used at first as well. However, it makes the problem almost trivially easy, far easier than problem 3-8, which is only marked as a '6' in difficulty.

I'm not sure that my new interpretation is correct, because I haven't been able to come up with the required $ O(h) $ solution using the new interpretation.

-- Matt 16:48, 3, May 2020 (UTC)