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

[Ravishankar Rajagopal]

Hi Dennis,

The requirements that you have provided for a valid solution are precisely
the ones that we (myself and MSD) team have decided upon and are working
towards. Although Matthew's loosening of restrictions in terms of allowing
at least one is theoretically valid, I would think that for clarity
purposes it is best to stick to having 'exactly one' restriction on the
leaves and the internal nodes

Regards,
Ravi Rajagopal

On Sun, Nov 20, 2011 at 9:05 AM, Dennis Zografos <dzog at ccs.neu.edu> wrote:

> Hi,
>
> Some questions/concerns about this:
>
> The original valid() was both too restrictive and too permissive.
>
> Yours is too permissive, in a new way.
>
> hsr(0,*) is not a valid instance.  Its solution is not h0 as your
> tests claim.  Its solution does not exist.  A safest rung can not
> be determined when there are no rungs.  Quality is also
> definitionally undefined for n=0; it looks like you've hacked the
> quality function to define it.
>
>
> From your requirements:
> "All rungs from 0..n-1 are represented at least once"
>
> This is fuzzy.
>
> To clear it up, let's make a discrete shift from HSR terminology
> to tree terminology.
>
> Valid hsr solutions are bounded by [0,n-1] for leaves and [1,n-1 ]
> for questions.
>
> Each leaf appears exactly once.
>      => There are n leaf nodes.
>
> Each question appears exactly once.
>      => There are n-1 question nodes.
>            (=> n>0)
>
> I would also be careful about stating solution=>BST without
> mentioning the specifics of ordering.
>
> ----
>
> How about this?
>
> Requirements for a valid solution:
> - Strictly binary tree (2-tree)
> - Tree is ordered: < to the left, ≥ to the right
> - Exactly n leaf nodes in [0,n-1] with no repeats
> - Exactly n-1 question nodes in [1,n-1] with no repeats
> - No more than k subsequent left branches
>
>
>
>
>
> ----- "Matthew Strax-Haber" <straxhaber at gmail.com> wrote:
>
> > 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
> >
>
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
-------------- next part --------------
HTML attachment scrubbed and removed