Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Divide & Conquer - 4 - Computer Science Engineering (CSE) MCQ

Test: Divide & Conquer - 4 - Computer Science Engineering (CSE) MCQ


Test Description

15 Questions MCQ Test - Test: Divide & Conquer - 4

Test: Divide & Conquer - 4 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Divide & Conquer - 4 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Divide & Conquer - 4 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Divide & Conquer - 4 below.
Solutions of Test: Divide & Conquer - 4 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Divide & Conquer - 4 solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Divide & Conquer - 4 | 15 questions in 35 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Divide & Conquer - 4 - Question 1

Which of the following is not a stable sorting algorithm in its typical implementation.

Detailed Solution for Test: Divide & Conquer - 4 - Question 1

Quick Sort, Heap Sort etc., can be made stable by also taking the position of the elements into consideration. This change may be done in a way which does not compromise a lot on the performance and takes some extra space

Test: Divide & Conquer - 4 - Question 2

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

Detailed Solution for Test: Divide & Conquer - 4 - Question 2

Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Divide & Conquer - 4 - Question 3

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.

Detailed Solution for Test: Divide & Conquer - 4 - Question 3

The time complexity is given by: T(N) = T(N/3) + T(2N/3) + N Solving the above recurrence relation gives, T(N) = N(logN base 3/2)

Test: Divide & Conquer - 4 - Question 4

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

Detailed Solution for Test: Divide & Conquer - 4 - Question 4

The data can be sorted using external sorting which uses merging technique. This can be done as follows:

1. Divide the data into 10 groups each of size 100.

2. Sort each group and write them to disk.

3. Load 10 items from each group into main memory.

4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen.

5. Loop step #4 until all items are not outputted. The step 3-5 is called as merging technique.

Test: Divide & Conquer - 4 - Question 5

A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

Detailed Solution for Test: Divide & Conquer - 4 - Question 5

The recurrence tree for merge sort will have height Log(n). And O(n2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be O (n2 log n).

Test: Divide & Conquer - 4 - Question 6

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

Detailed Solution for Test: Divide & Conquer - 4 - Question 6

The insertion sort will take θ(n) time when input array is already sorted.

Test: Divide & Conquer - 4 - Question 7

Which of the following sorting algorithms has the lowest worst-case complexity?

Detailed Solution for Test: Divide & Conquer - 4 - Question 7

Worst case complexities for the above sorting algorithms are as follows: Merge Sort — nLogn Bubble Sort — n^2 Quick Sort — n^2 Selection Sort — n^2

Test: Divide & Conquer - 4 - Question 8

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

Detailed Solution for Test: Divide & Conquer - 4 - Question 8

Time complexity of merge sort is θ(nLogn)

c*64Log64 is 30
c*64*6 is 30
c is 5/64

For time 6 minutes

5/64*nLogn = 6*60

nLogn = 72*64 = 512 * 9

n = 512. 

Test: Divide & Conquer - 4 - Question 9

What is the best sorting algorithm to use for the elements in array are more than 1 million in general?

Detailed Solution for Test: Divide & Conquer - 4 - Question 9

Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(nLogn). The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice. Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays. Quick Sort is also tail recursive, therefore tail call optimizations is done.

Test: Divide & Conquer - 4 - Question 10

Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be

Detailed Solution for Test: Divide & Conquer - 4 - Question 10

To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case. Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first. The reason for picking smallest two items is to carry minimum items for repetition in merging. So, option (D) is correct.

Test: Divide & Conquer - 4 - Question 11

Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?

Detailed Solution for Test: Divide & Conquer - 4 - Question 11

In Insertion sort if the array is already sorted then it takes O(n) and if it is reverse sorted then it takes O(n2) to sort the array. In Quick sort, if the array is already sorted or if it is reverse sorted then it takes O(n2).The best and worst case performance of Selection is O(n2) only. But if the array is already sorted then less swaps take place. In merge sort, time complexity is O(nlogn) for all the cases and performance is affected least on the the order of input sequence. So, option (A) is correct.

Test: Divide & Conquer - 4 - Question 12

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:

Detailed Solution for Test: Divide & Conquer - 4 - Question 12

Multiplications can be minimized using following order for evaluation of the given expression. p(x) = a0 + x(a1 + x(a2 + a3x))

Test: Divide & Conquer - 4 - Question 13

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?

Detailed Solution for Test: Divide & Conquer - 4 - Question 13

We can calculate power using divide and conquer in O(Logn) time.

Test: Divide & Conquer - 4 - Question 14

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?

Detailed Solution for Test: Divide & Conquer - 4 - Question 14

When Divide and Conquer is used to find the minimum-maximum element in an array, Recurrence relation for the number of comparisons is
T(n) = 2T(n/2) + 2 where 2 is for comparing the minimums as well the maximums of the left and right subarrays
On solving, T(n) = 1.5n - 2.
While doing linear scan, it would take 2*(n-1) comparisons in the worst case to find both minimum as well maximum in one pass.

Test: Divide & Conquer - 4 - Question 15

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

Detailed Solution for Test: Divide & Conquer - 4 - Question 15

Since, given array is almost sorted in ascending order, so Insertion sort will give its best case with time complexity of order O(n).

Information about Test: Divide & Conquer - 4 Page
In this test you can find the Exam questions for Test: Divide & Conquer - 4 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Divide & Conquer - 4, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)