[Cs5500] Playgrounds HSR and MMG under attack

[karan bhat]

Hi Ravi,

As requested Madhu and Haoran will be helping you out for solving
issues or defending HSR playground. The computational problems in MMG
playground are issues where we will have to come to a common
consensus, this we will discuss with the professor test it again and
let the undergrads know.

Thanks,
Karan Bhat


On Fri, Nov 18, 2011 at 12:09 PM, Ravishankar Rajagopal
<rajagopal.r at husky.neu.edu> wrote:
> 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
>
>