BC190202814
Ibrahim Khalid
CS502 Assignment Solution
Question No. 1
Marks: 20
Problem Statement: Suppose you are working on a project that involves compressing a large
amount of text data. You have decided to use Huffman encoding to achieve this compression.
Given the string:
HuffmanEncodingTree
Part 1: Calculate the total required number of bits for the ASCII code representation of
the above given string without compression of text?
The string "HuffmanEncodingTree" consists of 18 characters.
Total bits required for ASCII representation: 18 characters×8 bits/character=144 bits18 \
text{ characters} \times 8 \text{ bits/character} = 144 \
text{ bits}18 characters×8 bits/character=144 bits
Answer: 144 bits
Part 2: Calculate the frequencies of each character of the given string in a tabular form.
Character Frequency
H 1
u 1
f 2
m 1
a 1
n 3
E 1
c 1
o 1
d 1
i 1
n 1
g 1
T 1
r 1
BC190202814
Ibrahim Khalid
CS502 Assignment Solution
Character Frequency
e 3
Answer:
H: 1, u: 1, f: 2, m: 1, a: 1, n: 3, E: 1, c: 1, o: 1, d: 1, i: 1, g: 1, T: 1,
r: 1, e: 3
Part 3: Calculate the total required number of bits for the variable-length code
representation of the above given string from the frequency table?
To calculate the total bits for Huffman encoding, we need to build the Huffman tree and
calculate the bit length for each character based on their frequency and position in the tree.
Answer: To be calculated after Part 4.
Part 4: Construct a Huffman encoding tree based on the character frequencies.
The Huffman encoding tree construction involves the following steps:
1. Create initial nodes for each character with their respective frequencies.
2. Build a priority queue (min-heap) based on frequencies.
3. Merge nodes (lowest frequency first) until only one node remains, which becomes the
root of the Huffman tree.
4. Assign codes (0 for left, 1 for right) based on traversal from the root to each leaf.
Answer: To be constructed and detailed.
