[Cs4800] Playgrounds HSR and MMG under attack

[Ravishankar Rajagopal]

Hi Dennis,

I agree with your first example that although the solution is not valid,
the "as-is" valid function would return true for the below solution. It
satisfies the three conditions that i had mentioned in an earlier mail and
is the not correct for the same reason as Greg's example.

As for the second example, I am not sure if I clearly understand your
claim. The valid function would return true for the instance (1,0) and
HSRSolution = Simple(0). Is your argument that it does not return true even
though it is the right solution?

Regards,
Ravi Rajagopal

On Sat, Nov 19, 2011 at 10:40 AM, Karl Lieberherr <lieber at ccs.neu.edu>wrote:

> Hi Ravi:
>
> here are two more refutations of the HSR valid function. Please check
> them and give feedback to Dennis.
>
> Sorry for the delay.
>
> -- Karl
>
> ---------- Forwarded message ----------
> From: Karl Lieberherr <lieber at ccs.neu.edu>
> Date: Fri, Nov 18, 2011 at 12:00 PM
> Subject: Re: [Cs4800] Playgrounds HSR and MMG under attack
> To: Dennis Zografos <dzog at ccs.neu.edu>
> Cc: Greg I Kerr <kerr.g at husky.neu.edu>, CS4800 Mailing List
> <cs4800 at lists.ccs.neu.edu>
>
>
> 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.
> >
> >
> >
>
-------------- next part --------------
HTML attachment scrubbed and removed