

Karl Lieberherr

We want to give algorithm learners some control over their learning experiences. Choose your game (hypothesis) in an area where you want to refine your skills. Adults strive for control over their learning experiences.



Short High-Level Definition

Concepts: Hypothesis, Problem, Solution. Problem and Solution can have many different interpretations. For example, a problem may be an algorithm (description).

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

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

Choose a hypothesis with your partner scholar. Scholar 1 will first propose the hypothesis and Scholar 2 must oppose it. Then the roles change: Scholar 2 will propose the same hypothesis and Scholar 1 opposes.

Hypothesis selection takes two forms:

1. You choose from one of the hypotheses that I put into the hypothesis market.

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

Note that the hypothesis should not be refutable; but this is not so important for this version of the game because you play in both roles, as proposer and opposer.

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

The game will often end in a tie when Scholar 1 and 2 sucessfully defend or when they both successfully refute. 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 hypothesis, 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 hypothesis which is "close" to the given hypothesis. Ideally it should be a theorem.

Game Rules

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


Game steps to follow:

Choose hypothesis H
Scholar 1 proposes H
Scholar 2 opposes H
  Scholar 1 provides problem pp that is valid wrt the hypothesis H$
  Check pp
  Scholar 2 provides solution ss to problem pp $
    (depending on the hypothesis, the Scholar 1 and Scholar 2 are exchanged)
    The solution step may involve Scholar 1.
  Check ss
  Check outcome: Hypothesis.refuted(pp,ss)

Reverse roles of Scholar 1 and Scholar 2

Game in a nutshell:
hypothesis, problem, solution
hypothesis = claim about problems and solutions
opposition protocol

Hypothesis Design

Hypothesis design is a non-trivial activity. It is about learning to learn. If you need to explore a domain from an algorithms perspective, it is good to team up with someone and design hypotheses in that domain. Ideally, hypotheses are true statements about the algorithms. They must be efficiently refutable, in general.
Shapes of hypotheses:

mathematical hypotheses
E: exists a problem
A: for all solutions

A: for all problems
E: exists solution

algorithmic hypotheses
E: exists an algorithm
A: for all inputs
Network flow hypotheses
Mathematical hypotheses:

non-negative number
single source node s in V
single target node t in V

definition of flow with capacity and conversation constraints.

based on (7.9)
for all network flow problems G=(V,E) such that f is an s-t-flow

Algorithmic hypotheses:

m = |E|.

based on (7.10)
There exists an algorithm FF 
for all network flow problems 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 problems G with maximum flow f

Mathematical hypothesis:

based on (7.12)
For all flow networks G,