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(n²)

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. n²

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) = n²

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