# Questions tagged [divide-and-conquer]

The tag has no usage guidance.

97 questions
Filter by
Sorted by
Tagged with
32 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 ...
77 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 ...
34 views

### Prove that if you pair arbitrarily pair up the elements of an array A of size n to get n/2 pairs,

then you discard pairs of unequal elements and keep just one from the pairs of matching elements. Then the resulting collection will have a majority if and only if A had a majority, i.e. there exists ...
42 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 ...
68 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 ...
67 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 ...
9 views

70 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 ...
222 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 ...
340 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? ...
963 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 ...
2k 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 ...
666 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 ...
3k 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 ...
501 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 ...
186 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 ...
136 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
544 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 ...
91 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 ...
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 ...