Lab ideas for information theory

Question

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:

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.

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.

Answer 1

Image compression, for example sending back photos from far away in space and through narrow communications, is interesting because it gives a visual scene of the work done. You can compress the individual pixels to a range of bit-depths, from 2/4/8... 32 bits, you can compress 2 bits inside 8-bit registers of a PC which often reads and writes memory blocks of 8/16 bits. It's very good to have a thorough understanding of XY color graphs.

The concept of images also leads to the topic of floodfill, and recursive searching of black and white pixels, and recursion generates 100mb or 1gb, which leads to the concepts of stack overflows from disorganized memory. Students therefore learn to keep 2D and 3D arrays for pixels and voxels. If they do 3D arrays to compress data in, they are building a Minecraft world.

Voxels are stacks of XY graphs, on a Z axis, so videos are actually voxels, using XY and Time. Most work done on 2D graphs a lot easier and smaller, and also very similar to 3D graphs.

In a Minecraft world you are introducing the kids to lots of 3D concepts, and the limitations of bandwidth every frame to and from the graphics cards, and overall memory limitations. A voxel engine has to be very optimized to get around those.

I recently used 3D arrays to solve floodfill recursive algorithms so that they take up 100 times less space than line-scanning floodfills and I found it mentally very engaging. A voxel space can take up a billion memory spaces very fast, 1000x1000x1000 points of space, which requires a lot of bandwidth optimizing.

When you have objects in a voxel space, and you find the edge voxels of the shape, you can generate a point cloud, which is useful too. Point clouds use huge amounts of data, and they represent visible shapes. Being able to organize algorithms in point clouds requires a lot of organization, it leads to the concepts of Octrees and nearest neighbor algorithms.