# 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<A<\dots <A[n]$, $B>B>\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, ...
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 ...
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$ ...
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 ...
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-...
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: ...
130 views

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

I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem: We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $... 0 votes 1 answer 139 views ### Sum weighted nodes between nodes in a DAG efficiently Suppose we have a directed acyclic graph$G=(V,E)$, such that all vertices have a addible weight, e.g. there is a function$weight: V \to \mathbb{R} $. Moreover two vertices$v,w \in V$are given and ... 0 votes 1 answer 22 views ### How to represent a recurrence that increments by one at each tree level? I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ... 1 vote 1 answer 68 views ### Runtime of Divide and Conquer Flavored Bogo Sort Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en.... 0 votes 2 answers 73 views ### "Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency? For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So ... 1 vote 1 answer 195 views ### CLRS closest-pair$L_m$distances I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following: We can define the distance between two points in ways other than euclidean. In the ... 0 votes 0 answers 82 views ### Simple Divide and conquer proof Suppose a simple program is reading messages from a distributed cluster. The cluster has 3 partitions, and the program has three readers that are assigned one partition each (The setup will always be ... 1 vote 1 answer 218 views ### Two peaks finding algorithm We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than O(N), maybe ... 0 votes 1 answer 88 views ### Divide and Conquer a problem into a sub-problem to solve it efficiently Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the ... -4 votes 1 answer 94 views ### How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5 Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well. A substitution rule describes how to take a sequence of ... 1 vote 1 answer 311 views ### Converting a greedy algorithm to a dynamic programming algorithm Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be: First, find a maximum indpendent set of ... 3 votes 2 answers 550 views ### Spotting the difference between two arrays using divide-and-conquer Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index. For ... 2 votes 0 answers 396 views ### Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate] From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$... 2 votes 1 answer 83 views ### Can we apply the Master Theorem to the following recurrence? Our recurrence is$$ T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if$n>1$} \\ 1 & \text{if$n=1.$} \end{cases}$$I have identified$a = 1 > 0$, and$b = 2 > 1$... 0 votes 0 answers 63 views ### How to find running time complexity of divide and conquer method without Master Theorem I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of$T(n) = aT(\frac{n}{b}) + n^clog^k(n)\$ The reason behind it has to do with drawing a tree ... 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