Huffman Encoding in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a priority queue for Huffman nodes.

DSA C#

var priorityQueue = new PriorityQueue<HuffmanNode, int>();
priorityQueue.Enqueue(new HuffmanNode('a', 5), [1]);

Drag options to blanks, or click blank then click option'

A1

B5

C'a'

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character as priority instead of frequency.

Using a fixed number like 0 or 1 instead of the frequency.

The priority queue uses the frequency as the priority, so we enqueue with the frequency value 5.

2fill in blank

medium

Complete the code to merge two Huffman nodes by summing their frequencies.

DSA C#

int mergedFreq = node1.Frequency [1] node2.Frequency;

Drag options to blanks, or click blank then click option'

A-

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Dividing frequencies which is incorrect.

To merge two nodes, we add their frequencies to get the combined frequency.

3fill in blank

hard

Fix the error in the code that builds the Huffman tree by dequeuing two nodes.

DSA C#

var left = priorityQueue.[1]();
var right = priorityQueue.Dequeue();

Drag options to blanks, or click blank then click option'

ADequeue

BRemove

CPop

DExtract

Attempts:

3 left

💡 Hint

Common Mistakes

Using Pop which is for stacks.

Using Remove or Extract which are not valid methods here.

The correct method to remove and return the element with the highest priority is Dequeue.

4fill in blank

hard

Fill both blanks to correctly assign left and right children when creating a new Huffman node.

DSA C#

var mergedNode = new HuffmanNode(null, mergedFreq)
{
    Left = [1],
    Right = [2]
};

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cnode1

Dnode2

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right nodes.

Assigning null or wrong variables.

The merged node's left child is the left node dequeued, and the right child is the right node dequeued.

5fill in blank

hard

Fill all three blanks to build a dictionary comprehension that maps characters to their Huffman codes.

DSA C#

var huffmanCodes = nodes.ToDictionary(n => n.[1], n => n.[2].[3]());

Drag options to blanks, or click blank then click option'

ACharacter

BCode

CToString

DFrequency

Attempts:

3 left

💡 Hint

Common Mistakes

Using Frequency as key instead of Character.

Not converting code to string.

We map each node's Character to its Code converted to string using ToString().

Practice

1. What is the main purpose of Huffman Encoding in data compression?

easy

A. To assign shorter codes to more frequent characters

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding compresses data by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this purpose; others describe different concepts.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option A

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes in Huffman [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing compression with encryption
• Assuming sorting is the main goal

2. Which of the following C# code snippets correctly declares a priority queue for Huffman nodes using .NET 6+ syntax?

easy

A. var pq = new PriorityQueue();

B. PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

C. var pq = new PriorityQueue<HuffmanNode>();

D. PriorityQueue pq = new PriorityQueue();

Solution

1. Step 1: Recall .NET 6+ PriorityQueue syntax

   The correct syntax requires two generic types: the element and its priority, e.g., PriorityQueue.

2. Step 2: Check each option

   var pq = new PriorityQueue(); uses correct syntax with element type HuffmanNode and priority int. Others have syntax errors or missing types.

3. Final Answer:

   var pq = new PriorityQueue<HuffmanNode, int>(); -> Option A

4. Quick Check:

   PriorityQueue<TElement, TPriority> = var pq = new PriorityQueue(); [OK]

Hint: PriorityQueue needs element and priority types in angle brackets [OK]

Common Mistakes:

• Omitting priority type in PriorityQueue declaration
• Using empty angle brackets <> without types
• Declaring without var or explicit type

3. Given the following frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for character 'a' after building the tree?

medium

A. 110

B. 1100

C. 111

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5(a) and 9(b) -> 14; then 12(c) and 13(d) -> 25; finally 14 and 25 -> 39 root.

2. Step 2: Assign codes from root

   Left branch is '0', right is '1'. 'a' is in left subtree of 14, which is left subtree of root, so code is '1100'.

3. Final Answer:

   1100 -> Option B

4. Quick Check:

   Lowest freq 'a' gets longest code '1100' [OK]

Hint: Lowest freq chars get longer codes in Huffman [OK]

Common Mistakes:

• Assigning shorter codes to lowest frequency chars
• Mixing left/right branch codes
• Not building tree step-by-step

4. Identify the error in this C# snippet for building a Huffman tree:

var pq = new PriorityQueue<HuffmanNode, int>();
pq.Enqueue(new HuffmanNode('a', 5), 5);
pq.Enqueue(new HuffmanNode('b', 9), 9);
var left = pq.Dequeue();
var right = pq.Dequeue();
var parent = new HuffmanNode(null, left.freq + right.freq);
pq.Enqueue(parent, parent.freq);

medium

A. PriorityQueue requires priority as first argument in Enqueue

B. Dequeue returns a tuple, not a HuffmanNode

C. Cannot use null for character in HuffmanNode

D. HuffmanNode constructor missing frequency parameter

Solution

1. Step 1: Recall PriorityQueue Dequeue return type

   In .NET PriorityQueue, Dequeue() returns the element (HuffmanNode) directly, not a tuple.

2. Step 2: Verify other code parts

   Enqueue(element, priority) order is correct. left.freq and right.freq access is valid assuming public freq property. Constructor called with two arguments consistently.

3. Step 3: Identify the error

   Cannot use null for character in HuffmanNode is correct: new HuffmanNode(null, ...) fails because the constructor expects a non-nullable char (inferred from leaf nodes like new HuffmanNode('a', 5)), and null cannot be assigned to char. Use char? for character field or '\0' for internal nodes.

4. Final Answer:

   Cannot use null for character in HuffmanNode -> Option C

5. Quick Check:

   char cannot be null; use char? for internal nodes [OK]

Hint: Cannot assign null to char; use char? for internal nodes [OK]

Common Mistakes:

• Assuming Dequeue returns tuple with priority
• Thinking Enqueue argument order is reversed
• Thinking null can be passed to non-nullable char constructor

5. You have characters with frequencies: {'x': 1, 'y': 1, 'z': 1, 'w': 1}. After building the Huffman tree, what is the minimum and maximum length of the Huffman codes assigned to these characters?

hard

A. Minimum length = 2, Maximum length = 3

B. Minimum length = 1, Maximum length = 3

C. Minimum length = 1, Maximum length = 2

D. Minimum length = 2, Maximum length = 2

Solution

1. Step 1: Build Huffman tree for equal frequencies

   All freq=1. Dequeue two leaves (1+1=2), now pq has two leaves(1) and one internal(2). Dequeue two leaves (1+1=2), now two internals(2+2=4 root). Perfectly balanced tree.

2. Step 2: Determine code lengths

   All four leaves at depth 2, so all codes length 2: min=2, max=2.

3. Final Answer:

   Minimum length = 2, Maximum length = 2 -> Option D

4. Quick Check:

   4 equal freq chars: balanced tree, all codes length 2 [OK]

Hint: Equal freq chars yield balanced tree, equal code lengths [OK]

Common Mistakes:

• Thinking tree unbalanced, max length=3
• Thinking minimum code length=1 for 4 chars
• Ignoring that equal freq forces balance