# Questions tagged [divide-and-conquer]

Divide-and-conquer is an algorithmic technique in which a problem is divided into smaller subproblems, whose solutions are combined to a solution of the original problem. Classical examples include mergesort, quicksort, and FFT.

132 questions
Filter by
Sorted by
Tagged with
37 views

### $O(n \log n)$ Algorithm for first Train Problem

On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
45 views

### Modification on Boyer Moore Algorithm to find an element that occurs more than n/3 times

Given an array of numbers with length $n=3^k$, we try to find an element that occurs more than $\frac{n}{3}$ times. So work as follow: We divide the array into 3 parts of equal length. Find ...
1 vote
48 views

### Envyless location using divide and conquer

We have a cake of length $n$ and we have two arrays $A$ and $B$ of size $n$. The two arrays have order like below. $A[0]<A[1]<\dots <A[n]$, $B[0]>B[1]>\dots >B[n]$. We define a ...
2k views

### Divide and Conquer to identify a knight from n people

So I am doing an exercise in which there are $n$ people who are either knight or rogue, more than $\frac{n}{2}$ are knights. You are a princess and would like to marry a knight and do not want to ...
18 views

### Termination condition for max of array using divide and conuqer approach

I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
23 views

### Why doesn't Karatsuba multiplication break numbers into word size blocks?

So under the WORD RAM model of computation, the word size w is at least log of the input size and arithmetic operations on words take constant time. So rather than dividing an n bit number into bits, ...
• 83
28 views

### How to find the second most closest pair of points modifying the Divide and Conquer?

I know the Divide and conquer approach for the finding the closest pair of points and the proof of correctness. Can we modify it in such a way so that , we can find the 2nd most closest pair. I am ...
• 157
28 views

### Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
154 views

### Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
97 views

### Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
• 101
30 views

### Closest pairs of points with conquer without divide approach

In an algorithm where I have to search for the pair of points in a plain, with the smallest distance: suppose that we want to use a "Divide and Conquer" approach. Is it possible to make it ...
40 views

### What are some examples of overlapping subproblems that don't have an optimal substructure thereby we cannot solve it using dynamic programming?

I believe problems like quicksort and other divide-and-conquer are problems that have optimal substructure but do no have any overlapping subproblems. I hope I'm correct here. But I'm unable to think ...
• 121
28 views

### Recursive decomposition if a sequence can be parsed in both directions

Given a sequence/string of values and an algorithm that can process said sequence in both directions and obtain the same result - does it follow that the problem can in fact be decomposed in a divide-...
• 163
86 views

### Find element with at least $\frac{n}{2}$ repeats in an array

I saw this question on my college "Design of Algorithms" exam but I could not solve it: Given an array $A[1..n]$ of integers. find an element which is repeated at least $\frac{n}{2}$ times ...
77 views

### Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
1 vote
69 views

### Is this divide-and-conquer algorithm O(n)?

Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline: ...
• 178
130 views

• 133
1 vote
101 views

### Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$

Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is ...
• 107
1 vote
70 views

### Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$

Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a ...
• 202
40 views

### Finding the base case for T(n) = T(n - a) + T(a) + cn

I was solving the recurrence using Recursion tree method: $$T(n) = T(n - a) + T(a) + cn$$ When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the ...
80 views

1 vote
46 views

### How to solve 2 variable recursion?

T(m,n) = T(m-1,n) + T(floor(m/2), n-1) Base conditions T(m,n) = 1 when n = 0 T(m,n) = 0 when m < n Edited: Below is the code for which I want to know the time complexity in terms of m and n. <...
1 vote
99 views

### divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the ...
• 11