Revised: January 2011.
We want to give algorithm learners some control over their learning experiences. Choose your playground in an area where you want to refine your skills. Adults strive for control over their learning experiences. For some homeworks only one playground is defined and you must use that one.
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 (Specker Challenge Game = Scientific Community Game). 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". The game is played as a "board" game with the two players jointly enforcing the rules of the game.
The refutation protocols we use are usually defined by the the instructor to define playgrounds that are most instructive for the given topic. A claim might be HSR(16,2)=6 which informally means: I can solve any "problem" of the kind HSR(16,2) consuming only 6 units of some resource. The following refutation protocol for HSR(16,2)=6, executed by Alice (claimant) and Bob (tries to refute) might be: Bob defines a problem of the kind HSR(16,2) and deposits his secret solution that Alice must discover using at most 6 questions following the rules of HSR(16,2). Those rules limit the kind of questions that Alice may ask to Bob. Bob must give "consistent" answers to Alice according to the rules of HSR. If Alice finds the deposited secret with only 6 questions, she wins because she supported her claim. If not, Bob wins, because Bob forced Alice to contradict her own claim. HSR(16,2)=6 with the above protocol we call HSR-secret(16,2)=6.
Another refutation protocol for HSR(16,2)=6 might be: Bob defines a problem of the kind HSR(16,2) and gives it to Alice to solve it but Bob is allowed to change his secret solution while Alice asks questions. Again, Alice must discover the "floating" secret using at most 6 questions following the rules of HSR(16,2). If Alice finds the floating secret with only 6 questions, she wins because she supported her claim. If not, Bob wins, because Bob forced Alice to contradict her own claim. HSR(16,2)=6 with the above protocol we call HSR-floating(16,2)=6.
The HSR-floating game is more interesting because it invites both Alice and Bob to think harder. The HSR-secret game has more elements of chance because there is the possibility of luckily guessing the secret.
A third refutation protocol is: Bob announces that he refutes (this is equivalent to providing the singleton problem). Alice provides her decision tree for HSR(16,2). And Alice defends successfully if her decision tree is valid and has depth at most 6. HSR(16,2)=6 with the above protocol we call HSR-main(16,2)=6.
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.
The SCG game has several closely related variants. Each homework will describe the variant to be used.
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.
Choose a claim with your partner scholar. Scholar 1 will first propose the claim and Scholar 2 must oppose it. Then the roles change: Scholar 2 will propose the same claim or a strengthened version of the claim and Scholar 1 opposes.
Claim selection takes two forms:
1. You choose from one of the claims that I put into the claim market for the current assignment. For example, for hw1: http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/f10/homeworks/hw1/claims-market
2. You come up with your own claims using material that we covered in class.
Note that the claim 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 claim involves the scholars providing problems legal by the claim and solving them to substantiate the claim.
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 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.
Scholars mutually agree on Claim, 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.
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, problem, solution claim = claim about problems and solutions, together with a refutation protocol
Shapes of claims: mathematical claims E: exists a problem A: for all solutions (EA) A: for all problems E: exists solution (AE) algorithmic claims E: exists an algorithm A: for all inputs