Design and Analysis of Algorithm
(Write pseudo code wherever necessary)
Small Decision Tree:
- Show that every comparison based (i.e., decision tree) algorithm that sorts 5 elements, makes at least 7 comparisons in the worst-case.
- Give a comparison based (i.e., decision tree) algorithm that sorts 5 elements using at most 7 comparisons in the worst case.
Lower Bound on BST construction:
- Given a Binary Search Tree (BST) holding n keys, give an efficient algorithm to print those keys in sorted order. What is the running time of the algorithm?
- Within the decision tree model derive a lower bound on the BST construction problem, i.e., given a set of n keys in no particular order, construct a BST that holds those n keys.
Coin Change Making:
For each of the following coin denomination systems either argue that the greedy algorithm always yields an optimum solution for any given amount, or give a counter-example:
- Coins c0, c1, c2 , …, cn-1 , where c is an integer > 1.
- Coins 1, 7, 13, 19, 61.
- Coins 1, 7, 14, 20, 61.
(Question 4 on the next page)
Question 4)Ball and Boxes:
We have n balls, each with weight at most 1. More specifically, the input is an array ofth
weights W [1. . n], where W[ i ] is the weight of the i ball, 0 ≤ W [ i ] ≤ 1, i = 1. . n. The problem is to put these balls in a minimum number of boxes so that:
- each box contains no more than two balls, and ii. the total weight of the balls placed in each box is ≤ 1.
- Show an optimum solution for the following instance: W = [0.36, 0.45, 0.91, 62,
0.53, 0.05, 0.82, 0.35].
- Design and analyze an efficient greedy algorithm for this problem.
[Prove the correctness of the algorithm by the greedy loop invariant method and analyze it’s worst-case running time.]