[Cs5500] Fwd: Reg: Valiidity of Valid Method in HSRInstance Solution

[Karl Lieberherr]

Here is Ravi's evaluation why Greg is right. -- Karl


---------- Forwarded message ----------
From: Ravishankar Rajagopal <rajagopal.r at husky.neu.edu>
Date: Fri, Nov 18, 2011 at 1:04 PM
Subject: Reg: Valiidity of Valid Method in HSRInstance Solution
To: Karl Lieberherr <lieber at ccs.neu.edu>


The example that that was provided by Greg is a proper counterexample.
The decision tree can be seen in the below link for HSR(10,3)

http://pastebin.com/Rc2JHC1a

All the valid function seems to be doing is

1. There are no more jars broken than k along any path from the root
to each of the leaves.
2. Testing if none of the internal nodes(question in Compound
solutions) repeat and they fall exactly once between 1 and n-1
3. Testing if none of the leaves (simple solutions) repeat and they
fall exactly once between 0 and n-1

Greg's example satisfies all of them even though it is not a valid
solution. In fact for the same instance you could construct several
invalid decision trees which satisfy the above three.

While this is with regard to the false positives, since as per points
2 and 3, the method check for leaves and internal nodes being
available exactly once, as per our discussion yesterday the definition
of what is valid determines if there are false negatives or not.


Regards,
Ravi Rajagopal