logo
+1-617-874-1011 (US)
+61-7-5641-0117 (AU)
+44-117-230-1145 (UK)
Live Chat

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
Improve Your Grades with Custom Writing Help
Homework Help
Writing Help
Editing Services
Plagiarism check
Proofreading services
Research Project help
Custom writing services
scanner
E learning blogs

Disclaimer : The study tools and academic assistance/guidance through online tutoring sessions provided by AssignmentHelp.Net is to help and enable students to compete academically. The website does not provide ghostwriting services and has ZERO TOLERANCE towards misuse of the services. In case any user is found misusing our services, the user's account will be immediately terminated.