This term we will be using Piazza for class discussion and developing and debugging your algorithms. The system is highly catered to getting you help and feedback fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.
Through the quantifier game (a special case of the Specker Challenge Game (SCG), also called Scientific Community Game, where the claims are mathematical) you work in a collaborative/competitive mode with your class mates. You will lose points when you make claims that you cannot defend and you gain points when you refute or strengthen a claim made by someone else.
Find our class page at: http://www.piazza.com/northeastern/winter2012/cs4800. You are expected to participate in Piazza discussions by asking good questions and giving correct answers and by making claims that you can defend and by recognizing weak claims made by others and carry through the refutation or strengthening.
We will use Piazza in a semi-structured way to learn about algorithms. You will design algorithms for solving computational problems in a playground. The algorithms you invent you can keep secret for a while; you only need to apply them to specific inputs to defend claims you made or to refute claims made by others. Your class mates will try to figure out the algorithm you use. But after the "trade secret period" has expired (usually after the assignment is due) you must reveal your algorithm as an executable program or giving a detailed pseudo-code description again through Piazza or by a class presentation. This will "lift the boat" by disseminating successful algorithms that have proven themselves and that have been checked by the teaching staff.
We will use a semi-structured discussion format for refuting and defending algorithmic claims in a playground. For communicating instances and solutions, we use JSON. The particular language to be used is defined in each playground.
A domain is defined in terms of a set Instance and Solution and a valid function that checks whether a given solution is valid for a given instance and a quality function which computes the quality of a solution for a given instance. InstanceSet is also a part of the domain and it defines a family of sets of allowed instances. It is appropriate to define the concept of a playground for solving problems in a given area under study. A Piazza playground has the following interface:
A claim makes a prediction about the solve function. It predicts how well the solve function will do when applied to instances in the instance set of the claim. A claim consists of an instance set and has a real number between 0 and 1 which is the quality of the claim. A claim is either of the form ForAllExists or ExistsForAll where the first quantifier ranges over the instance set. A claim has a positive real number q which is the quality that is claimed to be achieved by the solve function for any instance in the instance set. A ForAllExists claim where the instance set is a singleton set, defines a function f:{InstanceSet} -> Solution as follows: ForAll x in InstanceSet Exists y in Solution : quality(x,f(x) >= q. {InstanceSet} is the set of all singleton instance sets allowed. We view the scientific dialog as a game using the Scholar Interface. A Dialog Format is suggested.
The activities of the scholars in Piazza are defined by a finite state machine. The states are: Start, Decision, RefutationProtocol. The RefutationProtocol Explained.
From the Start state there is a transition labeled "propose C" where ExistsP proposes claim C. C should be a claim that can be only agreed with the same quality. The state reached from Start is called Decision. When the opposer FoirAllP arrives, it will always transition into a new automaton called RefutationProtocol with different arguments.
If claims are of the form: ForAll x in X Exists y in Y: p(x,y) where |X|=1, the refutation protocol will reveal the solution for defending or refuting the given claim. For such playgrounds where there is a large selection of claims, we require that claims not be repeated. This makes the game interesting again because now the task is to abstract from the examples seen to a general algorithm that is successful in defending other claims.
For the purpose of getting a discussion going, we divide the refutation protocol into two parts: The first part does not reveal too much information: We just focus on the quality. For example, we say: For claim C I have a solution of quality q0. This can be safely said before the due date. The second part of the refutation protocol is completed after the due date and reveals the specific solution that achieves quality q0.