[Cs4800] Playgrounds HSR and MMG under attack

[Dennis Zografos]

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)?

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!?


> 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.