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.
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 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.
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.