Search results for divide-and-conquer / GATE Overflow for GATE CSE

3 votes

1 answer

1

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 28
You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$ ... of the best divide-and-conquer algorithm? $\Theta(\log n)$ $\Theta(n \log n)$ $\Theta(n)$ $\Theta\left(n^{2}\right)$

You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$” bit-array. This means that for some (unknown) in...

GO Classes

546 views

GO Classes asked Jan 21

1 votes

1 answer

2

Made Easy Test Series 2024
Which of the following statement(s) is/are true? (a) Quicksort and merge sort are both examples of divide and conquer algorithms. (b) If we randomly choose a pivot element each time, quicksort will always terminate in time $O(n log n).$ (c) For every fixed ... in time $O(1)$, quicksort would have worst case complexity $O(n log n)$. plese give answer and explain it why ?

Which of the following statement(s) is/are true?(a) Quicksort and merge sort are both examples of divide and conquer algorithms.(b) If we randomly choose a pivot element ...

Ray Tomlinson

881 views

Ray Tomlinson asked Aug 9, 2023

0 votes

0 answers

3

Made Easy Workbook

Huzaifa0111

169 views

Huzaifa0111 asked Aug 27, 2023

0 votes

1 answer

4

Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given by f(n) = Θ(n^c). The Master Theorem classifies this into different cases based on the value of c in relation to log_b(a). Could you explain the intuition and reasoning behind these classifications?

Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given b...

dhruba

456 views

dhruba asked May 29, 2023

1 votes

1 answer

5

Divide and conquer
How To Solve This Using Divide And Conquer Suppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Divide & conquer method. What is the divide & conquer recurrence, that would arise for the problem. 1. T(n) = 4T(n/2) + O(1) 2. T(n) = 2T(n/2) + O(n) 3. T(n) = 4T(n/2) + O(n^2) 4. T(n) = 4T(n/2) + O(n)

How To Solve This Using Divide And ConquerSuppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Di...

[ Jiren ]

495 views

[ Jiren ] asked Aug 28, 2022

0 votes

0 answers

6

Best Open Video Playlist for Algorithm design techniques: Divide‐and‐Conquer Topic | Algorithm
Please list out the best free available video playlist for Algorithm design techniques: Divide-and-Conquer from Algorithm as an answer here (only one playlist per answer). We'll then select the best ... more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Algorithm design techniques: Divide‐and‐Conquer from Algorithm as an answer here (only one playlist per ans...

makhdoom ghaya

217 views

makhdoom ghaya asked Aug 17, 2022

0 votes

3 answers

7

Merge Sort Doubt
what is the recurrence relation for merge sort?

what is the recurrence relation for merge sort?

aditi19

1.2k views

aditi19 asked Oct 6, 2018

4 votes

1 answer

8

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 19
You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$ ... complexity of best divide and conquer algorithm? $\Theta(\log n)$ $\Theta(n \log n)$ $\Theta(n)$ $\Theta\left(n^{2}\right)$

You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$” bit-array. This means that for some (unknown) in...

GO Classes

249 views

GO Classes asked Jun 13, 2022

0 votes

3 answers

9

Test by Bikram | Mock GATE | Test 3 | Question: 23
Partitioning and Merging are the two main parts of $Quick Sort$. Which of the following is TRUE? Partitioning is the key step while Merging is trivial. Partitioning is trivial while Merging is the key step. Both Partitioning and Merging are trivial. Both Partitioning and Merging are key steps.

Partitioning and Merging are the two main parts of $Quick Sort$. Which of the following is TRUE? Partitioning is the key step while Merging is trivial. Partitioning...

Bikram

444 views

Bikram asked Feb 9, 2017

0 votes

3 answers

10

QUICK SORT- SELF DOUBT
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n)

In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexit...

ajaysoni1924

3.6k views

ajaysoni1924 asked Sep 2, 2019

1 votes

1 answer

11

Self doubts
T(n)=T(n/5)+T(7n/10)+an a: constant what will be the time complexity of the above recurrence relation?? Please share the approach for this kind of recurrence relation

T(n)=T(n/5)+T(7n/10)+ana: constantwhat will be the time complexity of the above recurrence relation??Please share the approach for this kind of recurrence relation

lalitver10

613 views

lalitver10 asked Jan 4, 2022

0 votes

0 answers

12

#selfDoubt
Consider all the elements of an array is same and choosing pivot such a way that divides array into two equal parts. Then will it behave like QuickSort best case or worst case?

Consider all the elements of an array is same and choosing pivot such a way that divides array into two equal parts. Then will it behave like QuickSort best case or worst...

BHOJARAM

522 views

BHOJARAM asked Dec 17, 2021

1 votes

4 answers

13

NIELIT 2016 DEC Scientist B (IT) - Section B: 52
Find the odd one out Merge Sort TVSP Problem Knapsack Problem OBST Problem

Find the odd one outMerge SortTVSP ProblemKnapsack ProblemOBST Problem

admin

3.2k views

admin asked Mar 31, 2020

6 votes

5 answers

14

NIELIT 2017 DEC Scientific Assistant A - Section B: 39
Merge sort uses : Divide-and-conquer Backtracking Heuristic approach Greedy approach

Merge sort uses :Divide-and-conquerBacktrackingHeuristic approachGreedy approach

admin

1.6k views

admin asked Mar 31, 2020

1 votes

1 answer

15

NIELIT Scientific Assistant A 2020 November: 63
What is the product of following matrix using Strassen's matrix multiplication algorithm? $ A=\begin {bmatrix} 1&3\\ 5 &7 \end{bmatrix} \;\;\;\;\;\; B=\begin {bmatrix} 8&4\\ 6 &2 \end{bmatrix} $ $C_{11}=80; C_{12}=07;C_{21}=15;C_{22}=34$ ... $C_{11}=15; C_{12}=07;C_{21}=80;C_{22}=34$ $C_{11}=26; C_{12}=10;C_{21}=82;C_{22}=34$

What is the product of following matrix using Strassen’s matrix multiplication algorithm?$$ A=\begin {bmatrix} 1&3\\ 5 &7 \end{bmatrix} \;\;\;\;\;\; B=\begin {b...

gatecse

546 views

gatecse asked Dec 9, 2020

7 votes

1 answer

16

CMI2013-B-04
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.

You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two ...

go_editor

940 views

go_editor asked May 23, 2016

1 votes

1 answer

17

Test series
Consider a set of 156 elements to find minimum and maximum elements in the given set, the minimum number of comparisons required is___? You have given an array of 512 elements,minimum number of comparisons required to find out second largest element among all will be___? 230 & 517 229 & 516 231 & 518 232 & 519

Consider a set of 156 elements to find minimum and maximum elements in the given set, the minimum number of comparisons required is___? You have given an array of 512 ele...

vinay9427

625 views

vinay9427 asked Jan 5, 2018

3 votes

0 answers

18

GeeksForGeeks
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 ... complexity using Divide and Conquer. A O(n) B O(nLogn) C O(Logn) D O(n2) Correct answer is B. O(nLogn) How?

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 nai...

Rishav Kumar Singh

6.8k views

Rishav Kumar Singh asked Jul 27, 2018

1 votes

1 answer

19

No of multiplications

santhoshdevulapally

818 views

santhoshdevulapally asked Dec 15, 2016

3 votes

5 answers

20

#Divide and conquer
Given 2 sorted arrays each of n-elements and distinct. How much time it will take to find middle element of union array? (a) O(1) (b) O(log n) (c) O(n) (d) None of these

Given 2 sorted arrays each of n-elements and distinct. How much time it will take to find middle element of union array?(a) O(1)(b) O(log n)(c) O(n)(d) None of these

ayushigupta

3.1k views

ayushigupta asked Oct 11, 2016

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true