questions 14, 15, 16 and 17 230 3/Algorithms a) Show that this algorithm uses O(
ID: 3733099 • Letter: Q
Question
questions 14, 15, 16 and 17
230 3/Algorithms a) Show that this algorithm uses O(n3) comparisons to b) 1000n compute the matrix M. d) 1000n2 b) Show that this algorithm uses 2(n) comparisons to compute the matrix M. Using this fact and part (a), conclude that the algorithms uses (n*) comparisons. Hint: Only consider the cases where i s /4 and 17. What is the largest for which one can solve within a minute using an algorithm that requires f (n) bit op- erations, where each bit operation is carried out in 10 seconds, with these functions f (n)? a) log logn d) 1000000 e) n j3n/4 in the two outer loops in the algorithm.] 13. The conventional algorithm for evaluating a polynomial anx" +an-ix"-' + . . . + aix +ao at x = c can be ex b) log n c) logn pressed in pseudocode by procedure pohnomíal(c, ao, ai, n : real numbers) 18. How much time does an algorithm take to solve a prob- lem of size n if this algorithm uses 2n 2" operations, each requiring 10-9 seconds, with these values of n? for i := l to n power := power * c y:= y + ai * power 19. How much time does an algorithm using 250 operations return y (ya+an-1c++ac +aol where the final value of y is the value of the polynomial need if each operation takes these amounts of time? a) 10-6 12 10-ess0 20. What is the effect in the time required to solve a prob- lem when you double the size of the input from n to 2n assuming that the number of milliseconds the algorithm uses to solve the problem with input size n is each of these function? [Express your answer in the simplest form pos- sible, either as a ratio or a difference. Your answer may be a function of n or a constant.] a) log log n b log n a) Evaluate 3x2 +x +1 at x 2 by working through each step of the algorithm showing the values assigned at each assignment step. b) Exactly how many multiplications and additions are used to evaluate a polynomial of degree n at x = c? Do not count additions used to increment the loop c) 100n variable.) n logn 14. There is a more efficient algorithm (in terms of the num- ber of multiplications and additions used) for evaluating polynomials than the conventional algorithm described in the previous exercise. It is called Horner's method. This pseudocode shows how to use this method to find the 8) 2" 21. What is the effect in the time required to solve a problem when you increase the size of the input from n to1 assuming that the number of milliseconds the algorithm uses to solve the problem with input size n is each of these function? [Express your answer in the simplest form pos- sible, either as a ratio or a difference. Your answer may be a function of n or a constant.] value ofanx" +an-ir"-i+ +alx+a0 at x = c y := an b) 100n e) g) n! a) Evaluate 3x2 +x +1 at x 2 by working through each step of the algorithm showing the values assigned 22. Determine the least number of comparisons, or best-case a) required to find the maximum of a sequence of n in- b) used to locate an element in a list of n terms with a c) used to locate an element in a list of n terms using a at each assignment step. b) Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at c? Do not count additions used to tegers, using Algorithm 1 of Section 3.1 increment the loop variable.) search. 15. What is the largest n for which one can solve within one second a problem using an algorithm that requires f (n) it operations, where each bit operation is carried out in binary search. 23. Analyze the average-case performance of the linear search algorithm, if exactly half the time the element x is not in the list and if x is in the lis s equally likely to 0 seconds, with these functions f(n)? n logn be in any position. 16. What is the largest n for which one can solve within a day using an algorithm that requires f (n) bit where each bit operation is carried out in 101 seconds, with these functions f(n)? 24. An algorithm is called optimal for the solution of a prob- lem with respect to a specified operation if there is no algorithm for solving this problem using fewer opera-Explanation / Answer
Q.14)
a) Initialy y=3 //as per question
In for loop
Iteration 1st i=1
y=3*2+1 //y=y*c+an-i here c=2 and an-i=1 =1 ;here y=7 after oeration
Iteration 2nd i=2
y=7*2+1 //y=y*c+an-i here c=2 and an-i=1 =1
After end of loop value returned shuolud be y=15
b) During evaluation of polynomial of degree at most n addition and (n2 +n)/2 multiplication required.
Q.15) a) if f(n)=logn
By subsituting the value we get 210^9 approx 103*108
for option b) if subsitute the value we get 109
C) in this case OF GIVEN FUNCTION we get 3.96*107
D)IN THIS CASE OF GIVEN FUNCTION WE GET 3.16*10 4 AFTER SUBSITUTIING THE VALUE
E) IN THIS PART IOF GEIVE FUNCTION WE GET 29 AFTER SUBSITUTING
F) IN THIS PART FOR GIVEN FUNCTION WE GET 12
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.