UCCC 2063 Algorithm Analysis Midterm
with answer (UTAR)
True/False: Is 2^(n+1) = O(2^n) ? - ANSWER>>False
3^n + 12 - 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)
} - 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 ];
}
} - ANSWER>>4+2n
True/False: A Boolean variable can take on only 1 value. - 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 - ANSWER>>d
True/False: An algorithm is a well-defined sequence of steps used to solve a well-
defined problem in finite time. - ANSWER>>True
True/False: The running time of an algorithm is the number of instructions it
executes when run on a particular instance. - 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. - 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. - ANSWER>>True
The Backtracking algorithm implements what search?
a. Depth First Search
b. Sequential search
c. Breadth First Search
d. Binary Search - ANSWER>>a
Which of the following is NOT one of the steps used in a Divide-and-conquer
algorithm to solve a problem?
a. Breaking the problem into subproblems that are themselves smaller instances of
the same type of problem
with answer (UTAR)
True/False: Is 2^(n+1) = O(2^n) ? - ANSWER>>False
3^n + 12 - 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)
} - 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 ];
}
} - ANSWER>>4+2n
True/False: A Boolean variable can take on only 1 value. - 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 - ANSWER>>d
True/False: An algorithm is a well-defined sequence of steps used to solve a well-
defined problem in finite time. - ANSWER>>True
True/False: The running time of an algorithm is the number of instructions it
executes when run on a particular instance. - 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. - 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. - ANSWER>>True
The Backtracking algorithm implements what search?
a. Depth First Search
b. Sequential search
c. Breadth First Search
d. Binary Search - ANSWER>>a
Which of the following is NOT one of the steps used in a Divide-and-conquer
algorithm to solve a problem?
a. Breaking the problem into subproblems that are themselves smaller instances of
the same type of problem
