1 (a). List all the steps used by the following algorithm for the list [5,4,3,2,

Question

1 (a). List all the steps used by the following algorithm for the list [5,4,3,2,7,6]. What is the final value of x? local x,i; -1; Findx := proc (L ::list (integer)) for i from 1 nops (L) do x := if L[1] mod 2 = 0 then if x -1 or x > L[i] then x := L[i],end if; end if end do; return x; end proc; 1 (b). Modify the algorithm of part (a) so that it takes as input a list of integers and produces as output the largest odd integer in the list or 0 if there is no odd integer in the list. 2 (a). Show that 3x8 + x7 + 4x52x2 5x 7 is o(x8) using the Definition of o(x8) 2 (b). Find the least integer n such that 2x x3 log x is o(xa) using the definition of 0(Xn) 3 (a). show that 5x3 + 2x4 log x is (x') using the definition of 3(b). Show that 2x3 + 7x2 log x is (x?) using the definition of 9(x3) 4 (a). Give a big-O estimate for the number of comparisons used in this segment of an algorithm. Explain your answer. m := L[1]; n := nops (L); for i from 1 to n do if m > L[i] then m := L[i] ; end if; end do;

Explanation / Answer

(According to Chegg policy, only four subquestions will be answered. Please post the remaining in another question)

1. (a) Note that the procedure determines the greatest even number in the list or if there is none returns -1.

Step 1 : Local variable x is set to -1.

Step 2 : The for loop picks the first element in the list i.e 5

Step 3 : Since 5 is not divisible by 2 it is discarded

Step 4 : The for loop picks the next element in the list i.e 4

Step 5 : Since 4 is divisible by 2 and x = -1, x is set to 4

Step 6 : The for loop picks the next element in the list i.e 3

Step 7 : Since 3 is not divisible by 2 it is discarded

Step 8 : The for loop picks the next element in the list i.e 2

Step 9 : Since 2 is divisible by 2 but x = 4 > 2, it is discarded

Step 10 : The for loop picks the next element in the list i.e 7

Step 11 : Since 7 is not divisible by 2 it is discarded

Step 12 : The for loop picks the next element in the list i.e 6

Step 13 : Since 6 is divisible by 2 and 6 > x = 4, x is set to 4

Step 14 : The value 6 is returned.

1. (b) The modified algorithm is

Findx := proc (L::list(integer)) local x,i; x = 0;

for i from 1 to nops(L) do

if L[i] mod 2 = 1 then

if x = 0 or x > L[i] then x := L[i]; end if;

end if;

end do; return x; end proc;

2. (a) Let f(x) = 3x8 + x7 + 4x5 + 2x2 + 5x + 7

=> f(x) <= 3x8 + x8 + 4x8 + 2x8 + 5x8 + 7x8 x >= 1

=> f(x) <= 22x8   x >= 1

According to definition,

=> f(x) = O(x8)

2.b. We have

log x < x x >= 1

=> x3 log x < x3 * x x >= 1

=> x3 log x < x4   x >= 1

Also 2x3 < 2x4   x >= 1

Adding the two inequalities

=> 2x3 + x3 log x < 3x4   x >= 1

Thus 2x3 + x3 log x = O(x4)

The least integer n is 4.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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