The Scientific Community Game (SCG) for CS 4800 (Algorithms and Data)

Revised: January 2012.

We want to encourage interaction between algorithm learners by having them refute each others' algorithmic claims. We want to give algorithm learners some control over their learning experiences. Choose your game (claim) in an area where you want to refine your skills. Adults strive for control over their learning experiences.

We learn about algorithms using a high-level "algorithm" executed by humans to improve their learning experience about algorithms. The high-level "algorithm" we call SCG Scientific Community Game = Specker Challenge Game (SCG). The key concept in SCG is a claim. In this course we focus on algorithmic claims. A claim is defined by a refutation protocol which is a little algorithm involving two players to decide whether the claim is "right" or "wrong". Here "right" does not necessarily mean "true" and "wrong" does not necessarily mean "false" because the players may be imperfect. The game is played as a "board" game with the two players jointly enforcing the rules of the game.

We will play the game partially on Piazza to see public performances of the game. In this case we have multiple players out of which two at a time take the initiative to play a game.

The refutation protocols we use are determined by the claims. For example, if the claim is of the form: ForAllExists, the opposer of the claim will first provide an instance and the proposer a solution.

With SCG, we create a learning environment that provides opportunities for collaboration with other algorithm learners. What learning objectives are covered by playing the game? (1) recognizing incorrect algorithms (2) finding inputs that show why the algorithm is incorrect (3) recognizing algorithms with a wrong performance analysis (4) finding inputs that show why the algorithm analysis is incorrect (5) solving algorithm design problems and predicting the resource consumption of the algorithms. (6) describing algorithms at various levels of abstraction (7) distinguishing true algorithmic statements from false algorithmic statements

While the game creates a productive learning environment, only your active engagement with the topic area can realize the skills described in the above learning objectives.

Short High-Level Definition

SCG is a two-player game where each player, called Scholar, proposes and opposes claims about algorithms.

Students form teams of two, each one acting as Scholar.

Claim selection takes two forms:

1. You choose from one of the claims that I put into the claim market for the current assignment.

2. You come up with your own claims using material that we covered in class.

Note that the claims you propose should not be refutable.

Opposition engages two scholars in an opposition protocol which has a success or failure outcome. The opposition protocol for a claim involves the scholars providing instances legal by the claim and solving them to substantiate the claim.

For the opposition role: When Scholar 2 successfully refutes, but Scholar 1 does not then Scholar 2 wins. In other words: For the proposition role, When Scholar 2 successfully supports the claim, but Scholar 1 does not then Scholar 2 wins. In summary, when the outcome of both rounds is the same, we have a draw. If the outcome is different, one of them wins: In the proposition role the supporter and in the opposition role the refuter.

At the end of the game, the scholars get together and propose an improved claim which is "close" to the given claim. Ideally it should be a theorem.

Game Rules

Scholars mutually agree on Claim, Instance and Solution languages to be used. You may use a formal notation defined by a grammar (see Theory of Computation) or an informal notation.

The scholars, through mutual agreement, play the role of the administrator which makes sure the game rules are followed.

Game steps to follow:

Choose claim H
Scholar 1 proposes H
Scholar 2 opposes H following the refutation protocol

Reverse roles of Scholar 1 and Scholar 2

============
Game in a nutshell:
claim, instance, solution
claim = claim about instances and solutions, together with a refutation protocol

Claim Design

Shapes of claims:

mathematical claims
E: exists a instance
A: for all solutions
(EA)

A: for all instances
E: exists solution
(AE)

algorithmic claims
E: exists an algorithm
A: for all inputs

Mathematical claims:

Flow networks: G=(V,E), with each edge a capacity c(e),
non-negative number
single source node s in V
single target node t in V

definition of flow with capacity and conservation constraints.

based on (7.9)
for all network flow instances G=(V,E) such that f is an s-t-flow
  such that there is no s-t path in the residual graph G[f]
there exists an s-t cut (A*, B*) in G for which v(f) = c(A*, B*).

Algorithmic claims:

C = sum [e out of s] c(e).
m = |E|.

based on (7.10)
There exists an algorithm FF 
for all network flow instances nfi FF(nfi) computes a maximum flow
in time O(mC).

based on (7.11)
There is an algorithm that computes
for all network flow instances G with maximum flow f
 an s-t cut of minimum capacity in time O(m).

Mathematical claim:

based on (7.12)
For all flow networks G,
there exists a flow f and a cut (A,B), so that v(f) = c(A,B).