Collective Problem Solving on Piazza

We want to give you feedback on your algorithmic thinking through formal debates with your peers. This will give you an impression of what you and others can do at this stage. Those debates on Piazza will be like a good in class discussion about solving a problem with the difference that you have more time to respond. You can employ software to give better responses during the debate.

Some of the problem solving tasks we will approach collectively through Piazza. Because we have 50+ students we have to be careful that we don't have information overload. Therefore, try to find the optimal solutions for the claims and only post when you think you have found the optimum. Test your defense with your partner before you post on Piazza. Also only post on Piazza, if you you make a contribution to the current algorithm lab. If someone already has made a stronger or equal claim on Piazza than your planned claim, you should not post.

The debates are structured according to the claims and you will do best in those debates when you have designed and implemented an optimization algorithm that finds the optimum quickly. When you don't implement it carefully, your algorithm might run for a very long time and that does not make you competitive in the debates.

Optimization Problems

Given is a claim family with a stronger relation: c1 ==> c2 means that c1 logically implies c2 and (c1!=c2). ==> is logical implication where the arguments are distinct. Intuitively, c1 is "harder" to defend than c2. We also say that c2 is weaker than c1. Our objective is to find the strongest claim in a claim family.

Given is a claim family c(q in Q) where q ranges over a finite set of numbers Q with a minimum element qmin and a maximum element qmax. We assume that c(qmax) is true and c(qmin) is false. We define a derived claim: c-min() = (Exists q in Q: c(q) and (ForAll q' < q, q' in Q: !c(q))).

This claim has the property that it is trivially true. To find the best q, let's call it qopt, we enumerate all numbers in Q between qmin and qmax until we find qopt. This works because Q is finite.

Therefore, when we ask: "who wants to be verifier of c(q0)?", everybody wants to be on the verifier side. However, when you take the verifier side, you also have to tell us what your qopt is. We will then choose two verifiers with the best values for qopt and they will carry out the debate about the claim.

The HSR Lab

Recall that a lab is a claim family together with participants who contribute to the lab by designing algorithms for defending the claims. We deal with the following specific example: HSR(n,k,q) there is an experimental plan for a ladder with n rungs, k jars and a maximum of q questions to determine the highest safe rung. (That means the depth of the experimental plan, represented as a tree, is q.) The optimization problem is about minimizing q for a given n and k.

The goal of the HSR lab is to completely and efficiently automate the decision and defense of HSR related claims. And a later point we want to see your algorithms together with an analysis of their running time. The HSR lab is about optimally balancing trees under constraints.

More details about HSR are here: http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs5800/f13/piazza/hsr/HSR-problem-CS5800-1.pdf. This document gives important information about the debating language to be used so that we can read each others experimental plans. It also defines the concept of a correct experimental plan.

The Piazza claims for this exercise are defined by: HSRnk(n in Nat, k in Nat <= log(n))= Exists q in Nat < n: (HSR(n,k,q) and (ForAll q' < q, q' in Nat: !HSR(n,k,q')).

In other words, we consider the sub claim family where n and k are fixed: HSR(n,k,*) and we want to find a q so that there is no stronger claim than HSR(n,k,q). During the debate the participants will reveal their experimental designs in the form of trees.

HSR(n,k,q) ==> HSR(n,k,q')) if q < q'.

HSR(7,2,3) ==> HSR(7,2,4)

The first claim on Piazza will be: HSRnk(25,2).

A later claim on Piazza might be HSRnk(100000,35). That means your algorithm needs to be clever and cannot do extensive search to find the optimal experimental design.

Example of Piazza Dialog

claim HSRnk(25,2)

Prachi is verifier with qopt=9.
Chaitali is verifier with qopt=8. Nobody has a lower qopt.

Prachi and Chaitali prepare for the debate. 
They prepare their experimental designs in the agreed upon format.

Although Chaitali is a verifier, she gets by a random flip, forced to be
falsifier. So we have:
Prachi: verifier
Chaitali: forced falsifier

Who goes first?
Let's look at the logical structure 
of the claim in prefix form:
(Exists (and (Exists) (ForAll (! (Exists))))).
Therefore Prachi starts first by the debating rules.

Prachi provides her q=9. Now, Chaitali thinks she can do better,
and as falsifier, she will choose the right-hand side of the and,
again as falsifier, she will choose q'=8.

Now we are at: !HSR(25,2,8). Because of the negation, we switch the participants,
by the debating rules:
Chaitali: verifier
Prachi: falsifier
The claim is: HSR(25,2,8).

HSR(25,2,8) only has one existential quantifier, so Prachi can just watch
as Chaitali reveals her correct experimental plan for HSR(25,2,8).

Chaitali, even as forced falsifier, won the game. She has defended her claim
that qopt=8.

What is Chaitali's balancing strategy? Can Chaitali's solution be strengthened? Everybody can now see Chaitali's solution for q=8? Can you better balance that tree? What is the optimum balancing strategy? How does it work for any n and k?

Above we have assumed that everybody followed the debating rules. If someone tries to violate a debating rule, like delivering an incorrect experimental plan, she is disqualified.

You should develop an algorithm to check that an experimental plan is correct.