[PSEUDOCODE] [ALGORITHM] Improving Efficiency Please provide the following answe

Question

[PSEUDOCODE] [ALGORITHM] Improving Efficiency

Please provide the following answers in detail with valid explanations. The algorithm to be used is also given below. (Knapsack Algorithm)

a) What is the exact cost of the function Worth? i.e. how many times will its basic operation be executed when it is called with the parameter SetofItems? [1point]

b) What is the best case cost of the Knapsack algorithm and in which situation does it happen? Note: the answer is not “when n=1”. The best case occurs when the data is configured in such a way that the algorithm will do the least possible work for any given n. [4point]

c) In which situation does the worst case cost occur? (i.e. in which situation does this algorithm do the most work, maximizing both the work of Knapsack and Worth?)[3point]

Description of items is stored in arrays of n elements. Integer weightsIn] weights 3 weight of item i Integer values[n] values vaue of item i Set Knapsack anteger capacity, Integer n) capacity is the knapsack capacity n number of items to fit in the knapsack, n21 This function returns a set containing the most valuable combination of items which can fit in the knapsack Set Knapsack (nteger capacity, Integer n) If n-1 If weights[1] capacity return (1) Else return 0 lfitem n does not fit, leave it out Integer weightn weights[n If weig capacity return Knapsack (capacity, n-1) Best value when item n is included in knapsack Set included J (n) UKnapsack(capacity-weightn, n-1) Best value when item n is not included in knapsack Set excluded 3 Knapsack (capacity,n-1) If Worth excluded) Worth included) return excluded Else return included Integer Worth (Setofltems) Setofltems is a set of items This function returns the worth of a set of items Integer Worth (Setofltems) Integer result 0 For item in Setofltems do Result values item] Return result Additional Information: For the analysis that follows, you will be assuming that the basic operation is an array reference weights il or values i, i.e. you will be asked to count how many times an item is "touched". These references to the basic operation have been highlighted in the code. The size of this algorithm is n. Le. any description of the cost of this algorithm will be a function of n

Explanation / Answer

1. It will be O(n), as in worst case Worth funtion will take n set of items.

2. The best case cost will be 2n (i.e. two multiplied by n). The best case will occur when all given weight are equals to kanpsack capacity.

3. When knapsack capacity is greater then or equal to sum of weight of all elements. In this case, complexity will be polynomial, which is 2^n (i.e. two to the powen n).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.