To solve Counting money problem through Dynamic Programming 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.
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 |
Idea solution :
Consider the currency in U.S.A. There are paper notes for one dollar, five dollars, ten dollars, twenty
dollars, fifty dollars and hundred dollars. The notes are also called “bills”. The coins are one cent, five
cents (called a “nickle”), ten cents (called a “dime”) and twenty five cents (a “quarter”). In Pakistan, the
currency notes are five rupees, ten rupees, fifty rupees, hundred rupees, five hundred rupees and thousand
rupees. The coins are one rupee and two rupees. Suppose you are asked to give change of $6.39 (six
dollars and thirty nine cents), you can choose:
• a $5 note
• a $1 note to make $6
• a 25 cents coin (quarter), to make $6.25
• a 10 cents coin (dime), to make $6.35
• four 1 cents coins, to make $6.39
Notice how we started with the highest note, $5, before moving to the next lower denomination.
dollars, fifty dollars and hundred dollars. The notes are also called “bills”. The coins are one cent, five
cents (called a “nickle”), ten cents (called a “dime”) and twenty five cents (a “quarter”). In Pakistan, the
currency notes are five rupees, ten rupees, fifty rupees, hundred rupees, five hundred rupees and thousand
rupees. The coins are one rupee and two rupees. Suppose you are asked to give change of $6.39 (six
dollars and thirty nine cents), you can choose:
• a $5 note
• a $1 note to make $6
• a 25 cents coin (quarter), to make $6.25
• a 10 cents coin (dime), to make $6.35
• four 1 cents coins, to make $6.39
Notice how we started with the highest note, $5, before moving to the next lower denomination.
