Suppose we have an array A of n professors; each teacher has two characteristics: difficulty (a real number in the range (0,10), where a higher number indicates a more difficult teacher) and humor (a real number in the range (0, 100), where a higher number indicates a funnier teacher). You may assume that each value is distinct (no two professors are exactly as difficult or exactly as funny), but not that the precision of real numbers is limited (as floats and doubles are in C++ and Java). Our goal is to determine a set of professors that might satisfy an answer to the question "who is the easiest teacher that is the funniest?" We wish to avoid professors with high difficulty and low humor. We would like to find the largest subset of the input data such that no professor in the chosen subset is both less funny and more difficult than another professor in the set. Note that if professor A is easier than professor B, it does not follow that professor A is also funnier than professor B. For example, if our dataset is: Professor Difficulty Humor
Venabili 4 65
Jones Jr 8 15
Jones Sr 8.5 2
Grant 2 35
Moriarty 10 0
Plum 9 85
Walsh 8.2 90
Then we want to return Venabili, Grant, and Walsh. Note that none of these are meant to refer to anyone at UC Irvine and any similarity is unintentional and a coincidence.
(a) Devise an algorithm which takes as input A and n, and outputs the resulting set. Your algorithm does not need to be particularly efficient, but you may not give an algorithm that enumerates every subset.
(b) Analyze the worst-case runtime of your algorithm using 6-notation
(c) Do you believe your algorithm has obtained the best possible asymptotic runtime? Ex- plain your reasoning. Note that finding the best possible asymptotic runtime is not required to get full credit on this question. 35