CS502 Fundamentals of Algorithms Assignment No. 04 Solution July 2014

[vuassignments]

CS502 Fundamentals of Algorithms Assignment No. 04 Solution and Discussion Fall 2014 Due Date 24th July 2014



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.





  Untitled.jpg (Size: 16.47 KB / Downloads: 475)

[Entboy]

Lets start Dissension

[vuassignments]

For idea of question number 1: Look at this exmple:

Suppose you have to give Money-Change for the amount of Rs.18 with least possible number of coins/notes. Currently the denominations for Pakistan currency system in Rupees are coins of 1, 2, 5 and paper notes of 10, 20, 50, 100, 500, 1000, and 5000.



You are required to determine whether the Greedy-approach gives optimum value or not in this case by calculating the required number of total coins/bills through both the solution methods.

Using Greedy algorithm


  3.jpg (Size: 87.29 KB / Downloads: 464)

[vuassignments]

Making Change: Dynamic Programming Solution

The general coin change problem can be solved using Dynamic Programming. Set up a Table, C[1..k, 0..N] in which the rows denote available denominations, di; (1 _ i _ k) and columns denote the amount from 0 . . .N units, (0 _ j _ N). C[i, j] denotes the minimum number of coins, required to pay an amount j using only coins of denominations 1 to i. C[k, N] is the solution required.



To pay an amount j units, using coins of denominations 1 to i, we have two choices:



1. either chose NOT to use any coins of denomination i,

2. or chose at least one coin of denomination i, and also pay the amount (j - di).



To pay (j - di) units it takes C[i, j - di] coins. Thus,

C[i, j] = 1 + C[i, j - di]



Since we want to minimize the number of coins used,

C[i, j] = min(C[i - 1, j], 1 + C[i, j - di])



This is the forumulation!