Can U please give us the exact answer

Question no 1

Solve the recurrence relation T(n)=T(n-1)+ T(n-3) -T(n-4) , n>4 subject to T(n)= n for 0<=n<=3

Prove 7n2 -8n= (n2 )

Qurestion No 2

Solve the following instance of knapsack problem using Dynamic Computing.

(O denotes number of objects and C is the capacity of sack).

a. O=8

b. C=13

c. P1,P2,P3,P4,P5,P6,P7,P8 = 11,4,14,7,6,14,3,2

d. W1,W2,W3,W4,W5,W6,W7,W8 = 2,3,5,7,4,1,6

Question No 3:

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. Suppose that the available coins are in the charity bills that are powers of n, i.e., the charity bills are n 0 , n 1 , ...,nk for [4,15,6,7,9,3,2]. Show that the greedy algorithm always yields an optimal solution but keep the following terms in mind that

a. Solution should have most two dimes, at most one nickel at most four pennies,

b. Solution cannot have two dimes and a nickel.

c. The amount of change in dimes, nickels, and pennies cannot exceed 54 cents.