Fundamentals of Algorithms CS502-Fall 2009 Assignment No. 05 Due date: 21st of J
ID: 3616175 • Letter: F
Question
Fundamentals of Algorithms
CS502-Fall 2009
Assignment No. 05
Due date: 21st of January,2010
Total Marks: 20
Question No.1
Coin Change Problem:
Suppose we have a currency having following coins,
1. 1 cent
2. 5 cent
3. 10 cent
You have to find the solution of coin change problem usingdynamic programming for
amount 15. [Your solution should include minimum number ofcoins].
Hint: Your Table will have coins (denominations) as rows and values from 1 to 15 as columns. This
problem is similar to knapsack problemwith the difference that here value is count ofcoins and we will
select minimum coins count, you can see further details inhandouts and video lecture.
Question No.2
Huffman Encoding:
a. Suppose our text include only characters a, b, c, d ande and you have to encode the following string,
“abbbacccceedddecac”
Encode this string using Huffman Encoding and showing all steps includingfinding probability of each character, making Huffman Encoding Treeand finding codes for each character. Also show thepercentage compression achieved usingHuffman Encoding for this string if original string was stored in the form ofASCII characters (8 bits for each character).
b. What is Prefix property and why Prefix property alwaysholds when we apply
Huffman encoding, justify your answer.
Explanation / Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
1
2
3
4
1
2
3
4
5
2
3
4
5
6
3
10
1
2
3
4
1
2
3
4
5
1
2
3
4
5
2
Only two coins are required for 15.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
1
2
3
4
1
2
3
4
5
2
3
4
5
6
3
10
1
2
3
4
1
2
3
4
5
1
2
3
4
5
2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.