Question

(a) Your company participates in a competition and the fastest algorithm wins. You know of two different algorithms that can solve the problem in the competition. • Algorithm I solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. • Algorithm 2 solves problems of size n by dividing them into 16 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in (n?) time. Which algorithm is the faster one? Explain your answer in detail. You may use the Master Theorem to answer this question. recurrence Master Theorem For integer constants a > 1 and b > 1, and function f with f(n) € (nº), d > 0, the T(n) = at (n/b) + f(n) (with T (1) = c) has solutions, and (ne) if a <bd T(n) = { ulogn) if a=by (nl) ifa > ball Note that we also allow a to be greater than b. 6) The following algorithm is written by the head chef at PizzaMash to determine what the maximum profit they can receive by selling a long pizza which is L centimetres in length in smaller, variable length slices. They know that the price they can sell an i centimetre slice for is S[i]. function PizzAPROFIT(L) if L ==0 then return 0 po for i in 1...L do p+S[i] + PIZZAPROFIT(L-1) if p'>p then pop return p Unfortunately this algorithm is an exponential time algorithm. Describe how you could use Dynamic Programming to improve the efficiency of this al- gorithm. Give both the time complexity and space complexity of the improved algorithm.

Answer 1

Solution Recurrence Relation a Algorithm - 1 T(p) = 5 T + (n) compare with Tim)- at () + at Gött olmas a-s, 6:2, k = 1 bk, 2 =2 a=5 So that bk ca T(n)= oln tog, a o en tog 25 ) O (22.32 Algasuithm-2 T(n)= 16 T ( + (m2) a=16, 64, 10=2 b = 4² = 16 So Hot bha a= 16 tm). Osnokrogon) o ( n²logn) 2.32 n Inlogn ☆ So algarithm 2 is faster Algorithm because algo 2 have less time then algo 1. care et