Questions tagged [divide-and-conquer]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
18 views

FFT miscalculation(polynomial) [closed]

I am trying to find where I am doing a mistake as i am not getting the requested answer. I hope that i got the algorithm correctly for fft of polynomials. given: $p(x)=2x^3-x^2+4x+1$. so writing it ...
1
vote
0answers
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. <...
1
vote
0answers
58 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 ...
0
votes
1answer
19 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 ...
3
votes
1answer
97 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 ...
1
vote
0answers
40 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: ...
3
votes
1answer
372 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 ...
1
vote
1answer
224 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 (...
0
votes
0answers
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 ...
1
vote
1answer
73 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 ...
1
vote
0answers
123 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-...
0
votes
1answer
28 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 ...
8
votes
3answers
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 ...
-1
votes
1answer
95 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?
3
votes
0answers
19 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 ...
0
votes
1answer
756 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 ...
0
votes
1answer
123 views

Max subarray product

Is it possible to solve the max sub-array product problem using divide and conquer? Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) ...
2
votes
2answers
90 views

Determine when Strassen's algorithm for matrix multiplication is better than regular MM

I'm trying to find out how to determine the size of the matrices $n$ such that Strassen's algorithm for matrix multiplication is better than the regular algorithm. I know that Strassen's algorithm is $...
0
votes
2answers
396 views

Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes

Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each ...
3
votes
2answers
88 views

Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)

I'm working on some lecture notes and wondered if there was a good example algorithm for the recurrence equation $$T(n) = T(n/2) + n$$ I know that I can do selection in this running time, but that ...
2
votes
1answer
102 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
1
vote
2answers
380 views

Strassen Algorithm for Unusal Matrices

The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81). However, this algorithm is applied for the matrices which are ...
1
vote
0answers
20 views

Applications of the (cumulated) ruler function in algorithm analysis

In Chapter 2 (Page 76) of the book "An Introduction to the Analysis of Algorithms (2nd edition)" by Robert Sedgewick and Philippe Flajolet, the authors introduce two functions: Definition Given an ...
-1
votes
2answers
2k views

Finding missing number in an unsorted array

You are given an unsorted array of all the integers in the range $0$ to $n = 2^k -1$ except for one integer, called the missing number. Find a divide and conquer algorithm to find the missing ...
1
vote
1answer
76 views
1
vote
1answer
69 views

Finding a (Small-Big-Medium) subsequence

Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{...
0
votes
0answers
55 views

Practical example for recurrence relation of merge sort with more than 2 sublists

I couldn't wrap my head around for finding an example for the following recurrence. $T(n) = a T(n/b) + f(n)$ where $a \neq b$ and $b > 1$ If we divide n elements with b, it should give us a ...
0
votes
0answers
164 views

Understanding time complexity for kth minimum in CLRS

In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm ...
2
votes
1answer
161 views

Splitting the array in the median-of-median solution for $k$th smallest element problem

Regarding the median of medians solution to the $k$th smallest element in an array, why does the algorithm split the array into subarrays of length $n/5$, where $n$ is the length of the initial array? ...
1
vote
1answer
642 views

Karatsuba Multiplication with n/3 division of large number

I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts. Now I'm trying to understand how the multiplication ...
0
votes
0answers
1k views

Divide and conquer algorithm for finding majority element of array [duplicate]

I'm trying to solve the problem for finding majority element of given array. I made two attempts to solve the problem, but seems that both have something wrong in them. First one relies on the logic ...
5
votes
0answers
478 views

Obtaining max set interval intersection using Divide and Conquer

Given an array with $n>2$ elements of integer sets intervals, where each set is represented as a tuple of the form $(inf, sup)$ (with $inf $ ínfimum and $sup $ maximum of the set), we want to ...
-1
votes
1answer
2k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
0
votes
2answers
440 views

An algorithm to find highest lines in at least one point [duplicate]

Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$ $$a_i x_0 + b_i \ge ...
2
votes
2answers
168 views

Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$

The following problem is from CLRS (31.1-13, Page 933, 3rd edition): Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if ...
-2
votes
1answer
130 views

improve the running time

How can I use divide and conquer to improve the running time of this algorithm? input: A sorted array of length n output: the # of elements such that abs(A[i]) <= k
3
votes
1answer
519 views

Algorithm in O(logn)

I have a project where I should write the following algorithm : Let an integer function $f\colon\{1,2,3,\ldots,n\} \to \mathbb{Z}$ be monotone and suppose that $f(1) > 0$ and $f(n) < 0$. We ...
2
votes
0answers
76 views

Counting inversions with index constraint

I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$ $a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis. The question is how to find a algorithm that is ...
0
votes
1answer
1k views

Divide and Conquer majority element algorithm

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array) I came up with this linear divide and conquer algorithm, but I'm ...
0
votes
1answer
714 views

How can we design an efficient divide-and-conquer algorithm for constructing a round-robin tournament?

Background and main question I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia. One of the applications problems (...
3
votes
1answer
291 views

Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log_2(...
3
votes
1answer
189 views

Number of “hamiltonian tours” from upper left to lower left corner of a grid graph?

I got the following as an interview question: Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the ...
0
votes
2answers
219 views

Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?

In O(n log k) time? The input is the array of integers n, and some integer k. The output should be a boolean for whether or not the following condition holds for all elements: any two elements within ...
1
vote
2answers
603 views

How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?

This looks like a typical divide and conquer algorithm, but with a few tricky parts. It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) ...
3
votes
1answer
352 views

Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both. Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ ...
0
votes
0answers
512 views

Maximum Subarray Problem Algorithm that uses divide and conquer but runs in linear time

I am trying to design an algorithm that computes the largest (by sum) contiguous subarray of an array of size n that uses a divide and conquer approach, but runs in linear time. The standard divide ...
1
vote
2answers
76 views

Find a recurrence relation for merging of sublists of an array

There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list. My Approach Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$,...
0
votes
1answer
125 views

Algorithm for converting (coordinates + reach radius) data to directed graph

I am trying to find a solution better than O(n2) for the following problem: There are N points on a 2-D plane (N $\le$ 106), with integer coordinates between -105 and 105. Each point has an ...
-1
votes
1answer
628 views

Proof of correctness of divide and conquer clique algorithm

I have the following divide and conquer algorithm that finds a clique in an undirected graph $G = (V, E)$: ...
1
vote
1answer
372 views

Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution

I have to solve this using the substitution method. Floor functions cannot be skipped. IH: Assume that $T(k) \geq ck\log(k) $ for all $k \leq n$, where c is a constant. IS: Must prove $T(k) \geq ...