Quiz 4
CS F364: Design & Analysis of Algorithms
Quiz 4 — June 11, 2026
Coverage: Lectures 1–14
Instructions:
- Time: 15 minutes.
- Write your answers clearly on paper, scan, and upload to Google Classroom.
- Show all steps for full credit.
Question: Huffman Coding
A file contains characters with the following frequencies:
| Character | A | B | C | D | E |
|---|---|---|---|---|---|
| Frequency | 10 | 15 | 30 | 5 | 40 |
We want to design an optimal prefix code for these characters using Huffman’s greedy algorithm.
(a) [3 marks] Construct the optimal Huffman tree. Draw the final tree, showing the character and frequency at each leaf node, and the sum of frequencies at each internal node. Show the key intermediate steps of tree construction.
(b) [1 mark] Write the resulting binary code for each character. Assume that left branches are labeled with 0 and right branches are labeled with 1 (or vice versa, specify which convention you used).
(c) [1 mark] Compute the expected (average) number of bits per character under this Huffman code. How does it compare to the number of bits required per character using a standard fixed-length binary code for 5 characters? (State the percentage of space saved).