Homework
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.
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).
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.
