Dark Mode

Recent questions tagged divide-and-conquer

1 vote

1 answer

1

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)

[ Jiren ] asked in Algorithms Aug 28, 2022

193 views

0 votes

0 answers

2

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 playlist ... more likely to be selected as best. For the full list of selected videos please see here

makhdoom ghaya asked in Study Resources Aug 18, 2022

by makhdoom ghaya

70 views

1 vote

1 answer

3

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

lalitver10 asked in Algorithms Jan 4, 2022

437 views

0 votes

0 answers

4

#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?

BHOJARAM asked in Algorithms Dec 17, 2021

275 views

1 vote

1 answer

5

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$

gatecse asked in Algorithms Dec 9, 2020

192 views

5 votes

5 answers

6

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

Lakshman Patel RJIT asked in Algorithms Mar 31, 2020

by Lakshman Patel RJIT

1.0k views

1 vote

4 answers

7

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

Lakshman Patel RJIT asked in Algorithms Mar 31, 2020

by Lakshman Patel RJIT

2.5k views

0 votes

3 answers

8

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)

ajaysoni1924 asked in Algorithms Sep 2, 2019

by ajaysoni1924

2.8k views

0 votes

0 answers

9

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

akash.dinkar12 asked in Algorithms Apr 5, 2019

by akash.dinkar12

304 views

0 votes

0 answers

10

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?

akash.dinkar12 asked in Algorithms Apr 5, 2019

by akash.dinkar12

193 views

0 votes

0 answers

11

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?

akash.dinkar12 asked in Algorithms Apr 5, 2019

by akash.dinkar12

245 views

0 votes

0 answers

12

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.

akash.dinkar12 asked in Algorithms Apr 5, 2019

by akash.dinkar12

213 views

0 votes

1 answer

13

UPPCL AE 2018:12
Given below are some famous algorithms and some algorithm design paradigms ... $\text{1-(c), 2-(b), 3-(a), 4-(b)}$

Lakshman Patel RJIT asked in Algorithms Jan 5, 2019

by Lakshman Patel RJIT

194 views

0 votes

0 answers

14

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

Satbir asked in Algorithms Dec 24, 2018

by Satbir

385 views

0 votes

0 answers

15

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

Amit puri asked in Algorithms Nov 22, 2018

203 views

0 votes

2 answers

16

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

aditi19 asked in Algorithms Oct 6, 2018

969 views

0 votes

2 answers

17

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

Rustam Ali asked in Algorithms Sep 5, 2018

1.2k views

0 votes

1 answer

18

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

manvi_agarwal asked in Algorithms Sep 3, 2018

by manvi_agarwal

834 views

1 vote

2 answers

19

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

manvi_agarwal asked in Algorithms Sep 3, 2018

by manvi_agarwal

442 views

1 vote

0 answers

20

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)

rohan.1737 asked in Algorithms Aug 16, 2018

321 views

0 votes

1 answer

21

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

Sambhrant Maurya asked in Algorithms Aug 7, 2018

by Sambhrant Maurya

173 views

3 votes

1 answer

22

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?

Sambhrant Maurya asked in Algorithms Aug 7, 2018

by Sambhrant Maurya

1.4k views

1 vote

2 answers

23

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.

meethunjadhav asked in Algorithms Jul 30, 2018

by meethunjadhav

590 views

1 vote

1 answer

24

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.

meethunjadhav asked in Algorithms Jul 30, 2018

by meethunjadhav

250 views

3 votes

0 answers

25

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?

Rishav Kumar Singh asked in Algorithms Jul 27, 2018

by Rishav Kumar Singh

5.7k views

0 votes

1 answer

26

ACE Algorithms volume 2 Divede and Conquer Q 11
Given two sorted double linked list L1 and L2 of n elements each, which of the following are true? (A) L1 and L2 can be merged into single sorted list in Θ(n) time. (B) L1 and L2 can be merged into single sorted list in Θ(1) time. ( ... merged into single sorted list in Θ(nlogn) time. (D) L1 and L2 can be merged into single sorted list in Θ(n2) time.

JAYKISHAN asked in Algorithms Jul 5, 2018

552 views

2 votes

0 answers

27

Algorithm
You have an array A with n JPEG images some of which are identical. You can check if two objects are equal but you cannot compare them in any other way-i.e. you can check A[i] == A[j] and A[i] != A[j], but comparisons such as A[i] < A[j] ... of its elements are equal to each other. Use divide and conquer to come up with an O(n logn ) algorithm to determine if A has a majority element.

Kushagra Chatterjee asked in Algorithms May 2, 2018

by Kushagra Chatterjee

608 views

0 votes

1 answer

28

IIT MS Question
find T(n) = T(n-1)*T(n-2), given T(1) = a and T(2) = b

bittu asked in Algorithms Apr 25, 2018

by bittu

939 views

Page:

1
2
3
next »

Recent questions tagged divide-and-conquer