# Design and Analysis of Algorithm

*(Write pseudo code wherever necessary)*

__Question 1)__

__Small Decision Tree:__

- Show that every comparison based (i.e., decision tree) algorithm that sorts 5 elements, makes
7 comparisons in the worst-case.__at least__

- Give a comparison based (i.e., decision tree) algorithm that sorts 5 elements using
7 comparisons in the worst case.__at most__

__Question 2)__

__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.

__Question 3)__

__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 c
^{0}, c^{1}, c^{2}, …, c^{n-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.] *