[Cs5500] New Valid Function - Re: [Cs4800] Playgrounds HSR and MMG under attack

[Matthew Strax-Haber]

Hey Everyone,

So that the students in the undergrad class can start adapting, I'm attaching a modified HSRInstance.valid with counter-examples, documentation, and tests.

Please keep in mind that these have not been approved by the Professor yet, so they are subject to change or refutation.

There are two versions of the new HSRInstance, with tests:
 - Unoptimized: easier to read and debug
 - Optimized: runs faster, same functionality

I have also included a rough specification for what the valid function checks, and a simple counter-example for the old valid function.

Again, this is all subject to change. I've written some JUnit tests to test it (included), but please do send me a private e-mail if you find any bugs.

Best of luck in the next tournament


Best regards,
-- 
~ Matthew Strax-Haber
Northeastern University


On Nov 19, 2011, at 11:01 PM, Karl Lieberherr wrote:

> 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
>> 
>> 
> 
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
-------------- next part --------------
HTML attachment scrubbed and removed
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Packet.zip
Type: application/zip
Size: 12171 bytes
Desc: not available
Url : http://lists.ccs.neu.edu/pipermail/cs5500/attachments/20111119/b6774a45/attachment-0001.zip 
-------------- next part --------------
HTML attachment scrubbed and removed