# CS502 Fundamentals of Algorithms Assignment 4 Solution Spring 2014

To solve Counting money problem through Dynamic Programing as well as Greedy algorithm approaches and to develop Huffman binary tree and codes from the given frequency table.

Q.No.1

Let us suppose you have to give Money change for Rs.23 in Pakistani currency in minimum possible coins/currency notes. The denominations in the form of coins are 1, 2, 5 and currency notes of 10, 20, 50, 100, 500, 1000, and 5000.

You are required to solve this question by both Dynamic Programming as well as Greedy approach and find optimum value by calculating the required number of total coins/notes.

Solution:

The Greedy approach:

given rupees to get changed: 23

20-20=3

3-2=1

1-1=0

1 Note of 20 upees

1 coin of 2 rupees

1 coin of 1 rupee

20=2=1=23

and Total coins/note required: 3

Q.No.2

Compute Huffman encoding for the following frequencies of the characters. Apply the greedy strategy and your goal is to draw the binary tree to produce Huffman Codes for the given frequencies.

Character Frequency

 Character Frequency a 250 b 150 c 300 e 155 f 230 g 105 h 60 i 150 j 60 m 125 n 80 o 65 p 100 r 120 s 430 t 300

Solution:

Building a Huffman Tree

The easiest way to see how this algorithm works is to work through an example. Let’s assume that after scanning a file we find the following character frequencies:

Character           Frequency

‘a’                        12

‘b’                        2

‘c’                        7

‘d’                        13

‘e’                        14

‘f’                         85

Now, create a binary tree for each character that also stores the frequency with which it occurs.

The algorithm is as follows: Find the two binary trees in the list that store minimum frequencies at their nodes. Connect these two nodes at a newly created common node that will store NO character but will store the sum of the frequencies of all the nodes connected below it. So our picture looks like follows:

9                 12 ‘a’         13 ‘d’         14 ‘e’                   85 ‘f’

/    \

2 ‘b’  7 ‘c’

Now, repeat this process until only one tree is left:

21

/    \

9     12 ‘a’    13 ‘d’         14 ‘e’                   85 ‘f’

/    \

2 ‘b’  7 ‘c’

21                     27

/    \                  /      \

9     12 ‘a’    13 ‘d’    14 ‘e’               85 ‘f’

/    \

2 ‘b’  7 ‘c’

48

/               \

21                     27

/    \                  /      \

9     12 ‘a’    13 ‘d’    14 ‘e’               85 ‘f’

/    \

2 ‘b’  7 ‘c’

133

/       \

48                   85 ‘f’

/               \

21                     27

/    \                  /      \

9     12 ‘a’    13 ‘d’    14 ‘e’

/    \

2 ‘b’  7 ‘c’

Once the tree is built, each leaf node corresponds to a letter with a code. To determine the code for a particular node, walk a standard search path from the root to the leaf node in question. For each step to the left, append a 0 to the code and for each step right append a 1. Thus for the tree above we get the following codes:

Letter                  Code

‘a’                        001

‘b’                        0000

‘c’                        0001

‘d’                        010

‘e’                        011

‘f’                         1