Asymptotic Notations, Recurrence Relations, and Dynamic Programming
Asymptotic Notations and Correctness of Algorithms
1. 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)).
2. Rank the following functions by increasing order of growth: log( n! ), 10000n^2, log(n^3), 2^n, n^2log(n) log(n3), log( n! ), 10000n2, n2log(n), 2n
3. 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))
4.Which of the following can be used to compare two algorithms? growth rates of the two algorithms
5. If you are given different versions of the same algorithm with the following complexity classes, which one would you select? Logarithmic
6. When we say algorithm A is asymptotically more efficient than B, what does that imply? A will always be a better choice for large inputs
7. Consider the following algorithm What is its basic operation (write the line number of code which would define the execution time of the code)?
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
8. 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
9. What is the correct loop invariant for the below code: 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].
for i in range(len(A)): # in pseudo-code for i=0,…,len(A)-1
answer += A[i]
return answer
10. 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
Recursion, Recurrence Relations and Divide & Conquer
1. Which of the following correctly defines what a ‘recurrence relation’ is? An equation (or inequality) that relates the nth element of a sequence to its predecessors (recursive case). This includes an initial condition (base case).
2. Given the following algorithm
foo(n)
if n 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. Θ(n^2)
3. What is the solution of T(n) = 2T(n/2) + n^2 using the Master theorem? Θ(n^2), Case 3
4. Solve the following recurrence by giving the tightest bound possible. T(n) = 4T(n/4) + 4n Θ(nlogn)
5. What is the solution of T(n) = 2t(n/2) + n/logn𝑇(𝑛)=2𝑇(𝑛/2)+𝑛/𝑙𝑜𝑔𝑛 using the Master theorem? Master Method does not apply Example4 of exploration: This looks like it might satisfy the Special Case where f(n) is Theta(n^(logb(a)) * (log(n))^k) for some k >= 0″
6. We can use Divide and Conquer technique to solve a problem in which of the following scenarios? We can break the problem into several subproblems that are similar to the original problems but smaller in size
7. What would be the time complexity of the following algorithm? Θ(n^4)
int sum = 0;
for (i = 0; i for (j = 0; j
for (k = 0; k if (i == j == k) {
for (l = 0; l sum = i + j + k + l;
}
}
}
}
}
8. What would be the time complexity of the following algorithm? O(n^2)
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
9. Which of the following equations correctly represent the factorial function. Factorial of a number n is given by: Factorial of n = n * (n-1) * (n-2) …. 3 * 2 * 1
10. 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
Dynamic Programming
1. What are the major required aspects in a problem in order to apply Dynamic Programming Technique? Optimal Substructure and Overlapping subproblems
2. In which of the following approaches we start with the base case and proceed to solve the bigger subproblems? Bottom-up Approach
3. In dynamic programming, the technique of storing the previously calculated values is called Memoization
4. The difference between Divide and Conquer Approach and Dynamic Programming is Whether the sub-problems overlap or not
5. 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? Divide and Conquer since there are repeatable subproblems, but not Dynamic Programming because there are no overlapping sub-problems.
6. 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 element in the bottom right corner of the cache[m][n]
7. In bottom-up approach we start with the base case and build the solution starting from base case. In top-down approach we start solving the the bigger problem proceed towards the base case.
Dynamic Programming and Backtracking
1. 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
2. To find the optimal solution for 0-1 knapsack, what would be dimensions of the extra array that we would need? The knapsack has a capacity of W, and there are total of n items. Assume we are using the approach that was discussed in the exploration. Array[W+1][n+1]
3. We are given an array of numbers and we are asked to find an optimal solution to maximize the sum of numbers (i.e continuous subsequence that has maximum sum). if the order of the input numbers were altered or if we use a different algorithm, we will always end up with the same combination of numbers as answer. False
4. Backtracking is used to solve which of the problems: To find all possible solutions
5. What is the correct recurrence formula for the unbound knapsack problem that was discussed in the exploration? Consider the weight of the items w[1..n], value of the items v[1..n] F(x) = max{ F[x-wi] + vi }
6. In the o-1 knapsack recurrence formula f(x,i) = max{ vi + f[x-wi , i-1] , f[x , i -1] } The first part vi + f[x-wi , i-1] represents : adding the ith item to the knapsack The second part f[x , i -1] represents: not adding the ith item to the knapsack
Backtracking and Greedy Algorithms
1. What makes the solution for the ‘Activity Selection Problem’ that we implemented in the exploration, a greedy approach? We make a best available choice in each iteration and we never look back
2. Pick the statements which are True. •Dynamic programming technique would always return an optimal solution •Greedy algorithms are efficient compared to dynamic programming algorithms •A greedy algorithm is hard to design sometimes as it is difficult to find the best greedy approach
3. All possible greedy algorithms, at each step, choose what they know is going to lead to an optimal/near optimal solution. True
4. Can 0/1 knapsack problem be solved using the Greedy algorithm technique to obtain an optimum solution to fill the knapsack? 0/1 knapsack problem (This is the problem that we saw in the previous modules) When have n items and their values given. We are provided with a knapsack of capacity X. We have only one copy of each item. We need to maximize the value of our knapsack with items that we pick. False Greedy solution might not give us an optimal solution.
5. Fill in the below pseudocode for activity selection problem using the greedy approach. The function returns the count of the maximum number of activities that can be selected.
activitySelection(activities):
sortBasedonEndTime(activities) # uses quick sort to sort the activities
for activity in activities:
if currendEndTime result = result + 1
currentEndTime = activity.endTime
return result
Time complexity for the pseudocode will be O(n^2) Quick sort has worst case of O(n^2) time complexity
6. The asymptotic runtime of the solution for the combination sum problem that was discussed in the exploration is Expone
ntial
Time Complexity
Polynomial -> n^o Exponential -> o^n
Permutation Problem -> n!
Power set -> 2^n
Combination Sum -> k * 2^n
N Queens
T(n) = n T(n-1) + n^2
= n[(n-1) T(n-2) + (n-1)^2] + n^2
= n(n-1)[n-2 T n-3)]
= n(n-1)(n-2)(n-2)
= O(n!)
for k
for j
z O(n^2)
Comparing Function Growth
1. f(n) = 0.01n^3; g(n) = 50n+10 n^3/n -> inf. = omega, >
Pseudocode LCS – dp – overlapping subproblems & optimal structure
