Q1. Illustrate the operation of HEAPSORT on the array A = {15, 113, 12, 125, 17, 117, 120, 18, 14}. Show, visually, the binary tree just after the BUILD-HEAP is called and at the end of each of the HEAPIFY operation. Q2. Write a complete algorithm that determines if a given number is a favorite number or not. Use the following definition of a favorite number. The algorithm should take one parameter, the number, and print a message that says if the number is favorite or not. A number N (greater than 0) is said to be favorite if the sum of all its factors equals the number. For example, 6 is a favorite number because 1 + 2 + 3 = 6, and 1, 2 and 3 are favorite of 6. 28 is also a favorite number because 1 + 2 + 4 + 7 + 14 = 28, and the individual numbers are all factors of 28. Q3. Given some items, pack the knapsack to get the maximum total value. Each item has some weight and some value. Total weight that we can carry is no more than some fixed number W. So, we must consider weights of items as well as their values. Items are indivisible; you either take an item or not. Considering Weights = {3,4,6,5} Profits = (2,3,1,4} W= 8, n=4 Solved the problem with dynamic programming. Draw the look-up table, based on the Dynamic Programming method, for the 0-1 knapsack problem. Provide the final optimal solution, too Q4. Write a complete Greedy algorithm for the Fractional Knapsack problem. The problem is defined as follows: Terrorist robbing a store finds n items each item worth Pi Rupees and weighs Wi kg. Terrorist has a knapsack of capacity W kg (Terrorist can carry a total weight of not more than W kg). Terrorist is allowed to carry all the quantity available of an item or a fraction thereof. What items should the Terrorist take and how much of each of those items to maximize the value of the theft?
