Recent questions tagged 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

537 views

GO Classes asked Jan 21

0 votes

0 answers

2

Made Easy Workbook

Huzaifa0111

167 views

Huzaifa0111 asked Aug 27, 2023

1 votes

1 answer

3

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

860 views

Ray Tomlinson asked Aug 9, 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

448 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 ]

490 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

4 votes

1 answer

7

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

245 views

GO Classes asked Jun 13, 2022

1 votes

1 answer

8

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

609 views

lalitver10 asked Jan 4, 2022

0 votes

0 answers

9

#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

515 views

BHOJARAM asked Dec 17, 2021

1 votes

1 answer

10

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

542 views

gatecse asked Dec 9, 2020

6 votes

5 answers

11

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

4 answers

12

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

0 votes

3 answers

13

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.5k views

ajaysoni1924 asked Sep 2, 2019

0 votes

0 answers

14

Cormen Edition 3 Exercise 4.1 Question 5 (Page No. 74)
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum ... the form $A[i...j+1]$ inconstant time based on knowing a maximum subarray ending at index $j .$

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the rig...

akash.dinkar12

389 views

akash.dinkar12 asked Apr 5, 2019

0 votes

0 answers

15

Cormen Edition 3 Exercise 4.1 Question 4 (Page No. 74)
Suppose we change the definition of the $maximum-subarray problem$ to allow the result to be an empty subarray, where the sum of the values of an empty subarray is $0$. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

Suppose we change the definition of the $maximum-subarray problem$ to allow the result to be an empty subarray, where the sum of the values of an empty subarray is $0$. H...

akash.dinkar12

253 views

akash.dinkar12 asked Apr 5, 2019

0 votes

0 answers

16

Cormen Edition 3 Exercise 4.1 Question 3 (Page No. 74)
Implement both the brute-force and recursive algorithms for the $maximumsubarray$ problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, ... brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?

Implement both the brute-force and recursive algorithms for the $maximumsubarray$ problem on your own computer. What problem size $n_0$ gives the crossover point at which...

akash.dinkar12

332 views

akash.dinkar12 asked Apr 5, 2019

0 votes

0 answers

17

Cormen Edition 3 Exercise 4.1 Question 2 (Page No. 74)
Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.

Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.

akash.dinkar12

294 views

akash.dinkar12 asked Apr 5, 2019

0 votes

0 answers

18

UPPCL
how many terms will be computed to determine the value of C(10,8) using divide and conquer algo ? 88 89 90 91

how many terms will be computed to determine the value of C(10,8) using divide and conquer algo ?88899091

Satbir

529 views

Satbir asked Dec 24, 2018

0 votes

0 answers

19

general
how many terms will be computed to determine the value of 10C8 using divide and conquer strategy and dynamic programming? for divide and conquer ans is 89 how to compute please explain

how many terms will be computed to determine the value of 10C8 using divide and conquer strategy and dynamic programming?for divide and conquer ans is 89 how to compute p...

Amit puri

271 views

Amit puri asked Nov 22, 2018

0 votes

3 answers

20

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

what is the recurrence relation for merge sort?

aditi19

1.1k views

aditi19 asked Oct 6, 2018

0 votes

2 answers

21

#Divide and Conquer
What is the time complexity of calculating power of an element using DAC?

What is the time complexity of calculating power of an element using DAC?

Rustam Ali

1.7k views

Rustam Ali asked Sep 5, 2018

0 votes

1 answer

22

Divide and conquer made easy
Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )

Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )

manvi_agarwal

1.0k views

manvi_agarwal asked Sep 3, 2018

1 votes

2 answers

23

Made easy , divide and conquer
https://gateoverflow.in/?qa=blob&qa_blobid=11583750777176064728 Approach please

https://gateoverflow.in/?qa=blob&qa_blobid=11583750777176064728Approach please

manvi_agarwal

672 views

manvi_agarwal asked Sep 3, 2018

1 votes

0 answers

24

WBSET 2017
A student develops a technique to multiply two 2×2 matrices. The technique requires six multiplications. The complexity of the module that combines the module is O(n2). Then the recursive equation depicting the complexity of the algorithm is (A) T(n) = 6T(n/3) + O(n2) (B) T(n) = 6T(n/2) + O(n2) (C) T(n) = 6T(2n ) + O(n2) (D) T(n) = T(n/2) + 6 O(n2)

A student develops a technique to multiplytwo 2×2 matrices. The technique requires sixmultiplications. The complexity of the module thatcombines the module is O(n2). The...

rohan.1737

481 views

rohan.1737 asked Aug 16, 2018

0 votes

1 answer

25

Ace Algorithms
If k is a positive constant, then the following divide and conquer recurrence evaluates to? T(n) = k ; n=1 T(n) = 3 T (n/2) + kn ;n>1 a)T(n)= 3kn2-kn b)T(n)=3kn log23 - 2kn c)T(n)=3knlog23 - kn d)T(n)=3kn2-2knlog23

If k is a positive constant, then the following divide and conquer recurrence evaluates to?T(n) = k ; n=1T(n) = 3 T (n/2) + kn ;n>1a)T(n)= 3kn2-knb)T(n)=3kn log23 - 2knc...

Sambhrant Maurya

402 views

Sambhrant Maurya asked Aug 7, 2018

3 votes

1 answer

26

Ace Algorithms
Leading element in an array of n elements is the element which occurs more than n/2 times in the array. a) What is the time complexity to find whether a leading element exists or not in a sorted array of n elements? b)What is the time complexity to find ... between 0 to n? c)What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?

Leading element in an array of n elements is the element which occurs more than n/2 times in the array.a) What is the time complexity to find whether a leading element ex...

Sambhrant Maurya

2.0k views

Sambhrant Maurya asked Aug 6, 2018

1 votes

2 answers

27

ACE volume 2 divide and conquer
given an array that contain only two value (0 or 1) and an insertion sort is used to sort that array, which of the following input require maximum number of comparisons ? a)111111000000 b)101010101010 c)000000111111 c)010101010101 here, ans is ... compare to each element and the move that element to specified position. then how option (a) is correct plz explain me.

given an array that contain only two value (0 or 1) and an insertion sort is used to sort that array,which of the following input require maximum number of comparisons ?a...

meethunjadhav

985 views

meethunjadhav asked Jul 30, 2018

1 votes

1 answer

28

Ace volume-2 divide and conquer method
suppose merge sort takes 2 sec to sort a set of 64 keys then how much time will take to sort a set of 512 keys? here, ans is 24 sec how it is plz explain me.

suppose merge sort takes 2 sec to sort a set of 64 keys then how much time will take to sort a set of 512 keys?here, ans is 24 sec how it is plz explain me.

meethunjadhav

434 views

meethunjadhav asked Jul 30, 2018

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