Questions tagged [divide-and-conquer]
Divide and conquer is an algorithm design paradigm based on recursion. A problem is broken down into multiple small subproblems until they are simple enough to be solved. The solutions are then combined to give a solution to the original problem.
26
questions
4
votes
1answer
82 views
Maximum sub-array sum
My code finds the maximum subarray sum and the starting and ending index of that subarray.
...
7
votes
2answers
2k views
Python program to solve the “skyline problem”
This is a Leetcode problem -
A city's skyline is the outer contour of the silhouette formed by all
the buildings in that city when viewed from a distance. Now suppose
you are given the ...
5
votes
0answers
97 views
A Parallel Processing Template for Divide & Conquer Problems
I’ve written a program for solving a problem using standard single-threaded code. However, it looks like it could be recast as a multi-threaded problem using divide & conquer. Since this is a ...
2
votes
1answer
284 views
Finding peak point in an array by using divide and conquer approach
It is to find the maximum element in an array which is first increasing and then decreasing. I've tried to write my idea by using divide and conquer approach. Is there any improvable or missing point? ...
3
votes
1answer
201 views
Checking whether given array is sorted by divide-and-conquer
I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.
...
5
votes
1answer
2k views
Closest Pair algorithm implementation in C++
I had been working on the implementation of closest pair algorithm in a 2-D plane.
My approach has been that of divide and conquer O(nlogn) :
...
2
votes
2answers
192 views
Finding the closest pair of points divide-and-conquer speed improvement
This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...
4
votes
2answers
3k views
Finding the closest pair of points divide-and-conquer
Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
3
votes
0answers
509 views
Finding the majority element in a sequence of integers in \$O(n \log n)\$
I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in \$ O(n \log n)\$. The majority element is defined as the ...
8
votes
2answers
396 views
Shortest distance for points in a plane
I was wondering how I can make this code more pythonic. More professonal-looking and more readable. The code runs perfectly fine.
...
1
vote
0answers
284 views
Merge two unsorted array of numbers into sorted array using divide and conquer
I have done an implementation of merging two unsorted array of numbers into single sorted array.
I have used the concept of divide an conquer.
The code is as follows
...
7
votes
1answer
783 views
Finding Second Largest Element in an Array
Here's my implementation using divide and conquer in C++.
What do you think of this implementation regarding running time ?
...
1
vote
0answers
515 views
Compute the minimum distance between two points in a 2-D plane
I have tried to calculate the minimum distance between the two points in a 2D plane. I have used the divide and conquer strategy to attain the complexity of n logn. ...
3
votes
1answer
1k views
Divide and conquer algorithm for max binary gaps
The codility.com free test is as follows:
A binary gap within a positive integer N is any maximal sequence of
consecutive zeros that is surrounded by ones at both ends in the
binary ...
3
votes
1answer
143 views
Implementation of binary search
I am new to the divide and conquer paradigm. I wanted to verify that there's nothing wrong with this implementation of binary search.
I ran it a few times and it does print the correct result, but I ...
-1
votes
1answer
2k views
My implementation of Karatsuba Multiplication in C++
I have recently implemented Karatsuba's multiplication algorithm in C++ for my Algorithms course. It is a very sloppy implementation because I ran out of time, yet criticism would be appreciated. I ...
6
votes
5answers
3k views
1D Peak Finder Algorithm
I'm reviewing MIT Introduction to Algorithm lectures/exercises and am trying to implement a one dimensional peak finder algorithm.
I've got a working copy but it's a bit messy and I've had to put ...
2
votes
1answer
3k views
Finding closest pair of 2D points, using divide-and-conquer
I'm learning C++ as well as algorithms. Here's my implementation of finding the closest pair problem. I tried to minimize memory by using only iterators.
And points are being read from ...
3
votes
0answers
328 views
Divide-and-conquer approach for finding the closest pair of points
This is an algorithm for finding the closest pair of points on a 2d plane by dividing the problem by half recursively, as illustrated here:
...
1
vote
2answers
219 views
Random iteration over an array using divide and conquer
I have created a utility class which allows random iteration over an array.
The idea is pretty much a divide and conquer approach.
...
2
votes
1answer
725 views
Maximum subarray problem solved with divide and conquer also for the all negative element case
Solving the maximum subarray problem with added cases of finding non maximum non contiguous subarray as well. I used divide and conquer approach and tackled the 'all negative' case by keeping a ...
4
votes
1answer
797 views
Divide and Conquer algorithm for counting inversions
I've written a program that counts the number of inversions using a Divide and Conquer algorithm, written in C++11.
...
1
vote
1answer
1k views
Monge Array - leftmost minimum for each row
This implementation is the result of solving exercise 4-6 "Monge Arrays" from the book Introduction to algorithms.
Definition of a Monge Array:
An m x n array A of real numbers is a Monge array ...
3
votes
1answer
1k views
Number to spanish word converter
This converts from a number to a Spanish word for example :
100 => cien
200 => doscientos
I used a divide-and-conquer approach:
Constants:
...
2
votes
3answers
342 views
5
votes
2answers
6k views
Maxmin algorithm implementation
I'm currently taking an algorithm course in college. To find the maximum and minimum elements in an array, I'm using a divide and conquer algorithm. Please offer suggestions for this code snippet. I ...
