COT-4400: Design and Analysis of Algorithms QUESTION 1 The algorithm below compu

Question

COT-4400: Design and Analysis of Algorithms

QUESTION 1

The algorithm below computes the maximum value in an array A[1..n] with n elements:

Which of the following is the correct loop invariant of the for loop?

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i-1].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..n].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[0..i-1].

QUESTION 2

Arrange the following functions in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) = O(g(n)).

question 3:

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i-1].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..n].

At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[0..i-1].

Explanation / Answer

Question 1
b) At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i].
int max(int* l,int n){
   int mx = -INFINITY;
   for (int i = 0; i < n; i++){
       if (l[i] > mx)
           mx = l[i];
   }
   return mx;
}

Question 2:

1. N^3
2. 9^(log3 (n))
3. N^2 * log n
4. 1^n
5. (1/3)^n
6 (log n)^3

functions in ascending order of growth rate
N^3 > 9^(log3 (n)) > (log n)^3 > N^2 * log n > 1^n > (1/3)^n

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects