Securing Higher Grades Costing Your Pocket? Book Your Assignment at The Lowest Price Now!

Get assignment help service to meet the high expectations of your professors


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 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:

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

Want solution for this assignment
Assignment Help Features
Assignment Help Services
  • Assignment Help
  • Homework Help
  • Writing Help
  • Academic Writing Assistance
  • Editing Services
  • Plagiarism Checker Online
  • Proofreading
  • Research Writing Help
QR Code Assignment Help