[Cs5500] Fwd: Playgrounds HSR and MMG under attack

[Karl Lieberherr]

Hi Karan:

Software development projects sometimes take unexpected turns.

The graduate class has tested those playgrounds and found them to be
good. Now we need to defend them!

Get the playground testers who tested the playgrounds to help Ravi.
Repair the playgrounds if needed.

-- Karl

---------- Forwarded message ----------
From: Karl Lieberherr <lieber at ccs.neu.edu>
Date: Fri, Nov 18, 2011 at 12:46 AM
Subject: Playgrounds HSR and MMG under attack
To: CS4800 Mailing List <cs4800 at lists.ccs.neu.edu>


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