Glendale Community College Not Huffman Coding – Description
Overview: Recall that a code (in the context of prefix codes, Huffman codes, ascii) is just an assignment of
a bit string to every letter/character. A Huffman Code guarantees that any message can only be decoded
in one way by requiring that the bit string assigned to any letter cannot be a prefix of the bit string
assigned to any other letter. If this requirement is discarded it may be possible to have a message that
can be decoded in multiple ways.
For example, using the code from the table, the message 11101110000001011101011 can be decoded
many different ways. Two of the ways are indicated below. (SEE ATTACHED PHOTOS)
Details: You program will be provided with a file called input.txt which consists of one line that tells you
the number of letters in the code N and then N lines each with a letter and its code and finally a message
on the last line.
You will use dynamic programming to determine the number of ways that the message can be decoded
and print out this number. As with all dynamic programming algorithms, you’ll want to determine a way
to solve the problem using recursion (the base case and how the solution to a larger case depends on
smaller cases) and then program it NOT using recursive calls, but instead an array that can store the
answers to the cases and fill that array from small to large. My hint would be that you might want an
array called CFLB (count for last bits) where CFLB[i] ≡ the number of ways the last i bits in the message
can be decoded.
MUST USE DYNAMIC PROGRAMMING. NO packages Allowed.
has to pass all cases.
Examples:
Case 1: input.txt contains:
4
a 00
b 01
c 10
d 11
01110000
then the output would be
1
Case 2: If input.txt contains:
12
a 00
b 01
c 10
d 11
e 000
f 001
g 010
h 011
i 100
j 101
k 110
l 111
100101100011
then the output would be:
12
Case 3: If input.txt contains:
11
a 11
d 11101
g 0111010
h 110
i 11000
j 111
n 00
o 01
r 011
s 0
u 101
11101110000001011101011
then the output would be
753
Case 4 : If input.txt contains:
14
a 00
b 01
c 1001
d 0101
e 11001
f 0111
g 1001
h 11011
i 00111
j 100
k 01100110
l 101
m 11
n 1100
000110010101110010111100111011001111000110011010111110000111010101111001
the the output would be
12096
If your program takes more than second on this last example then it is extremely likely
that you are not using dynamic programming.
The post Glendale Community College Not Huffman Coding first appeared on .
