Question 1 Counting only assignment statements as operations, what is the order

Question

Question 1

Counting only assignment statements as operations, what is the order of complexity of the
following code fragment as a function of n?

x = 1;
while (x < n)
             x = x + x;

Select one:

a. O(1)

b. O(n)

c. O(log n)

d. O(n2)

Question 2

Question text

True/False: Recursive routines cannot be used in Dynamic Programming algorithms.

Select one:

True

False

Question 3

True/False: Linear programming is an excellent approach for optimization problems where the objective function graphs as a curvilinear line.

Select one:

True

False

Question 4

Counting only assignment statements as operations, what is the exact number of operations executed by the following code fragment in terms of n?

x = n;
while (x > 0) {
            z = 0;
            while (z <= 6)
                             z = z + 2;
            x = x - 1;
}

Select one:

a. 6n+1

b. n2

c. 2(6n)

d. 6n

Question 5

Question text

True/False: NP is the set of decision problems that can be solved in polynomial time.

Select one:

True

False

Question 6

What is the running time of the following algorithm (in the worst case) expressed in terms of n?

for i   1 to n
    do if A[i] = x
         then return i
         elseif A[i] < x
               then i   i + 1
              else return “x not found”
return “x not found”

Select one:

a. T(n) = n

b. T(n) = n log n

c. T(n) = 2n

d. T(n) = n2

Question 7

Draw the following graphs:

a. Directed Graph

b. Undirected Graph

c. Tree

d. Directed Acyclic Graph

Question 8

True/False: By the master theorem, the solution to the recurrence T(n) = 3T(n/3) + log n is T(n) = (n log n), assuming the following definition of the master theorem.

Select one:

True

False

Question 9

True/False: Dynamic Programming reduces asymptotic complexity by eliminating redundant computations.

Select one:

True

False

Explanation / Answer

Question 1
Counting only assignment statements as operations, what is the order of complexity of the
following code fragment as a function of n?

x = 1;
while (x < n)
x = x + x;

Ans: O(n). because it depends on n value. So that loop rotates n-1 times. And for the statement x = x + x; time cost is 1 so that ans is n

Question2:
Recursive routines cannot be used in Dynamic Programming algorithms.
Ans: True.
Recursive algorithm is not seem to be a reasonable algorithm of sorting with dynamic programming.

Question 3
Linear programming is an excellent approach for optimization problems where the objective function graphs as a curvilinear line.
Ans: False

Question 4
Ans: a. 6n+1
The inner while loop runs for 6 times as it is evident from the condition (z<=6). The number of times this loop runs depends on the outer loop. And the outer loop runs for n times as x starts from n and for each iteration it gets decremented by 1. Hence, this loop takes 6n times . Inside the inner loop, there's an assigment operation which takes 1 times. Hence , the operations is 6n+1

Question 5:
NP may be equivalently defined as the set of decision problems that can be solved in polynomial time
Ans: True.

Question 8:
Ans:True.
By the master theorem, the solution to the recurrence T(n) = 3T(n/3) + log n is T(n) = (n log n), assuming the following definition of the master theorem.

Question 9
Dynamic Programming reduces asymptotic complexity by eliminating redundant computations.
Ans: False.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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