Review of Information Theory Lab

Question

Background

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:

1. I(p) ≥ 0
2. I(1) = 0
3. I(p1 * p2) = I(p1) + I(p2)
4. 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

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 playgame that 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 'G are 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.

The Request

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.

Answer 1

I love the idea that you've created a lab using a classic logic puzzle. If you don't already, it might also be beneficial if you could give a real-world problem that the same logic, or concept, has been, or could be, used to solve.

I've got a few ideas about changing how the lab, and its grading, breaks down.

First off, it just feels wrong to have the reduction in potential points for advancing through the "hints" and is even more questionable knowing that it's on the honor system to self-report how far the student went into the hints.

I'm thinking it's better to develop a rubric for grading the final project. Possibly disseminate it, or its basics, with the initial introduction of the lab project. Build into that the appropriate penalties and bonuses based on what you want them to learn, and how that fits into the total course objectives. Completing the project successfully, including all of the target objectives, should be a full-credit project. Penalties ought to be levied for failure to meet stated goals, or demonstrate targeted proficiencies. Bonuses, of course, a assessed for above and beyond work. As a compensation for the loss of good will from the prior experiment, the more transparent, and objective, the rubric is, the better off you will be.

For the scaffolding of the project points, a possibility is to do a timed-release of the "hint" sections, with an advanced notice of when the next section will be released, and what it will pertain to. Those students who think they have solved the issue addressed in the pending section release can "lock-in" their solution by submitting their current work on that issue before the release. When the final project is in, you can compare what they "locked-in" with what they finally submitted, and determine if they adjusted their work to fit the released hint, or merely to correct flaws they would have found without the hint. Thereby, cheating, and self-reporting, are circumvented, and you can award bonuses in the final review for having successfully utilized their original solution (but no penalties for switching to the hint version). Each section release can have its own, unique, bonus weighted to its importance to course/project objectives and/or level of advancement from the course baseline. Overall, I think it's probably best to keep such bonuses relatively small, allowing for a total project value to be 110/100 points. The benefits of the bonus points, hopefully, will only be to compensate for points lost to other criteria in the rubric.

One point I'm unclear on is the timing or the project relative to the entire term for the course, and if it's able to be adjusted. What I'm thinking here, is that the project specs, rubric, and other details can be released fairly early in the term, and the students can have the project as a continual "go to" when they are ahead of the curve on other minor assignments. As the term progresses, you can present concepts that are important to the course objectives, and relate the same concepts to the ongoing project. This will allow them to learn and practice the concepts in your normal flow. Then repeat that learning on their version of the project. The timed release of "hints" and sections could then be set for a few days, or a week, after the pertinent concept is covered in the curriculum. Time enough for them to, possibly, find their own solution, yet not so long as to delay the full project to the point of becoming unsolvable in the remaining time.

As an additional point, the last section you released, with the essentially complete solution, no matter how idiosyncratic, should probably not happen. If, for whatever reason, the student cannot complete the project successfully, they simply will not get the points for the project. If the breakdown of the solution is such that you can award, per the rubric, points-per-section, then an incomplete project need not become a complete loss. They can earn points for the sections, or methods, they did successfully implement. Giving wrong answers on a test, or only completing a portion of a timed test, will not earn full marks. Neither should a project that the student is unable to complete.

As a parting thought, the reluctance to proceed beyond the 100% section probably should have been anticipated. Your student body is not going to respond in a typical fashion, just because they are a select group. They don't dare risk loosing their status as a member of that select group by achieving sub optimal marks. In addition, the perception of students in that age range is that going into the field as developers is a "high stakes" realm. Shades of Facebook and Twitter here. Anything, such as low marks, that could threaten that future potential, either as an active developer or select university admissions, is to be avoided like the plague. Since they cannot conceive of failure as a possibility, they don't see the loss of 6 points as insurance against failure, but as an admission of inferiority, or unsuitability for becoming a developer. (You don't need insurance against something that cannot happen, such as a zombie apocalypse. For them, failure seems impossible, so no insurance is necessary.)

Answer 2

I would maybe flip the order in which students approach the problem -- rather then going from harder to easier, start from easier to harder. That is, start by having your students solve a simpler version of the problem for partial points, then guide them steadily towards a more and more generalized solution until they have a finished product.

This would probably be easier for them to grasp, for starters, since it mirrors how the material itself was presented.

Going from simple to complex would also align incentives correctly -- currently, your assignment is set up such that students get the impression that they are in effect punished for admitting they don't understand and need extra assistance. Naturally then, they're going to want to avoid that hit, either by refusing to read ahead, or by cheating.

In this particular case, I would also take the allegations of cheating seriously. If your students are intelligent, it would be pretty easy for them to read ahead, take the gist of your solution, and re-write it in their own style to avoid accusations of plagiarism. It costs them very little to do so (even if they don't carefully follow your hints, just skimming them would be useful), and there's relatively low risk they'll be caught.

Of course, there's the honor code, but not all students will follow it (and the students who do will feel punished for being honest) -- IMO it's better to just set the assignment up so cheating is difficult to begin with.

In any case, a few more ideas for lowering the difficulty curve without compromising on material:

• Split the assignment part and make it a multi-part assignment. Have students complete the relevant portions after the corresponding lecture. This gives them more time to think through the problem, and should help lower the overall difficulty curve while still covering the same material.
• Make this a partner project -- this sounds like the sort of project where brainstorming and collaborating with others can be very helpful to begin with, so it might perhaps be worth just embracing it.
• Re-write the assignment so students are completing it in a language they're already familiar with. I'm uncertain if this is your student's first real exposure to Scheme (and functional-style languages in general), but if it is, consider moving back to a language they're comfortable with to remove some of the incidental difficulty.