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.
141
questions
0
votes
1
answer
24
views
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.
Any subarray array[start, end] ...
- 1
1
vote
1
answer
42
views
product of every difference
Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $
$$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$
Best approach I can ...
- 105
0
votes
1
answer
58
views
Substitution method for the upper bound of a recurrence without an explicit base case
Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence:
$$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{...
- 113
1
vote
2
answers
63
views
Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)
The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows:
**Algorithmic recurrences
[...] A recurrence is algorithmic, if for every sufficiently large ...
- 113
0
votes
0
answers
381
views
How to generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices?
the question is as follows:
"Generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices for which n is not necessarily an exact power of 2. Give a recurrence describing its running time. ...
0
votes
1
answer
87
views
What recurrence describes the time complexity of this algorithm?
The problem is as follows:
The input is an array $A$ of $n$ natural numbers such that:
(1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
- 103
1
vote
1
answer
48
views
Minimum amount of parties containing round tables for everyone to meet each other
So the problem is: There is a group of n people that want to meet each other and everyone is divided into pairs, so everyone has a partner that they know. Now there will be parties at which they can ...
- 25
0
votes
0
answers
288
views
Divide and conquer problem
Problem:
Given a set of n intervals I = [a1, b1],[a2, b2], . . .[an, bn]. Here ai < bi for all i = 1
to n. Devise a Divide and Conquer algorithm to compute the length of the biggest
overlap between ...
- 1
0
votes
1
answer
351
views
Finding majority element in $\mathcal{O}(nlogn)$ time
I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time.
I thought that in order to make ...
- 225
0
votes
1
answer
145
views
Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?
Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third ...
- 305
1
vote
2
answers
3k
views
Closest pair of points in 3D
My professor mentioned that if we already know the divide and conquer algorithm for the closest pair of points in 2 dimensions it's easy to think of a similar algorithm for the 3 dimensions. But I am ...
- 47
0
votes
1
answer
133
views
In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?
Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?
- 101
1
vote
1
answer
86
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 ...
- 11
0
votes
0
answers
95
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
1
vote
1
answer
88
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 ...
- 11
8
votes
5
answers
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 ...
- 83
0
votes
1
answer
26
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 ...
user139614
3
votes
1
answer
304
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 ...
- 289
0
votes
0
answers
176
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
0
votes
0
answers
35
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 ...
- 101
2
votes
0
answers
129
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
0
votes
1
answer
32
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
-1
votes
3
answers
638
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 ...
- 250
0
votes
0
answers
105
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 ...
- 31
1
vote
1
answer
94
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
3
votes
3
answers
139
views
Algorithms question: Largest contiguous subset selection
Q. Given two arrays, $A$ and $B$, of equal length, find the largest possible contiguous subset of indices $[i,j]$ such that $\max(A[i: j]) < \min(B[i: j])$.
Example: $A = [10, 21, 5, 1, 3], B = [3, ...
- 31
1
vote
1
answer
631
views
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
- 11
1
vote
2
answers
84
views
Minimal element in logarithmic time
Suppose $A$ is an array of distinct natural numbers. We call an element $A[i]$ minimal if it's less than both the element before and after it (if any). Present a worst-case $O(\log n)$ algorithm for ...
- 411
0
votes
1
answer
325
views
Multiplying two integers by dividing each into 3 parts
Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
- 101
3
votes
3
answers
1k
views
Clarification on the algorithm for finding a majority element
Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani,
Question 2.23. I'm ...
- 39
2
votes
1
answer
82
views
Calculate the number of "count inversions" of sub arrays
Recently, I encountered the following problem:
Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
0
votes
0
answers
67
views
Tangled cable - divide and conquer
Tangled cable: Let's have a long cable, from both ends of which protrudes n wires. Each wire at the left end is connected to just one at the other end and we want to find out which one. To do this, we ...
- 125
0
votes
1
answer
189
views
Multiplication of polynomials in value representation as done for Fast Fourier Transform
I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
- 659
0
votes
1
answer
810
views
A visitor at a political convention with n delegates
So I have been asked to specifically construct a divide and conquer algorithm for the question:
"You are a visitor at a political convention with n delegates; each delegate is a ...
- 27
0
votes
1
answer
179
views
Divide and conquer problem:sequence of integers (with possible repetitions)
I was trying to solve this problem.
Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$...
- 13
1
vote
1
answer
187
views
Divide and conquer algorithm for a gas station problem
I never heard about this variation of the gas station problem. The statement is as follows:
There is just one road connecting the n+1 cities c0, …, cn
consecutively. You want to go from c0 to cn ...
- 117
1
vote
1
answer
552
views
Can the maximum single sell profit by divide and conquer be O(n)?
The single sell profit problem is:
Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day.
There is a solution ...
- 121
3
votes
1
answer
179
views
Justifying a claim in the proof of the master theorem
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.
My argument is as follows:
Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
- 133
1
vote
1
answer
192
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 ...
- 117
1
vote
1
answer
102
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
0
votes
1
answer
87
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 ...
2
votes
1
answer
89
views
Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem
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
166
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 ...
- 111
0
votes
1
answer
23
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
95
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
129
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 ...
- 134
1
vote
1
answer
349
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 ...
- 133
0
votes
0
answers
84
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 ...
- 105
1
vote
1
answer
363
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 ...
- 13
0
votes
1
answer
92
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 ...
- 23