Overview

Compression is a method or protocol for using fewer bits to represent the original information. Compression can be achieved in a variety of methods including looking for patterns and substituting symbols for the larger patterns of data. Compression can be a "hard problem" for computers because it is difficult to know whether or not the compression you've found is optimal - if you keep trying would it get better? It's hard to know when to stop, and hard to verify that you've compressed it "enough". When it's impossible, or would take an unreasonable amount of time, to know an exact solution you can create a strategy called a "heuristic" to define some rules about when the solution is good enough. See the vocabulary section below.

Vocabulary

Goals

Students will be able to:

Purpose

This is a big lesson that covers a lot of bases. First and foremost it covers the following topics directly from the CSP framework:

Resources

Getting Started

Before beginning the lesson activities, briefly talk with students about compression -- how they might use it normally in their own discourse, what it does, and why it's important in computing.

Let's look at an example of a text message that's been compressed in a clever way.

Activity 1

Provide students with the Decode This Message - Activity Guide.

Either individually or with partners, let students decode the message using the key in the activity guide.

How much was it compressed?

To answer, we need to compare the number of characters in the original poem to the number of characters needed to represent the compressed version.

Display or demonstrate the ideas from the Decode This Message - Activity Recap (Teacher's Guide)

Important Note: The compressed poem is not just this part. If you were to send this to someone over the Internet they would not be able to decode it. The full compressed text includes BOTH the compressed text and the key to solve it. Thus, you must account for the total number of characters in the message plus the total number of characters in the key to see how much you've compressed it over the original.

Now you are going to try your hand at compressing things on your own.

Activity 2

First, watch the following video about Text Compression.

Rather than using Code.org's Text Compression Widget as described in the video, we will use a Quorum program instead. The program is fully finished - it doesn't need any modifications, and can be run as-is. The widget can be accessed by the "Lossless Text Compression Widget" resource.

Heuristics

In computer science there is a word for strategies to use when you're not sure what the exact or best solution to a problem is. A HEURISTIC is a problem solving approach (typically an algorithm) to find a satisfactory solution where finding an optimal or exact solution is impractical or impossible.

Wrap Up

Compression in the Real World (.zip)

Assessment

Extended Learning

Computer Science Principles Curriculum