Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [divide-and-conquer]

The tag has no usage guidance.

6
votes
2answers
356 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
61 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
15 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
74 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
46 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
41 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
170 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
84 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
60 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
112 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 ...
0
votes
0answers
26 views

How to implement a divide and conquest algorithm?

I'm taking a course on Algorithm design and I'm having a hard time with one of the practice problems given to us to work on. Below is the question, and then my attempted solution. You have ...
1
vote
0answers
18 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
896 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
47 views
1
vote
1answer
66 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
32 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
129 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
98 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
307 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
592 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
410 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
296 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
139 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
126 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
389 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 ...
3
votes
0answers
57 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
441 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
211 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
136 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
146 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
536 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) ...
4
votes
1answer
333 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
452 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
47 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
72 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
516 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
290 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 ...
2
votes
2answers
790 views

Finding integer square root for large integers [find asymptotic time complexity]

So I found this tasks in one book I am practicing from where it says: "Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time ...
2
votes
3answers
284 views

Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

The questions is to find the running time $T(n)$ of the following function: $$T(n)=3\cdot T(n/2) + n \tag{1}$$ I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
1
vote
1answer
54 views

How do I find running time for the following divide and conquer problem?

Question is to find the runtime $T(n)$ of following problem by solving the recurrence. $T(n)=16\cdot T(\frac{n}{4}) + n!$. I went through the following theory. If the recurrence relation is of the ...
1
vote
0answers
196 views

Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

Here is a divide and conquer approach for finding minimum and maximum elements in an array. ...
1
vote
2answers
209 views

How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
4
votes
3answers
962 views

Categorization of Binary search as Divide and Conquer

Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.
0
votes
1answer
404 views

Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?

why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire ...
2
votes
1answer
141 views

Could my algorithm be considered Divide-and-Conquer?

So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n. I recognize that my version ...
3
votes
1answer
712 views

Understanding Closest Pair Algorithm (CLRS)

I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise 33.4-2 they say 33.4-2 Show that it ...
0
votes
1answer
126 views

Help needed with lesson on recursion

I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example". I understood the beginning and I even made a program that calculates $X$ to the power of $N$ ...
1
vote
1answer
421 views

Divide and Conquer 3D Convex Hull [closed]

http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf This is a divide and conquer algorithm for computing the convex hull in 3 dimensions. I am having trouble understanding the merge step, which is ...