Q3Design and Analysis of Algorithms

Huffman Coding is a lossless data compression algorithm devised by David Huffman in 1952. It assigns variable-length binary codes to characters based on their frequencies — more frequent characters get shorter codes. It produces an optimal prefix-free code (no codeword is a prefix of another), ensuring unambiguous decoding.

• Create a leaf node for each character and add it to a min-priority queue (keyed by frequency).
• While the queue has more than one node:
• Extract the two nodes with minimum frequency (x and y).
• Create a new internal node z with frequency = freq(x) + freq(y).
• Set x and y as left and right children of z.
• Insert z back into the priority queue.
• The remaining node is the root of the Huffman tree.
• Traverse the tree: left = 0, right = 1 to assign codes.

Characters and frequencies: A=5, B=9, C=12, D=13, E=16, F=45.

• Initial queue: A(5), B(9), C(12), D(13), E(16), F(45).
• Step 1: Extract A(5) and B(9). Create Z1(14). Queue: C(12), D(13), Z1(14), E(16), F(45).
• Step 2: Extract C(12) and D(13). Create Z2(25). Queue: Z1(14), E(16), Z2(25), F(45).
• Step 3: Extract Z1(14) and E(16). Create Z3(30). Queue: Z2(25), Z3(30), F(45).
• Step 4: Extract Z2(25) and Z3(30). Create Z4(55). Queue: F(45), Z4(55).
• Step 5: Extract F(45) and Z4(55). Create root(100).

• F: 0 (1 bit)
• C: 100 (3 bits)
• D: 101 (3 bits)
• A: 1100 (4 bits)
• B: 1101 (4 bits)
• E: 111 (3 bits)

Total encoded bits = 5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1 = 20 + 36 + 36 + 39 + 48 + 45 = 224 bits. Fixed-length encoding would require ⌈log₂6⌉ = 3 bits per character × 100 = 300 bits. Huffman saves (300-224)/300 ≈ 25.3% space. Time Complexity: O(n log n). Huffman coding is used in JPEG, MP3, ZIP compression formats.