6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Possibly helpful to users thinking of making suggestions, or to yourself to generate ideas; what specific concept should the lab demonstrate, or expose? information theory is pretty big for a lab, or three. $\endgroup$ – Gypsy Spellweaver Jul 29 '17 at 15:39
  • $\begingroup$ @GypsySpellweaver Any of the concepts listed above. Should those each be separate questions? It felt like the topics would get so miniscule as to become useless for others. $\endgroup$ – Ben I. Jul 29 '17 at 19:46
  • $\begingroup$ @nocomprende I guess your answer has taught me that I have more to learn about information theory! $\endgroup$ – Ben I. Aug 23 '17 at 0:00
3
$\begingroup$

Image compression, for example sending back photos from faraway in space and through narrow communications, is interesting because it gives 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 alot 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 floodfils and I found it mentally very engageing. 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 algorythms.

$\endgroup$
  • $\begingroup$ Welcome to CSEducators. I think that was a great answer. Come back often. $\endgroup$ – Buffy Jan 25 '18 at 16:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.