Design and Analysis of Algorithm

(Write pseudo code wherever necessary)

Question 1)

Small Decision Tree:

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

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

Question 2)

Lower Bound on BST construction:

1. 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?

1. 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⁰, c¹, c² , …, 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:

1. each box contains no more than two balls, and ii. the total weight of the balls placed in each box is ≤ 1.

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

1. 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.]