# Use of Piazza for Algorithmic Problem Solving based on the Quantifier Game

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:

## Piazza Playground Interface

This information is embedded in the homework description. It is used to define a playground for scholars whose interface is given below.
• type Instance
• type Solution
• type InstanceSet. The first quantifier ranges over this type.
• function valid: Option < String > valid(Instance instance, Solution solution)
• function quality: double quality(Instance instance, Solution solution)
• function belongsTo: Option < String > belongsTo(InstanceSet is)
• function valid: Option < String > valid(InstanceSet is)
• type Claim. A claim consists of an InstanceSet, the quality and a "protocol" depending on whether we have ForAllExists or ExistsForAll claims.
If the option is Some a string is returned that gives the reason for the violation (false). If the option is None, the test succeeded (true).

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.

## Piazza Scholar Interface

The four key functions are: propose, oppose, provide, solve.
• function propose: Claim propose (List < Claim > forbiddenClaims) propose returns a claim and might be restricted to proposing a claim that has not been proposed yet. The returned claim should be true and optimum.
• function oppose: List < OpposeAgreeAction > oppose(List < Claim > ). OpposeAgreeAction: Refute | Agree_with_same_quality | Agree_with_stronger_quality. Agree_with_stronger_quality means strengthening: has a field representing the new quality which is of type double.
• function provide: Instance provide(Claim). Provide an instance that belongs to the instance set of the claim.
• function solve: Solution solve(Instance i). Solve the instance.

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.

• transition Refute: RefutationProtocol(ExistsP, ForAllP, C)
• transition Agree_with_same_quality: RefutationProtocol(ForAllP, ExistsP, C)
• transition Strengthen = Agree_with_stronger_quality: RefutationProtocol(ForAllP, ExistsP, Cs) where Cs is stronger (wrt quality) than C.
RefutationProtocol(ExistsP,ForAllP,C) collects data using provide and solve and evaluates the predicate of the protocol. C is either of the form ForAllExists or ExistsForAll which determines the order of data collection.

## Piazza Playground Police

All students in the class play the role of policing the playground.
• Are proposed and strengthened claims valid?
• Do instances provided belong to the instance set?
• Is the solution valid for the given instance?
• Was the claim properly refuted or defended. Was the claimed quality achieved?
• etc.

## Standard Testing and Documentation

Before you apply your software in the playground you need to test it with your own test cases and you need to document it. When it is time to turn in your algorithms, we expect the following: Source code for propose, oppose, provide and solve. Test cases and a justification why they are adequate. Documentation of your algorithms including obstacles you encountered.

## Revealing Information about Homework Solution Approach

When the scientific dialog prescribed by the refutation protocol is carried out for a claim some information about the solution approach is revealed. This revelation is intentional because the quantifier game is both collaborative as well as competitive. When you refute or strengthen someone's claim, you must reveal a "clever" instance or a "clever" solution that says something about your secret ideas.

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.