Side-Choosing Games Specialized for MOOCs

The instructor defines a problem solving domain by giving a notation for expressing instances (a language for Instances, e.g., in JSON), class of instances (a predicate setOfInstances), and solutions (a language for Solutions, e.g. in JSON). Since not every solution expressible in the solutions notation can be a correct solution for any given instance, the instructor provides a predicate that decides whether a solution is a correct solution for a given instance (correct((Instances,Solutions):Boolean). The instructor provides a predicate that decides whether an instance belongs to a particular class of instances (setOfInstances(Instances): Boolean).

Interface Summary for defining a Problem Solving Domain:
language Instances
language Solutions
predicate correct(Instances,Solutions)
predicate setOfInstances(Instances)

The students start with limited knowledge about their ability to find solutions for a given instance or class of instances. In an SCG game, they are encouraged to put out objectively refutable claims about their ability to solve a certain instance or class of instances. Other game participants are also encouraged to examine claims put out by others and either agree or refute them.

As the game proceeds, students get targeted feedback, from other students, about: 1. misconceptions they have about their ability to solve problems. 2. their relative ability to solve problems.

Instructors only need to intervene at the end of all games for a fixed claim if the students conclude that a true claim is false or a false claim is true. All the games are peer-graded in conjunction with the instructor-provided functions mentioned above.

Where is the side-choosing game?

Claims are about a single instance or a class of instances and how they can be solved. Claims are formulated as predicate-logic claims and the side-choosing games are semantic games.
ForAll instance in Instances and satisfying setOfInstances(Instances)
Exists solution in Solutions
  solution is correct for instance
A student who makes this claim is confident that she has a correct algorithm that works for any instance satisfying setOfInstances and produces a correct solution. The "algorithm" might need input from the student or could be all automated.

What is interesting in this special case? The students don't see the query written by their opponent. The students will write a "test case" based on their attempts in getting their query tested. They will likely use test cases on their opponent where their query failed initally. Instead of peer grading the instructors could use test cases that capture typical student misconceptions. But this requires more work for the instructors and does not create an interaction between the students.

For the above claim the students don't exchange their queries (blackbox testing). The following claim asks them to exchange their queries which they study to provide a better answer (whitebox testing).

Exists function f: Instances to Solutions
ForAll instance in Instances and satisfying setOfInstances(Instances)
  solution f(instance) is correct for instance

It will be important to give the player, who loses while not forced, a heavy penalty to encourage forced players to try hard to test the programs of their opponents.

It is best to divide the students into teams of three. The third student plays the role of the administrator and checks that the game rules are followed. This is a low-tech implementation of the this technology and does not require additional software.

Example 1: Teaching Query Design and Implementation

We look for a sequence of queries to implement a query specification. We assume a relational schema is fixed. Instances are a pair consisting of (1) tables satisfying the schema and (2) a query specification. Solutions is a table satisfying the query. We are looking for a program (avatar), implemented in, e.g., SQL. Because this is a well-understood domain, the instructor will provide a perfect query (avatar).
Query result for a fixed query specification:

Fix schema in Schemas
Fix querySpecification for schema 
ForAll tables satisfying schema
Exists solution (table) in Solutions
  solution is correct for schema, tables and query specification
Possible scenario: A student who makes this claim is confident that she can implement the query correctly so that it works for any database. The opponent would try to construct a "difficult" database that would derail the query implementation by showing that it gives a wrong result. Notice that there is one quantifier alternation and therefore there is student interaction.
Query implementation for a fixed query specification:

Fix schema in Schemas
Fix querySpecification for schema 
Exists queryImplementation
ForAll tables satisfying schema
  queryImplementation produces Table which is correct for schema, tables and query specification
Possible scenario: A student who makes this claim is confident that she can implement the query correctly. Query implementation is visible to opponent.

Alice provides her query implementation to Bob. Bob studies it and tries it out on a few data bases and tries to find one where the query fails. Here Bob has more information because he sees Alice' query implementation.

Next we consider claims involving partial queries. Those are queries with UNKNOWNs sprinkled in them. So the students get a partial solution but they have to complete it in a structured way.

Complete a partial query: find UNKNOWNs for a fixed query specification and partial query:

Fix schema in Schemas
Fix querySpecification for schema 
Fix partial query
Exist UNKNOWNs for partial query
ForAll tables satisfying schema
  completed query finds solution
  that is correct for schema, tables and query specification
A student who makes this claim is confident that she can complete the partial query so that it works for any database.

This kind of claim is useful for checking the students, provided UNKNOWNs have only one possible value.

Possible scenario 1 (assuming UNKNOWN has only one possible value): Instructor provides the fixed quantities. Student finds UNKNOWN Blackboard checks that the UNKNOWN is correct.

Possible scenario 2: Alice provides UNKNOWN, runs query and it works. Bob provides a database where the query fails. Alice' UNKNOWN must be wrong. Notice that Alice learned from Bob through peer teaching.

Query result for a fixed database:

Fix schema in Schemas
Fix querySpecification for schema 
Fix tables satisfying schema
Exists solution (table) in Solutions
  solution is correct for schema, tables and query specification
  and has value c

(the query is an aggregation query which returns one number. 
We solve a single instance.)
A student who makes this claim is confident that for the given database his query is correct. The check is done by using the perfect avatar from the instructor. Notice that there is no quantifier alternation and therefore there is no student interaction. Good for automated checking using, e.g., Blackboard.

To partition the material into learning units consider query features. 1) Table selection, join, projection 2) The basic PoSQ queries: select (filter), widen, aggregate, eliminate duplicates. Nested queries. 3) action queries, etc.

What is the first query kind in the shortest query implementation for a given query specification (using PoSQ)? Shortest: so that filler queries (like an empty selection) are excluded.

Query kind of first subquery for a fixed query specification:

Fix schema in Schemas
Fix querySpecification for schema 
Exists queryKind (in PoSQ query kinds)
Exists queryImplementation
ForAll tables satisfying schema
  queryImplementation produces Table which is correct for schema, tables and query specification and first aubquery of queryImplementation is of queryKind
Possible scenario: Student Alice claims the kind of the first subquery is queryKind=aggregation. Alice provides her queryImplementation and tests it on the provided data base (starter file) and it gives correct result. Bob provides a different database where the query fails. Something must be wrong with Alice' understanding. It could be that she forgot an "eliminate duplicates" subquery as the first subquery.

Informal Query Specifications

The queries are specified in English. Such as: "Which products have never been ordered by any customer. List product names." Occasionally, there are ambiguities in those queries. We assume that the queries are specified without ambiguities.

Example 2: Spreadsheet Programming

in preparation

Instances: table of cells
Solutions: formula draggable over a table that computes correct cell values

To partition the material into learning units consider formula features.

Basic Excel: dragging of formulas, absolute and relative addressing,
summing, PMT function, named ranges

Boolean Logic and conditional expressions,
See (this is dated: from 2011): http://www.ccs.neu.edu/home/lieber/courses/se-courses/cs5500/sp11/projects/playground-designer-user-guide.html See: SCG Court http://www.ccs.neu.edu/home/lieber/courses/se-courses/cs5500/sp11/GenericSCG/GenericSCG-march-11/src/ Spring 2011 implementation: http://www.ccs.neu.edu/home/lieber/SCG/assembla/managing-sw-dev-shared/trunk/GenericSCG/src/ http://www.ccs.neu.edu/home/lieber/SCG/