[Cs4800] Playgrounds HSR and MMG under attack

[Karl Lieberherr]

Hi Dennis:

On Fri, Nov 18, 2011 at 1:25 AM, Dennis Zografos <dzog at ccs.neu.edu> wrote:
> Oh, so valid(i,s) is supposed to actually check if the *solution*
> is *correct* (as in, s actually finds the right q for i)?

Yes, it checks that the decision tree properly determines the highest safe rung.
But it does not care about the depth.

>
> For some reason, I thought this function was only supposed to be
> checking for *syntax*.
>
> Is valid(i,s) the only solution-checking happening in the HSR game!?

Yes. The quality function "grades" the solution: it checks the quality
of the solution.

We will check the refutations below.

-- Karl

>
>
>> 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.
>
> i=HSR(2,1)
> s=(1 y h1 n h0)
>
>
>> 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.
>
> i=HSR(1,0)
> s=h0
>
>
> -Dennis
>
>
> ----- "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.
>
>
>