Question 1

True/False:  Is $$2^{\left(n+1\right)}=O\left(2^{n}\right)?$$

Select one:

• True
• False

The correct answer is 'False'.

Question 2 $$3^{n}+12$$ Select one:

• a.$$ Θ(3^n) $$
• b.$$ Ω(3^n) $$
• c.$$ Ο(2^n) $$
• d.$$ Ο(3^n) $$

The correct answer is: $$Θ(3^n)$$

Question 3

What is the Asymptotic complexity of a binary search given the code below and the following recursion equation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// initially called with low = 0, high = N - 1
  BinarySearch_Right(A[0..N-1], v alue, low , high) {
      // in variants: v alue >= A[i] for all i < low
                     v alue < A[i] for all i > high
      if (high < low)
          return low
      mid = (low + high) / 2
      if (A[mid] > v alue)
          return BinarySearch_Right(A, v alue, low , mid-1)
      else
          return BinarySearch_Right(A, v alue, mid+1, high)
  }

Select one:

• a.$$ Θ(lg.n) $$
• b.$$ O(n^2) $$
• c.$$ {\O}\left(lg \cdot n\right) $$
• d.$$\Omega \left(lg \cdot n\right)$$

The correct answer is: $$ Θ(lg.n) $$

Question 4

Given the following algorithm, what is the number of  fundamental instructions that this routine will execute if  the value of  n is 4?

1
2
3
4
5
6

varM = A[ 0 ];
for( vari = 0; i < n; ++i ) {
   if( A[ i ] >= M ) {
      M = A[ i ];
   }
}

Select one:

• a.$$4+2n$$
• b.$$10$$
• c.$$n^2$$
• d.$$2n+2$$

The correct answer is: $$ 4+2n $$

Question 5

True/False: A Boolean variable can take on only 1 value.

Select one:

• True
• False

The correct answer is 'False'.

Question 6

Which of the following is NOT a property of logarithms?

Select one:

• a.$$log(nm) = log n + log m$$
• b.$$log(n/m) = log n - log m$$
• c.$$\log \left(n^{r}\right)=r log n$$ *d.$$log_{b} n=log_{n}b \ log_{a}b$$

The correct answer is: $$log_{b} n=log_{n}b \ log_{a}b$$

Question 7

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in finite time.

Select one:

• True
• False

The correct answer is 'True'.

Question 8

True/False:  The running time of an algorithm is the number of instructions it executes when run on a particular instance.

Select one:

• True
• False

The correct answer is 'True'.

Question 9

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in an infinite number of steps.

Select one:

• True
• False

The correct answer is 'False'.

Question 10

True/False: The backtracking algorithm treats the solution space as a graph and follows a path to conclusion to find a solution to a problem.   The algorithm may 'backtrack' by reversing up to previous branches in a tree and try all branches to find the solution.

Select one:

• True
• False

The correct answer is 'True'.

Question 11

The Backtracking algorithm implements the following search?

Select one:

• a.Depth First Search
• b.Sequential search
• c.Breadth First Search
• d.Binary Search

The correct answer is: Depth First Search