Font size
WorksheetsADA Quiz
Total questions: 16
Worksheet time: 6mins
1. The complexity of merge sort algorithm is
O(n)
O(log n)
O(n2)
O(n log n)
Master’s theorem is used for?
solving recurrences
solving iterative relations
analyzing loops
calculating the time complexity of any code
Consider the given graph. What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
23
15
19
23
What is the worst case run-time complexity of binary search algorithm?
Ο(n2)
Ο(nlog n)
Ο(n3)
Ο(n)
Which of the following is an example of dynamic programming approach?
01 Knapsack
Binomial Coefficient
Floyd Marshal
All of the above
Which of the following searching techniques require the data to be in sorted form
Binary Search
Interpolation Search
Linear Search
All of the above
How many swaps are required to sort the given array using bubble sort - { 2, 5, 1, 3, 4}
4
5
6
7
In dynamic programming, the technique of storing the previously calculated values is called ___________
Saving value property
Storing value property
Memorization
Mapping
What are 2 things required in order to successfully use the dynamic programming technique?
Optimal sub structure and overlapping sub problems
A problem that can’t be sub divided and is complex
Non overlapping sub problems and intervals
Recursion and a problem that is complex
Dynamic Programming is often used for (choose all that apply):
Optimization problems that involve making a choice that leave one or more subproblems to be solved.
Problems previously solved using divide and conquer that have over lapping subproblems
Non polynomial solution problems
Subproblems where resources are shared
The difference between Divide and Conquer and Dynamic Programming is:
The division of problems and combination of subproblems
Whether the sub problems overlap or not
The way we solve the base case
The depth of recurrence
If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
Overlapping subproblems
Optimal substructure
Memorization
Greedy
Which of the following problems is NOT solved using dynamic programming?
0/1 knapsack problem
Matrix chain multiplication problem
Edit distance problem
Fractional knapsack problem
You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the 01 knapsack?
170
200
160
90
Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
10*20
20*30
10*30
10*20*30
Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
6
7
8
9
