Questions tagged [divide-and-conquer]

The tag has no usage guidance.

88 questions
Filter by
Sorted by
Tagged with
23 views

...
26 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 ...
37 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. <...
66 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 ...
26 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 ...
148 views

How to understand the recurrence relation and time-complexity of StoogeSort?

I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the ...
61 views

Divide and conquer algorithm to find points beneath certain (x, y) coordinates

Let's say you have a bunch of points on a cartesian plane. For a few of these points you would like to find how many of the other points lie within their (x, y) coordinate, see below for an example: ...
470 views

Difference between sequential and parallel divide and conquer

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy In divide and conquer, we ...
300 views

$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

I'm having trouble making an algorithm to fit these specs: Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves. Reading the leaves from left to right makes a sequence of integers (...
25 views

How would be a query where its operators are NOT worth to execute in parallel?

I would like to have an example of a query for database or a dataflow program in spark (or any stream processing system) that is not worth to parallelize at least one of its operators. The insigth ...
103 views

How to write recurrence relation for backtracking problem?

I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that. Recurrence ...
145 views

Tennis Tournament Divide and Conquer for arbitrary number of players

I'm struggling with a divide and conquer algorithm for the Tennis Tournament (or Round Robin tournament). I can successfully build a timetable if $N$ (number of players) is $2^k=N$, but Brassard-...
33 views

Divide and Conquer Algorithm to calculate $a^n$

I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$. So for example, using the Java language pattern, the algorithm will be ...
1k views

Strassen algorithm for matrix multiplication complexity analysis

I see everywhere that the recursive equation for the complexity of Strassen alg is: $$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me. The parameter $n$ is supposed to be the size of the ...
112 views

Applications of divide-and-conquer outside of merge sort and quicksort [closed]

What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
22 views

Power of 2 assumption in Divide and conquer [duplicate]

Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
982 views

Complexity of finding a majority element

I was given a question that is stated that; Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection ...