COSC 5313 Analysis of Algorithms

Assignment 9

Due: 23:59:00pm, 11/09/2020 (Monday)

1. (30 points) Please use a greedy algorithm to solve the following change problem. Is your solution optimal?

To make $19.99 use the fewest US bills and coins.

2. (40 points) Consider the 8*8 image below, please create the Huffman code tree and show the Huffman

code for each value. Please compute the compression ratio assuming that each value needs 3 bits using

fixed-length code before Huffman compression. Please show detailed steps for full credits.

(Hint: calculate the frequency for each number in the image, and then apply Huffman coding)

3. (30 points) A good way to pick pivot for QUICKSORT is ‘Median of three elements’. Assume an input

array has n elements with indexes from 1 to n. PARTITION function uses the median of the following

THREE elements as the pivot: the first element, the last element, and the element with index

floor((1+n)/2). (floor(A) function returns the greatest integer that is less than or equal to A)

Please sort the array below using QUICKSORT with the pivots found by ‘Median of three elements’

(Please show all iterations to get the final sorted array).

[65 28 75 60 32 45 90 95]