Practice Data Compression in CS Thinking

Use these practice problems to test your method after reviewing the concept explanation and worked examples.

Worksheet PDF Free Answer-key PDF Family

Quick Recap

Data compression is the process of reducing the number of bits needed to store or transmit information. Some compression is lossless, meaning the original data can be recovered exactly, while some is lossy, meaning some detail is discarded to save more space.

Compression is packing information more tightly so files take less space or move faster across a network.

Showing a random 20 of 50 problems.

Example 1

medium
RLE on `AAABBBBCC` produces what string, and is it shorter than the original?

Example 2

medium
RLE encodes `AAAAAAABBBBC` (7 A's, 4 B's, 1 C). Give the encoded form and original/compressed character counts.

Example 3

medium
You must transmit medical X-ray images. Which compression type is appropriate and why?

Example 4

medium
A photo is JPEG-compressed, then that JPEG is re-saved as JPEG several more times. What happens to quality and why?

Example 5

hard
By the pigeonhole principle, no lossless algorithm can compress EVERY nn-bit file to fewer than nn bits. Why?

Example 6

medium
RLE on `ABABAB` produces `1A1B1A1B1A1B`. Why did compression FAIL here?

Example 7

medium
A backup grows from 8080 GB to 200200 GB, but the compressed size only grows from 1616 GB to 2525 GB. Which compression ratio improved, original →\to compressed?

Example 8

hard
A 44K frame raw is 2424 MB. A codec produces 0.30.3 MB per frame at 3030 fps. Compute the compression ratio per frame.

Example 9

hard
Huffman codes for symbols with probabilities {0.4,0.3,0.2,0.1}\{0.4,0.3,0.2,0.1\} have lengths {1,2,3,3}\{1,2,3,3\}. Compute the expected bits per symbol.

Example 10

medium
A 100 MB dataset must transfer over a link in under 10 seconds, and the link does 5 MB/s. What minimum compression ratio is required?

Example 11

easy
A song file is 8 MB and compresses to 2 MB. What is the compression ratio?

Example 12

hard
A 300300 MB video must stream in real time over a 22 MB/s connection for 6060 s of content. What compression ratio minimum is required?

Example 13

easy
If a file does not compress at all (ratio 1:1), what does that suggest about its data?

Example 14

easy
Apply RLE to the string `BBBBBB` (6 B's). Give the compressed form.

Example 15

hard
A 640×480640\times 480 8-bit grayscale image compresses to 3030 KB. Compute the compression ratio (raw bytes ÷\div compressed bytes).

Example 16

medium
A backup is 80 GB raw and compresses at 5:1. What is the compressed size, and how much space is saved?

Example 17

challenge
You receive a 1010 MB file in 44 seconds on a 11 MB/s link. Explain how this is possible.

Example 18

easy
True or false: PNG is a LOSSLESS image format.

Example 19

easy
A file shrinks from 200 KB to 50 KB. What is the compression ratio?

Example 20

easy
Apply RLE to `CCCCDDDD`. What is the output?
← Back to Data Compression Worked Examples Formula Explained