Let a_{n} be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$?
Consider the recurrence relation $\style{font-family:'Times New Roman'}{a_1=8,a_n=6n^2+2n+a_{n-1}.\mathrm{Let}\;a_{99}=K\times10^4.}$ The value of K is __________.
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ($\ge 2$) numbers? In the recurrence equations given in the options below, c is a constant.
Let a_{n} represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_{n}?
Let P be a quicksort program to sort numbers in ascendinng order using the first element as the pivot. Let t_{1} and t_{2} be the number of comparisions made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. which one of the following holds?
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
Consider the following pseudo code. What is the total number of multiplications to be performed?
D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
$T\left(n\right)=2T\left(\frac{n}{2}\right)+\mathrm{log}n$
The minimum number of arithematic operation required to evaluate the polynomial $P\left(X\right)={X}^{5}+4{X}^{3}+6X+5$ for a given value of X,using only one temporary variable is_____.
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements is
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
Four matrices M_{1}, M_{2} , M_{3} and M_{4}, of dimensions p × q , q × r , r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M_{1} × M_{2}) × (M_{3} × M_{4})). The total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M_{1} × M_{2}) ×M_{3}) ×M_{4}), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is
In quick sort , for sorting n elements, the (n/4)^{th} smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
Which of the following sorting algorithms has the lowest worst-case complexity?
In the following C function, let n ≥ m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); }
How many recursive calls are made by this function?