k Flashcards
Is the following a property that holds for all non-decreasing positive functions f and g? (True=Yes/ False=No)
If f(n) = O(n2) for c=1 and n0=0 and
g(n) = Theta(n2) for n0=0 and c1 =1 and c2=1
then f(n) = O(g(n)).
True
Rank the following functions by increasing order of growth:
log( n! ), 10000n2, log(n3), 2n, n2log(n)
log(n3), log( n! ), 10000n2, n2log(n), 2n
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?
- A(n) = O(W(n))
- A(n) = \Theta(W(n))
- None of the options
- A(n) = \Omega(W(n))
A(n) = O(W(n))
Which of the following can be used to compare two algorithms?
- implementations of the two algorithms
computers on which programs which implement the two algorithms are run - growth rates of the two algorithms
- number of input parameters required for two algorithms
growth rates of the two algorithms
If you are given different versions of the same algorithm with the following complexity classes, which one would you select?
- linear
- quadratic
- Logarithmic
- polynomial
logarithmic
When we say algorithm A is asymptotically more efficient than B, what does that imply?
- B will always be a better choice for small inputs
- A will always be a better choice for large inputs
- B will always be a better choice for all inputs
- A will always be a better choice for small inputs
A will always be a better choice for large inputs
Consider the following algorithm
1 Bubble-sort(a)
2 for i = a.length() to 1
3 for j = 1 to i-1
4 if a[j]>a[j+1]
5 swap(a[j],a[j+1]);
6 end if
What is its basic operation (write the line number of code which would define the execution time of the code)?
4
What is the basic operation (that which is executed maximum number of times) in the following code?
reverse(a):
for i = 1 to len(a)-1
x = a[i]
for j = i downto 1
a[j] = a[j-1]
a[0] = x
a[j] = a[j-1]
What is the correct loop invariant for the below code:
for i in range(len(A)): # in pseudo-code for i=0,...,len(A)-1
answer += A[i]
return answer
- at the start of iteration i of the loop, the variable answer should contain the sum of the numbers from the subarray A[0:i-1]
- the loop iterates from i ranging from 0 to length of the array
- the loop stops when i reaches the last element of the array
- the result of this code will be the sum of all the elements in the array
At the start of iteration i of the loop, the variable answer should contain the sum of the numbers from the subarray A[0:i-1].
Select correct inequality for the asymptotic order of growth of the below function. That is, as the value of n becomes very large what is the relation between the two functions.
n ___ n^2
<
Which of the following correctly defines what a ‘recurrence relation’ is?
- An equation (or inequality) that represents nth iteration of a sequence in terms of n. That includes an initial condition.
- T(n) = 2(1+n), T(0) = 2
- T(n)=T(n-1)+2n, T(0)=1
- An equation (or inequality) that relates the nth element of a sequence to its predecessors (recursive case). This includes an initial condition (base case).
An equation (or inequality) that relates the nth element of a sequence to its predecessors (recursive case). This includes an initial condition (base case).
Given the following algorithm
foo(n)
if n <= 1
return 1
else
x = foo(n-1)
for i = 1 to n
x = x + i
return x
Determine the asymptotic running time. Assume that addition can be done in constant time.
Theta(n^2)
Solve the following recurrence by giving the tightest bound possible.
T(n) = 4T(n/4) + 4n
Theta(nlogn)
What is the solution of T(n) = 2T(n/2) + n^2
using the Master theorem?
Theta(n^2), case 3
What is the solution of T(n) = 2T(n/2) + n/logn
using the Master theorem?
master method does not apply
We can use Divide and Conquer technique to solve a problem in which of the following scenarios?
- None of the options
- The complexity is exponential to solve the entire problem
- The subproblems are overlapping so we don’t have to solve them over and over again
- We can break the problem into several subproblems that are similar to the original problems but smaller in size
We can break the problem into several subproblems that are similar to the original problems but smaller in size
What would be the time complexity of the following algorithm?
int sum = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
if (i == j == k) {
for (l = 0; l < nnn; l++) {
sum = i + j + k + l;
}
}
}
}
}
Theta(n^4)
What would be the time complexity of the following algorithm?
reverse(a):
for i = 1 to len(a)-1
x = a[i]
for j = i downto 1
a[j] = a[j-1]
a[0] = x
O(n^2)
Which of the following equations correctly represent the factorial function.
- f(n) = (n-1) f(n-1)
- f(n-1) = n f(n) - f(n) = n f(n)
- f(n) = nf(n)
- f(n) = n f(n-1)
f(n) = n f(n-1)
Which of the following recurrence relations is correct representation of the towers of Hanoi problem that was discussed in the exploration?
- F(n) = 2F(n-1) + 1
- F(n) = F(n-1) + 2
- F(n) = 2F(n-1)
- F(n) = nF(n-1) + 1
F(n) = 2F(n-1) + 1
What are the major required aspects in a problem in order to apply Dynamic Programming Technique?
- Base case to stop recurrence
- Be able to solve using top down and bottom up approach
- Optimal Substructure and Overlapping subproblems
- Whether a problem can be divided or not
Optimal Substructure and Overlapping subproblems
In which of the following approaches we start with the base case and proceed to solve the bigger subproblems?
- both
- none of the options
- bottom-up approach
- top-down approach
bottom-up approach
In dynamic programming, the technique of storing the previously calculated values is called
- bottom-up approach
- top-down approach
- cache
- memoization
memoization
The difference between Divide and Conquer Approach and Dynamic Programming is
- The way we divide the sub-problems
- The base case
- Whether the sub-problems overlap or not
- Use of recurrence formula
Whether the sub-problems overlap or not
A binary search algorithm searches for a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found or until a search can no longer be performed. This problem can be solved using which of the techniques?
- Any of the two techniques
- Dynamic Programming
- None of the options
- Divide and Conquer
Divide and Conquer
In the Longest Common Subsequence problem assume we are comparing two strings of lengths m and n. In the bottom-up approach the solution we build a 2-Dimensional array called Cache[m][n]. The final solution was obtained by accessing which element of the cache?
- The last but one element in the cache[m][n]
- Any element in the Cache[m][n]
- The first element in the cache[m][n]
- The element in the bottom right corner of the cache[m][n]
The element in the bottom right corner of the cache[m][n]
In _______ approach we start with the base case and build the solution starting from base case. In
________ approach we start solving the the bigger problem proceed towards the base case.
bottom-up approach
top-down approach
Given two integer arrays to represent weights and profits of ’N’ items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number ‘C’. Best technique to solve this problem is?
- Dynamic Programming
- Brute Force
- Backtracking
- Divide and Conquer
Dynamic Programming
