Data compression basics in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the main goal of data compression?

Imagine you have a large box of books and you want to fit them into a smaller box without losing any pages. What is the main goal of data compression in computing?

A To reduce the size of data so it takes up less space or bandwidth

B To make data load slower to save energy

C To change the data into a secret code for security

D To delete parts of data to save space

💡 Hint

Think about how you can fit more books in a smaller box without losing any pages.

Data compression reduces the size of data so it uses less storage or bandwidth, similar to packing books tightly without losing any pages.

❓ trace

intermediate

Trace the output of a simple run-length encoding

Run-length encoding (RLE) compresses data by replacing repeated characters with a count and the character. What is the output of encoding the string AAAABBBCCDAA using RLE?

Intro to Computing

Input: AAAABBBCCDAA
Output: ?

A 4A3B2CDAA

B A4B3C2D1A2

C AAAA3BBB2CC1D2AA

D 4A3B2C1D2A

💡 Hint

Count how many times each character repeats consecutively and write the count before the character.

RLE counts consecutive characters and writes the count followed by the character: 4 A's, 3 B's, 2 C's, 1 D, 2 A's.

❓ identification

advanced

Identify the type of compression from description

Which type of compression uses a dictionary of repeated patterns and replaces repeated data with references to this dictionary?

A Run-length encoding

B Dictionary-based compression

C Lossy compression

D Huffman coding

💡 Hint

Think about a compression method that builds a list of common pieces and reuses them.

Dictionary-based compression stores repeated patterns in a dictionary and replaces repeats with references to save space.

❓ Comparison

advanced

Compare lossless and lossy compression

Which statement correctly compares lossless and lossy compression?

A Both lossless and lossy compression remove data permanently.

B Lossless compression loses some data to reduce size; lossy compression keeps all data intact.

C Lossless compression keeps all original data; lossy compression removes some data to reduce size.

D Lossy compression is slower than lossless compression in all cases.

💡 Hint

Think about whether the original data can be perfectly restored after compression.

Lossless compression keeps all data so it can be perfectly restored; lossy compression removes some data to save more space but loses some quality.

🔍 Analysis

expert

What is the output of this Huffman coding frequency table?

Given the characters and their frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}, what is the length of the Huffman code for character 'f'?

Intro to Computing

Frequencies: a=5, b=9, c=12, d=13, e=16, f=45
Question: Length of Huffman code for 'f'?

A 1

B 3

C 4

D 5

💡 Hint

In Huffman coding, the most frequent character gets the shortest code.

Since 'f' has the highest frequency, it gets the shortest code, which is 1 bit long.

Practice

1. What is the main purpose of data compression?

easy

A. To make files smaller so they use less space

B. To make files larger for better quality

C. To change file formats randomly

D. To delete important parts of a file

Solution

1. Step 1: Understand the goal of compression

   Compression reduces file size by encoding data more efficiently.

2. Step 2: Compare options to the goal

   Only To make files smaller so they use less space correctly states making files smaller to save space.

3. Final Answer:

   To make files smaller so they use less space -> Option A

4. Quick Check:

   Compression = smaller files [OK]

Hint: Compression means smaller files to save space [OK]

Common Mistakes:

• Thinking compression increases file size
• Confusing compression with file format change
• Believing compression deletes data

2. Which of the following is a correct description of lossless compression?

easy

A. It removes some data permanently to reduce size

B. It compresses data without losing any original information

C. It changes file format to a different type

D. It only works on images, not text

Solution

1. Step 1: Define lossless compression

   Lossless compression reduces size but keeps all original data intact.

2. Step 2: Match definitions to options

   It compresses data without losing any original information correctly describes lossless compression as no data loss.

3. Final Answer:

   It compresses data without losing any original information -> Option B

4. Quick Check:

   Lossless = no data lost [OK]

Hint: Lossless means no data is lost during compression [OK]

Common Mistakes:

• Confusing lossless with lossy compression
• Thinking lossless deletes data
• Believing lossless only works on images

3. Consider this simple compression example: The string "AAAABBBCCDAA" is compressed by replacing repeated letters with the letter and count (e.g., A4 for AAAA). What is the compressed form?

medium

A. A4B3C2D1A2

B. 4A3B2C1D2A

C. AAAABBBCCDAA

D. ABCD

Solution

1. Step 1: Identify repeated letters and counts

   "AAAABBBCCDAA" has A repeated 4 times, B 3 times, C 2 times, D 1 time, A 2 times.

2. Step 2: Write compressed form as letter + count

   Following the pattern, compressed string is A4B3C2D1A2.

3. Final Answer:

   A4B3C2D1A2 -> Option A

4. Quick Check:

   Repeated letters + counts = A4B3C2D1A2 [OK]

Hint: Count repeats and write letter then number [OK]

Common Mistakes:

• Writing count before letter
• Not counting single letters
• Leaving string uncompressed

4. A compression program replaces repeated words with a code but forgets to store the code mapping. What problem will occur when decompressing?

medium

A. The program will run faster

B. The file size will increase instead of decrease

C. The original data cannot be restored correctly

D. The compressed file will be empty

Solution

1. Step 1: Understand the role of code mapping

   Code mapping links codes to original data for decompression.

2. Step 2: Identify impact of missing mapping

   Without mapping, decompression cannot restore original data correctly.

3. Final Answer:

   The original data cannot be restored correctly -> Option C

4. Quick Check:

   Missing mapping = wrong decompression [OK]

Hint: Mapping needed to restore original data [OK]

Common Mistakes:

• Thinking file size increases due to missing mapping
• Assuming program runs faster without mapping
• Believing compressed file becomes empty

5. You have a text file with many repeated phrases. Which compression method is best to reduce its size without losing any information?

hard

A. Lossy compression that removes repeated phrases

B. Deleting repeated phrases manually

C. Changing the file format to a different type

D. Lossless compression that replaces repeated phrases with codes

Solution

1. Step 1: Identify need for no data loss

   The question requires no information loss, so lossy methods are unsuitable.

2. Step 2: Choose method that compresses repeated phrases without loss

   Lossless compression replaces repeated phrases with codes, preserving data.

3. Step 3: Eliminate other options

   Changing format or deleting phrases manually does not guarantee compression or data safety.

4. Final Answer:

   Lossless compression that replaces repeated phrases with codes -> Option D

5. Quick Check:

   No data loss + repeated phrases = lossless compression [OK]

Hint: Use lossless for repeated data without losing info [OK]

Common Mistakes:

• Choosing lossy compression when data loss is not allowed
• Thinking changing file format compresses data
• Deleting data manually instead of compressing