Divide and Conquer

Download as pdf or txt
Download as pdf or txt
You are on page 1of 4

Download our App for Study Materials and Placement Preparation 📝✅ | Click Here 

(https://play.google.com/store/apps/details?id=co.jones.cjzgt)

Get Latest Exam Updates, Free Study materials and Tips


Your Name
(https://lastmomenttu
Your Branch
itions.com/)
Year Of Engineering

[MCQ] Analysis Of Algorithms

Introduction (#1617622154105-59ec4c41-97a6)

Divide and Conquer Approach (#1617622154112-c1392ccd-f510)

 Module 2

1. The approach of dynamic programming is


similar to
a. Parsing
b. Hash table
c. Divide and Conquer algorithm
d. Greedy algorithm
Answer: C
Divide and Conquer algorithm

2.The algorithms like merge sort, quick sort


and binary search are based on
a. Greedy algorithm
b. Divide and Conquer algorithm
c. Hash table
d. Parsing
Answer: D
Divide and Conquer algorithm

3.The step(s) in the Divide and conquer


process that takes a recursive approach is said to
be
a. Conquer/Solve
b. Merge/Combine
c. Divide/Break
d. Both B and C
Answer : C
Divide/Break

4.The sub-problems in the dynamic


programming are solved
a. Dependently
b. Independently
c. Parallel
d. Concurrent
Answer: D
Concurrent

5. In the Divide and Conquer process, breaking


the problem into smaller sub-problems is the
responsibility of
a. Divide/Break
b. Sorting/Divide
c. Conquer/Solve
d. Merge/Combine
Answer: A
Divide/Break

Crack Job Placement Aptitude in First Attempt

Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! (https://lastmomenttuitions.com/aptitude/?ref=42057)

6.Which of the following algorithms is NOT a divide & conquer algorithm by nature?
a.Euclidean algorithm to compute the greatest common divisor
b.Heap Sort
C.Cooley-Tukey fast Fourier transform
d.Quick Sort
Answer b
Heap Sort

7.Consider the following C program


int main()
{
int x, y, m, n;
scanf (“%d %d”, &x, &y);
/* x > 0 and y > 0 */
m = x; n = y;
while (m != n)
{
if(m>n)
m = m – n;
else
n = n – m;
}
printf(“%d”, n);
}

What does the program compute? (GATE CS 2004)


a.x + y using repeated subtraction
b.x mod y using repeated subtraction
c.the greatest common divisor of x and y
d.the least common multiple of x and y
Answer C
the greatest common divisor of x and y

8.Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to
evaluate p on an input x is:
a.3
b.4
c.6
d.9
Answer A
3
9.Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10},
the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and
return the maximum of all. We can solve this using Divide and Conquer, what will be the worst case time complexity using Divide and
Conquer.
a.O(n)
b.O(nLogn)
c.O(Logn)
d.O(n^2)
Answer B
O(nLogn)

10.Consider a situation where you don’t have function to calculate power (pow() function in C) and you need to calculate x^n where x can
be any number and n is a positive integer. What can be the best possible time complexity of your power function?
a.O(n)
b.O(nLogn)
c.O(LogLogn)
d.O(Logn)
Answer D
O(Logn)

Python Programming for Complete Beginners

Start your Programming Journey with Python Programming which is Easy to Learn and Highly in Demand
Click Here! (https://lastmomenttuitions.com/complete-python-bootcamp/?ref=42057)

11.Consider the problem of searching an element x in an array ‘arr[]’ of size n. The problem can be solved in O(Logn) time if. 1) Array is
sorted 2) Array is sorted and rotated by k. k is given to you and k <= n 3) Array is sorted and rotated by k. k is NOT given to you and k <=
n 4) Array is not sorted
a.1 Only
b.1 & 2 only
c.1, 2 and 3 only
d.1, 2, 3 and 4
Answer C
1, 2 and 3 only

12.The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an
iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The
procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to
be put in place of?
So that it follows all steps of the secant method? Secant
Initialize: xa, xb, ε, N // ε = convergence indicator
fb = f(xb) i = 0
while (i < N and |fb| > ε) do
i = i + 1 // update counter
xt = ? // missing expression for
// intermediate value
xa = xb // reset xa
xb = xt // reset xb
fb = f(xb) // function value at new xb
end while
if |fb| > ε
then // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if
a.xb – (fb– f(xa)) fb/ (xb – xa)
b.xa– (fa– f(xa)) fa/ (xb – xa)
c.xb – (fb – xa) fb/ (xb – fb(xa)
d.xa – (xb – xa) fa/ (fb – f(xa))
Answer D
xa – (xb – xa) fa/ (fb – f(xa))

13.Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of array.
Algorithm A1 can compute min-max in a1 comparisons without divide and conquer. Algorithm A2 can compute min-max in a2
comparisons by scanning the array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?
a.a1 < a2
b.a1 > a2
c.a1 = a2
d.Depends on the input
Answer B
a1 > a2

Learn Machine Learning with Python from Scratch

Start your Machine learning & Data Science journey with Complete Hands-on Learning & doubt solving Support
Click Here! (https://lastmomenttuitions.com/python-with-machine-learning/?ref=42057)

Greedy Method Approach (#1617629753056-e13c69b7-cef6)

Dynamic Programming Approach (#1617632450818-4e763a5a-bfbe)

Backtracking and Branch and bound (#1617635582320-a3acc518-42aa)

String Matching Algorithms (#1617638004246-75673406-edcf)


Prepare For Your Placements: https://lastmomenttuitions.com/courses/placement-preparation/ (https://lastmomenttuitions.com/courses/placement-
preparation/)
(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-

included-mentorship/youtube-2/)

/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q


(https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q)

Follow For Latest Updates, Study Tips & More Content!

(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/insta-1/)/lastmomenttuition (https://www.instagram.com/lastmomenttuition/)

(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/link/)/ Last Moment Tuitions (https://in.linkedin.com/company/last-moment-
tuitions#:~:text=Last%20Moment%20Tuitions%20(LMT)%20is,others%20is%20its%20teaching%20methodology.)

(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/twittrwer/)/ lastmomentdost (https://twitter.com/lastmomentdost)

You might also like