This is mid-year in a course for HS juniors in theoretical computer science. The unit is about Information Theory. We were using the coin-weighing problem as something of a motivator for the entire enterprise, as a deep understanding of that problem would also engender a pretty reasonable understanding of the purpose and use of the four axioms of Information Theory:
- I(p) ≥ 0
- I(1) = 0
- I(p1 * p2) = I(p1) + I(p2)
- I is continuous and monotonic
In the lectures prior to this lab, we cover the coin problem, the axioms themselves, some of the derived properties of the axioms, bits, trits (including the Soviet Setun computers), nats, and Hartleys, how much information is present in random and constrained events, the concept or entropy, and how to calculate the storage requirements of a theoretically maximal lossless data compression given some set of rules.
In covering the coin problem itself, we actually visit it three times, spread out among the lessons above. At first, I simply introduce the problem and have the kids try to solve it for some small numbers of coins. Later, we revisit the coin problem and show how we would solve some larger problems, and draw some generalized conclusions from these solutions. Finally, at our third visit, we derive a generalized algorithm for what steps you could use to figure out a next optimal weighing.
The lab is in Scheme, and asks students to create a function that provides the proper weighings to solve a game. The entire lab write-up comes in at a whopping 8 pages, so I won't put that all here, but this is the opening that describes the problem:
Your goal is to create a function called
playgamethat takes arguments like so:
(define sampleGame '((u . 1) (u . 2) (u . 3) (u . 4) (G . 5)))
(playgame 4 'H sampleGame)
In the game example above, the real answer is that coin 4 is heavy. But coming into the problem, coins 1-4 are unknown, and coin 5 is a reference coin. The data encodings are like so:
'u – unknown, could be light, heavy, or good
'l – could be light or good (heavy has been eliminated as a possibility)
'h – could be heavy or good (light has been eliminated as a possibility)
'L – coin is Light. This is a final answer state.
'H – coin is Heavy. This is a final answer state.
'G – coin is good.
All games with
'Gare considered to be equivalent, so a designation of no false coins can be made with any coin number.
The function call above would have an output like:
Game of ((u . 1) (u . 2) (u . 3) (u . 4) (G . 5))
With real answer that coin 4 is H
Move 0: (((u . 4) (u . 1)) ((G . 5) (u . 2)) ((u . 3)))
result: ((h . 4) (h . 1) (G . 5) (l . 2) (G . 3))
Move 1: (((h . 4)) ((h . 1)) ((G . 5) (l . 2) (G . 3)))
result: ((H . 4) (G . 1) (G . 5) (G . 2) (G . 3))
Game finished in 2 moves
There are many possible ways to get the answer. In your lab, don’t be concerned with whether you are weighing coin 4 vs coin 1 instead of coin 2 versus coin 4. What matters is that every move is legal, and that your weighings will always find the answer within the minimum number of steps.
What follows on that same page is a recap (and explanation) of the algorithm for figuring out the next move that we derived together in class.
The lab itself turned out to be extremely difficult, even when I did it on my own. I don't like to shrink back from course targets. I would prefer to scaffold until every student can meet the goal. So, I had to find a way to make it more manageable. I arrived at the following strategy, which I confess I thought quite innovative at the time:
I created the lab itself in segments, each with more hints, discussion, and code organization. If you ultimately read through the entire lab write-up, you would eventually the method header and description for every one of the 28 functions in my own personal (idiosyncratic) solution, as well as additional hints, thoughts, and alerts to some programming traps.
At the bottom of each section, I had a message like this:
If you stop here and complete the problem correctly, you will be able to earn 100%.
If you go on to the next page, you will only be able to earn 94%.
The notion was to allow for self-selected scaffolding to make the lab more possible. The earnings per section were originally set to 105, 100, 94, and 80. (The big gap for the last section was because the last section basically just laid out every little detail.) This setup, I believed, would provide a challenge to those who could handle it, and support for those who needed.
How things went down
When the lab went live, it did not go at all as I expected. The students at my highly selective school were far, far more resistant to going on to the next section than I had anticipated, and preferred instead to work at a level that was inappropriately hard. Most students refused to go below 100% for any reason whatsoever, and the students who could really have benefited from the 80% section would not go past 94%. Some students never completed the lab at all, ironically garnering a zero in an attempt to avoid a 94%.
More perturbing to me were assertions that there were other students who were cheating, since the sections you actually read were on your own honor. My protestations that my solution was, in fact, highly idiosyncratic (and therefore it would be easy to tell) did nothing to dispel this idea. Later, upon analysis, I did find at least one student who definitely did read beyond the section that he declared, but that was all I was able to find.
This whole episode took a tremendous amount of class time, and ate substantially into the good will I had built over the last two years with the class.
Innovation? Meet near-abject failure.
I have already made a pass at addressing some of the problems the kids identified for this next school year. First of all, I have integrated the coin problem far more tightly into the lecture materials. I have further added new hints and clarifications across the entire text of the lab, and I have changed the point values for the sections to: 105, 100, 96, and 90.
With these modifications, the lab will be incrementally better on a number of fronts. However, I can't help but think that my approach is foundationally wrong here. I don't see how to entirely avoid many of the problems that I encountered the first time.
How can I scaffold the lab more appropriately without retreating on the final product? I believe that the exercise has real value, and I don't want to simply retreat into lab material that is inherently less rich.