Internet Study Groups

Having a large class on algorithms calls for a novel, intelligent approach to facilitate the learning process. We are going to use internet study groups (ISGs) to maximize the communication and hands-on learning between the students.

The above investigation flow describes the activities happening in an ISG to support learning. An ISG involves two kinds of scholars: owners, which is the teaching staff, and participants, which are the students belonging to the study group. The red rectangles with rounded corners describe actions made by the owners who pose questions to be solved by the students. What is interesting in this approach is the experimental design created for each question in a very systematic manner. The running of the experiments gives the students feedback on whether they gave the right answer and whether they have a good support strategy for their answer.

During the experiments, the student engage in games where they try to push each other into contradictions. The students who manage not to be pushed into contradictions help the other students to learn about the topic of the question currently studied by the ISG. The students who manage not to be pushed into contradictions accumulate a positive reputation in the study group. The games happen without involving the teaching staff provided the experimental design rules set by the teaching staff are followed. We use a gentlemen approach to enforcing that all game rules are properly followed.

The ISG records all games and the scientific discourse which happens during those games.

An ISG is based on a claim family defined by a parameterized, interpreted logical formula over a structure. The claim family defines the requirements for the algorithmic problem we want to solve.

To start, the focus is on one claim in the claim family. As a running example, we use the very simple claim family over the structure of real numbers:

CF(c in [0,2]) = ForAll x in [0,1] Exists y in [0,1]: x+y >= c
Consider CF(0.5), which turns out to be true; while CF(1.5) turns out to be false. The algorithmic problem behind this claim family is a function f(x) which maps an x to a y which satisfies the predicate x+y>=c. A fundamental insight from logic is that any interpreted logical formula f can be mapped into a semantic game G(f) to support or refute the claim. In a semantic game there is a participant who takes the verifier side and a participant who takes the falsifier side. The verifier wants to argue that the claim holds while the falsifier wants to argue that the claim is false. For the claim CF(0.5), the falsifier might provide a value of 0 for x while the verifier provides 1 for y which makes the predicate true and the verifier has won the game. For a true claim, the verifier has a winning strategy for the semantic game associated with the claim.

Semantic games are folklore knowledge: An Explanation of Semantic Games. They are sometimes called Tarski games or Hintikka games. In the above explanation only the word "game" is used where we use "semantic game".

Here is a complete, succinct definition of semantic games.

A study group works as follows: The members of the study group are called participants. A claim c is proposed by the teaching staff or a participant within the study group. Scholars will take sides on claim c and then support their chosen side through actions. The two sides are: either they want to be verifier or falsifier of the claim c. If all want to be verifier or falsifier, we select two students to play a semantic game and we randomly force one student to take the opposite position, playing devil's advocate. If there is at least one verifier and at least one falsifier they play one semantic game.

Formal Debates are a good tool to explain semantic games.

You should use formal debates to improve and check your claims you make in homeworks before you turn them in. There are several reasons for this: (1) We want you to successfully defend your claims that you make in homeworks against a partner in class. If you do, you have confirmed that your thinking might be right. If you don't there must be an error in your thinking and your partner will give you a strong hint where to look for the error. Both cases are win-win situations: you confirm or you learn and improve your understanding. (2) Playing devil's advocate is fun if both you and your partner have the same opinion but maybe for different reasons. One of the reasons might be wrong. The devil's advocate can never lose. It can play aggressively and unexpectedly. This might lead to a new idea. (3) We want you to turn in homeworks that have a convincing defense strategy for the claims you make. Your partner might find a hole in your defense strategy. (4) There are many talented students in the class who deserve to take on a teaching role by passing on their skills to others. (5) Have fun with the competitive nature of the little inventions and improvements you make during playing the game.

All this checking and learning is accomplished by semantic games which precisely define the scientific dialog for a given topic (claim family).