Design and Analysis of Algorithms

Chapter $10--$ the Greedy Method

$10\mathrm{.}5\mathrm{.}1$

Let be a collection of objects with benefit$-$weight values, $.$ What is an optimal solution to the fractional knapsack problem for assuming we have a sack that can hold objects with total weight $18?$ Show your work.

$10\mathrm{.}5\mathrm{.}3$

Suppose we are given a set of tasks specified by pairs of the start times and finish times as$.$ Solve the task scheduling problem for this set of tasks.

$10\mathrm{.}5\mathrm{.}4$

Draw the frequency table and Huffman tree for the following string:

$$; dogs do not spot hot pots or cats$$

$10\mathrm{.}5\mathrm{.}15$

Describe an efficient greedy algorithm for making change for a specified value using a minimum number of coins, assuming there are four denominations of coins $($called quarters, dimes, nickels, and pennies$),$ with values $25,10,5,$ and $1,$ respectively. Argue why your algorithm is correct. You must explain your answer, why they work or why not.

$10\mathrm{.}5\mathrm{.}16$

Give an example set of denominations of coins so that a greedy change making algorithm will not use the minimum number of coins. You must explain your answer, why they work or why not.

Rumor spreading $-$ There are $n$ people, each in possession of a different rumor. They want to share all the rumors with each other by sending electronic messages. Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee. Design a greedy algorithm that always yields the minimum number of messages they need to send to guarantee that everyone of them gets all the rumors.