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

[Karl Lieberherr]

Hi Karan:

Here is the successful refutation of the HSR playground. Please work
with Ravi and the HSR playground testers to provide a correct valid
function.

-- Karl

---------- Forwarded message ----------
From: Greg I Kerr <kerr.g at husky.neu.edu>
Date: Fri, Nov 18, 2011 at 1:03 AM
Subject: Re: [Cs4800] Playgrounds HSR and MMG under attack
To: Karl Lieberherr <lieber at ccs.neu.edu>
Cc: CS4800 Mailing List <cs4800 at lists.ccs.neu.edu>


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