Algorithm Analysis Midterm with answer (UTAR)
True/False: Is 2^(n+1) = O(2^n) ? - Correct answer-False
3^n + 12 - Correct answer-O(2^n)
What is the Asymptotic complexity of a binary search given the code below and the following recursion
equation:
T(n) = T(n/2) + 1
// initially called with low = 0, high = N - 1
BinarySearch_Right(A[0..N-1], value, low, high) {
// invariants: value >= A[i] for all i < low value <
A[i] for all i > high if (high < low) return low
mid = (low + high) / 2 if (A[mid] > value) return
BinarySearch_Right(A, value, low, mid-1) else
return BinarySearch_Right(A, value, mid+1, high)
} - Correct answer-O(lg * n)
Given the following algorithm, what is the number of fundamental instructions that this routine will
execute if the value of n is 4?
var M = A[ 0 ];
for ( var i = 0; i < n; ++i ) {
if ( A[ i ] >= M ) {
M = A[ i ];
, }
} - Correct answer-4+2n
True/False: A Boolean variable can take on only 1 value. - Correct answer-False
Which of the following is NOT a property of logarithms?
a. log(nm) = log n + log m
b. log(n/m) = log n - log m
c. log (n^r)= r log n
d. log(b) n= log(n)b log(a)b - Correct answer-d
True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in
finite time. - Correct answer-True
True/False: The running time of an algorithm is the number of instructions it executes when run on a
particular instance. - Correct answer-True
True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in an
infinite number of steps. - Correct answer-False
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. - Correct answer-True
The Backtracking algorithm implements what search?
a. Depth First Search
b. Sequential search
c. Breadth First Search
True/False: Is 2^(n+1) = O(2^n) ? - Correct answer-False
3^n + 12 - Correct answer-O(2^n)
What is the Asymptotic complexity of a binary search given the code below and the following recursion
equation:
T(n) = T(n/2) + 1
// initially called with low = 0, high = N - 1
BinarySearch_Right(A[0..N-1], value, low, high) {
// invariants: value >= A[i] for all i < low value <
A[i] for all i > high if (high < low) return low
mid = (low + high) / 2 if (A[mid] > value) return
BinarySearch_Right(A, value, low, mid-1) else
return BinarySearch_Right(A, value, mid+1, high)
} - Correct answer-O(lg * n)
Given the following algorithm, what is the number of fundamental instructions that this routine will
execute if the value of n is 4?
var M = A[ 0 ];
for ( var i = 0; i < n; ++i ) {
if ( A[ i ] >= M ) {
M = A[ i ];
, }
} - Correct answer-4+2n
True/False: A Boolean variable can take on only 1 value. - Correct answer-False
Which of the following is NOT a property of logarithms?
a. log(nm) = log n + log m
b. log(n/m) = log n - log m
c. log (n^r)= r log n
d. log(b) n= log(n)b log(a)b - Correct answer-d
True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in
finite time. - Correct answer-True
True/False: The running time of an algorithm is the number of instructions it executes when run on a
particular instance. - Correct answer-True
True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in an
infinite number of steps. - Correct answer-False
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. - Correct answer-True
The Backtracking algorithm implements what search?
a. Depth First Search
b. Sequential search
c. Breadth First Search
