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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 1
1 vote
1 answer
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 ...
user avatar
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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, ...
user avatar
  • 83
0 votes
0 answers
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 ...
user avatar
  • 157
0 votes
0 answers
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: ...
user avatar
  • 1
3 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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$ ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 121
0 votes
1 answer
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-...
user avatar
-1 votes
3 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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: ...
user avatar
3 votes
3 answers
130 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, ...
user avatar
1 vote
1 answer
163 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 ...
user avatar
  • 11
1 vote
2 answers
61 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 ...
user avatar
  • 377
0 votes
1 answer
94 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$, ...
user avatar
3 votes
3 answers
632 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 ...
user avatar
2 votes
1 answer
47 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 ...
user avatar
0 votes
0 answers
35 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 ...
user avatar
0 votes
1 answer
38 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 ...
user avatar
0 votes
1 answer
465 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 ...
user avatar
  • 27
0 votes
1 answer
73 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]$...
user avatar
  • 13
1 vote
1 answer
109 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 ...
user avatar
  • 117
1 vote
1 answer
189 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 ...
user avatar
  • 121
3 votes
1 answer
89 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)^{\...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 107
1 vote
1 answer
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 ...
user avatar
  • 202
0 votes
1 answer
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 ...
user avatar
2 votes
1 answer
80 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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
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....
user avatar
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 ...
user avatar
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 ...
user avatar
  • 123
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 ...
user avatar
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 ...
user avatar
  • 13
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 ...
user avatar
  • 23
-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 ...
user avatar
  • 43
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 ...
user avatar
  • 165
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 ...
user avatar
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 $$...
user avatar
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$...
user avatar
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 ...
user avatar
1 vote
0 answers
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. <...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
85 views

Geometric median of two disjoint sets of points lies on line between their respective medians

I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ...
user avatar
  • 195