[Cs5500] spec for valid

[Karl Lieberherr]

Hi Greg:

I want to be very careful with software that evaluates the performance
of a student's avatar.
You are right that the current valid function is not kicking an avatar
when she provides a correct decision tree.
The playground admin is too permissive and stamps too many decision
trees as legal.

The following scenario could happen. Alice proposes HSR(9,2)<=5. Bob
refutes.  Alice provides her
decision tree of depth 5 that passes the valid function but which is
not working. The admin says that Alice
defended her claim. But it is with a wrong argument and Bob might say
that it is unfair that Alice won.

Therefore, we are going to repair the playground and the spec for
valid is below. Any refutation or defenses
of this spec?

-- Karl

On Sun, Nov 20, 2011 at 1:18 AM, Greg I Kerr <kerr.g at husky.neu.edu> wrote:
> Hi,
>
> Unfortunately I think we had a miscommunication. I did not implement my own
> valid function. I used the one from the playground. Yes, I knew that valid
> was broken, but it's only broken for "unnatural" trees. It seemed to me that
> one would have to work hard to actually generate a tree that slipped wrongly
> through valid. Why would anyone do all that work when it would be easier to
> just return the correct tree?
> Truthfully I am not convinced that any avatar was harmed in the tournament
> because of the behavior of valid. Have you seen an example of valid falsely
> rejecting a valid solution? I have not, and that would be the harmful case.
> I'm CCing David on this as we have had some fruitful conversations on the
> matter.
> Regards,
> Greg
> On Sun, Nov 20, 2011 at 1:11 AM, Karl Lieberherr <lieber at ccs.neu.edu> wrote:
>>
>> Hi Greg:
>>
>> A decision tree for HSR(n,k) is valid if
>> (1) the tree is a binary search tree with inner nodes 1..n-1 exactly
>> once and leaves 0..n-1 exactly once (left nodes are < root, right
>> nodes >= root, for all subtrees).
>> (2) all paths from the root to a leaf have at most k left branches.
>>
>> Do you agree with this spec for your valid function?
>>
>> -- Karl
>
>