This question is somewhat related to a prior question that I asked about an Information Theory lab. I received a lot of great feedback there, but I have not gotten past the idea yet that the lab that I assigned last year was simply too hard. I have been wracking my brain to think of a new lab idea, but so far, I have come up empty-handed.
So you don't have to visit the prior question, here is the relevant portion:
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.
All of the coding done by students during this course is in Scheme, so labs that naturally lend themselves to functional programming paradigms instead of imperative ones are appreciated. My best labs tend to present a series of very short lab assignments, and either present them in escalating order of difficulty, or provide some options to the students about which ones to pursue, to smaller-scale ideas are also a better fit for my class structure.