[Cs5500] [Cs4800] Playgrounds HSR and MMG under attack

[Karl Lieberherr]

Hi Greg:

you have refuted the professor. I claimed that for all inputs the
valid function properly checks for valid decision trees but you give
an input which refutes my claim. Matthew Strax-Haber was the first to
alert me that there is a bug crawling around in the playground.

You said you implemented a fast and correct valid method that you used
to test that all your decision trees for up to 1000 rungs are valid.
Please send it to me privately.

-- Karl

On Fri, Nov 18, 2011 at 1:03 AM, Greg I Kerr <kerr.g at husky.neu.edu> wrote:
> Hi,
>
> Valid claims the following tree is valid when it cannot be:
> HSRInstance inst = new HSRInstance(10,3);
> HSRSolution s0 = new Simple(9);
> HSRSolution s1 = new Simple(1);
> HSRSolution s2 = new Simple(7);
> HSRSolution s3 = new Simple(3);
> HSRSolution s4 = new Simple(4);
> HSRSolution s5 = new Simple(8);
> HSRSolution s6 = new Simple(6);
> HSRSolution s7 = new Simple(2);
> HSRSolution s8 = new Simple(5);
> HSRSolution s9 = new Simple(0);
>
> HSRSolution q2 = new Compound(s1, s2, 2);
> HSRSolution q1 = new Compound(s0, q2, 1);
> HSRSolution q4 = new Compound(s4, s3, 4);
> HSRSolution q6 = new Compound(s5, s6, 6);
> HSRSolution q5 = new Compound(q4, q6, 5);
> HSRSolution q3 = new Compound(q1, q5, 3);
> HSRSolution q8 = new Compound(s7, s8, 8);
> HSRSolution q9 = new Compound(q8, s9, 9);
> HSRSolution q7 = new Compound(q3, q9, 7);
> Picture of tree is here: http://pastebin.com/Rc2JHC1a
> - Greg
> On Fri, Nov 18, 2011 at 12:46 AM, Karl Lieberherr <lieber at ccs.neu.edu>
> wrote:
>>
>> 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
>>
>> _______________________________________________
>> Cs4800 mailing list
>> Cs4800 at lists.ccs.neu.edu
>> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
>