[go: up one dir, main page]
Scribd
Upload
47 views2 pages

CS301 - Assignment - 02 Done

Uploaded by

Aqib Rajput
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
47 views2 pages

CS301 - Assignment - 02 Done

Uploaded by

Aqib Rajput
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Muhammad Aqib Javed

BC200400686 Total Marks: 20

Lectures Covered:25-26
Assignment No. 02
SEMESTER Spring 2024 Due Date: 24th June,
2024
CS301- Data Structures

Question. No. 1:
Marks: 20

String:
Data Structures is one of the core courses of BS(CS) program.

a. Build frequency table and Huffman encoding tree.


[14 Marks]

Frequency Table
Character Frequency Number of Bits Huffman code of Number of Bits
used without any each character used with
encoding Huffman
encoding
D 1 8 100100 6
a 3 24 0010 12
t 4 32 1000 16
10 80 111 30
S 3 24 0011 12
r 6 48 010 18
u 3 24 11001 15
c 3 24 0110 12
e 5 40 1101 20
s 4 32 1010 16
i 1 8 011100 6
o 6 48 000 18
n 1 8 101111 6
f 2 16 10110 10
h 1 8 101110 6
B 1 8 100111 6
( 1 8 100110 6
C 1 8 011111 6
) 1 8 011110 6
p 1 8 110001 6
g 1 8 110000 6
m 1 8 011101 6
. 1 8 100101 6
Huffman Encoding Tree
The Huffman encoding tree is built by merging nodes with the lowest frequencies until a single
tree is formed.

b. Calculate how many bits will be used for the above string:
[6 Marks]

Without using any encoding technique: 488 bits

With Huffman encoding technique: 251 bits

Percentage of bits saved by Huffman encoding scheme: 48.57%

You might also like