[Cs5500] Playgrounds HSR and MMG under attack

[Ravishankar Rajagopal]

Hello Professor,

I reviewed the latest code for the valid function in the HSRInstance class
and based on my understanding the valid function does return invalid
results as valid. Although the example that Matthew provided does not seem
to be right, the example that that was later provided by Greg seems to be 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.

I would appreciate some help from someone in the MSD group to help me test
more thoroughly. Thanks.

Regards,
Ravi Rajagopal

On Fri, Nov 18, 2011 at 12:51 AM, Karl Lieberherr <lieber at ccs.neu.edu>wrote:

> Hi Karan:
>
> Software development projects sometimes take unexpected turns.
>
> The graduate class has tested those playgrounds and found them to be
> good. Now we need to defend them!
>
> Get the playground testers who tested the playgrounds to help Ravi.
> Repair the playgrounds if needed.
>
> -- Karl
>
> ---------- Forwarded message ----------
> From: Karl Lieberherr <lieber at ccs.neu.edu>
> Date: Fri, Nov 18, 2011 at 12:46 AM
> Subject: Playgrounds HSR and MMG under attack
> To: CS4800 Mailing List <cs4800 at lists.ccs.neu.edu>
>
>
> It is claimed that the HSR playground and the MMG playgrounds are
> unfair. The discussion of munfair algorithms at the SCG court level
> (like scoring, which applies to all playgrounds) has now shifted to
> the specific playgrounds for which you write avatars.
>
> Ravi, your TA, is checking out the HSR and MMG playgrounds.
>
> So we are back at arguing about algorithms which is a good thing. It
> is an important objective of an algorithms class that you learn to
> defend and refute algorithms.
>
> For the HSR playground, the arguments are about the valid function for
> instances and their solution.
>
> Claim HSR-I: There is an instance i=(n,k) and a solution s (a decision
> tree) to the valid function Boolean valid(i,s) so that valid(i,s)
> holds but s  does not properly compute the highest safe rung for a
> ladder with n rungs and k jars to break.
>
> Claim HSR-II: There is an instance i=(n,k) and a solution s (a
> decision tree) to the valid function Boolean valid(i,s) so that
> valid(i,s) does not hold, but s  properly computes the highest safe
> rung. In addition, there is no decision tree that solves i=(n,k) and
> that passes valid.
>
> The MMG playground is tricky to implement correctly. It is important
> that the admin only rejects solutions that are wrong. The fundamental
> problem is
> that irrational numbers like the golden ratio are only approximated in
> computer memory. Square roots might not be computed well enough by
> Java.
> The playground cannot use comparison operators <,=,> directly on
> doubles. See
> http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Double.html.
>
> The claims MMG-I and MMG-II are analogous to HSR-I and HSR-II.
>
> ===============
>
> We will let you know when the status of those claims is resolved. If
> you have a proof (winning strategy) for one of the claims or its
> negation, send it to us for additional credit. Also send us
> suggestions for improved playgrounds.
>
> -- Karl
>
-------------- next part --------------
HTML attachment scrubbed and removed