Recent questions tagged divide-and-conquer

1
Merge sort uses : Divide-and-conquer Backtracking Heuristic approach Greedy approach
2
Find the odd one out Merge Sort TVSP Problem Knapsack Problem OBST Problem
3
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)
4
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 subarray of $A[1 j]$, extend the ... a maximum subarray of the form $A[i...j+1]$ inconstant time based on knowing a maximum subarray ending at index $j .$
5
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?
6
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, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?
7
Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.
8
how many terms will be computed to determine the value of C(10,8) using divide and conquer algo ? 88 89 90 91
9
what is the recurrence relation for merge sort?
10
Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )
1 vote
11
1 vote
12
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)
13
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 whether a ... are 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?
14
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 ... time complexity using Divide and Conquer. A O(n) B O(nLogn) C O(Logn) D O(n2) Correct answer is B. O(nLogn) How?
15
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. (C) L1 and L2 can be merged into single sorted list in Θ(nlogn) time. (D) L1 and L2 can be merged into single sorted list in Θ(n2) time.
16
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] are not ... half 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.
17
find T(n) = T(n-1)*T(n-2), given T(1) = a and T(2) = b
18
in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1) How to reach this type of analysis where we get to know that we have to divide n into halves?
1 vote
19
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
1 vote
20
21
22
Do we need to study the Strassens's algorithm in detail like proof or working of that algorithm or we just need to know the time complexity of the algorithm because I can't find it's explanation anywhere?
1 vote
23
I implemented maximum sub-array problem with Divide and Conquer approach in c++ and python. I got little bit of confusion in the implementation.Below are the implementations. I got different results when I change the for loop of both c++ and python code.in first I implemented something ... loop)) In first case I am getting right output i.e 43 but in 2nd I am getting 56 as the output! Please help!
24
how to apply master's method for this recurrence relation $T\left ( n \right )= {}\sqrt{n}T\left ( {\sqrt{n}} \right )+n$
1 vote
25
What is the difference between dynamic programming and divide and conquer technique,
CAN SOMEONE SOLVE THE NUMBER OF COMPARISIONS FOR COMPUTING MIN AND MAX IN AN ARRAY USING DIVIDE N CONQUER?? RECURRENCE RELATION IS $T(n) = 2 T(\frac{n}{2}) + 2$ IT SHOULD COME TO $\frac{3*n}{2} - 2$ ??