Solution
Assignment 1
Consider the making change problem in the country of India using Greedy algorithm. The input
to this problem is an integer M. The output should be the minimum number of coins to make M
rupees of change. In India, assume the available coins are 1,5,10,20,25,50 rupees. Assume that
we have an unlimited number of coins of each type
a. M = 234
b. Do you think Greedy Algorithm will produce the optimal solution for this problem?
Check output of Greedy Algorithm with M = 40.
Answer:
Greedy Algorithm for M = 234:
Start with the largest coin (50 rupees).
Take as many 50 rupee coins as possible.
o 4 coins of 50 rupees.
o Remaining amount: 234−4×50=34
Next, take as many 25 rupee coins as possible.
o 1 coin of 25 rupees.
o Remaining amount: 34−1×25=9
Next, take as many 5 rupee coins as possible.
o 1 coin of 5 rupees.
o Remaining amount: 9−1×5=4
Finally, take as many 1 rupee coins as possible.
o 4 coins of 1 rupee.
o Remaining amount: 4−4×1=0
Coins Used:
4 coins of 50 rupees
1 coin of 25 rupees
1 coin of 5 rupees
4 coins of 1 rupee
Total Number of Coins:
Total = 4 + 1 + 1 + 4 = 10 coins
Greedy Algorithm for M = 40
We can compare the Greedy solution with the optimal solution:
Greedy solution used 3 coins (1 of 25, 1 of 10, and 1 of 5).
The optimal solution for M = 40 is:
o 2 coins of 20 rupees (total value = 40).
o Total = 2 coins, which is fewer than the greedy solution.
Thus, the Greedy Algorithm does not produce the optimal solution for M = 40
Assignment 2
Given an array F with size n. Assume the array content F[i] indicates the length of the ith file and
we want to merge all these files into one single file. Check whether the following algorithm
gives the best solution for this problem or not?
Algorithm: Merge the files contiguously. That means select the first two files and merge them.
Then select the output of the previous merge and merge with the third file, and keep going...
Note: Given two files A and B with sizes m and n, the complexity of merging is O(m + n).
Answer:
This algorithm will not produce the optimal solution. For a counter example, let us consider the
following file sizes array.
F = {10,5,100,50,20,15}
As per the above algorithm, we need to merge the first two files (10 and 5 size files), and as a
result we get the following list of files. In the list below, 15 indicates the cost of merging two
files with sizes 10 and 5.
{15,100,50,20,15}
Similarly, merging 15 with the next file 100 produces: {115,50,20,15}. After the subsequent
steps, final file is
{200}
And the total cost of merging = Cost of all merging operations = 15 + 115 + 165 + 185 + 200 =
680.
To see whether the above result is optimal or not, consider the order: {5,10,15,20,50,100}. For
this example, following the same approach, the total cost of merging = 15 + 30 + 50 + 100 + 200
= 395. So, the given algorithm is not giving the best (optimal) solution.
Assignment 3
We are given two sorted lists of size n and m. Give an algorithm for finding the median element
in the union of the two lists.
a. The given algorithm has running time O(n+m)
b. The given algorithm has a better running time compared with algorithm of question a
Example 1:
a[] = {-5, 3, 6, 12, 15}, b[] = {-12, -10, -6, -3, 4, 10}
combined list of a and b = {-12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15}.
Median element of combined list is 3
Example 2:
a[] = {2, 3, 5, 8}, b[] = {10, 12, 14, 16, 18, 20}
combined list of a and b= {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
If the number of the elements are even. So there are two middle elements.
Take the average between the two: (10 + 12) / 2 = 11.
Answer:
a. The O(n + m) algorithm can be implemented by simply merging the two sorted lists, similar
to the merge step of the Merge Sort algorithm. After merging, we can find the median
b. A more efficient solution is based on binary search and has a better time complexity of
O(log(min(n, m))). This algorithm avoids merging the lists entirely and directly computes the
median by comparing elements using binary search.
Check this link for more information and real code: Median of two Sorted Arrays of Different Sizes |
GeeksforGeeks
