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.
34 questions
5
votes
3
answers
763
views
A simple checksum for java.math.BigInteger
Intro
I have a simple methods that converts the input instances of java.math.BigInteger to checksum. The checksum algorithm sums up all the digits in the input <...
- 32k
1
vote
0
answers
82
views
A parallel MSD radix sort in Java for long keys with near linear speedup
Intro
I have this implementation of a parallel MSD (most significant digit) radix sort. It runs in
$$\mathcal{O}\Bigg( \bigg(\frac{N}{P} + PB \bigg) \log_B \sigma\Bigg),$$ where \$N\$ is the length of ...
- 32k
1
vote
2
answers
724
views
Duplicate Binary Search Improvements
I'm working on an implementation of binary search (in Python) that can operate on a sorted array that may have duplicate elements.
I've written a submission that has managed to hold up against my test ...
- 111
1
vote
2
answers
317
views
Closest Pair of Points - Optimizing Code for big sets of points
I'm trying to create an algorithm that finds the closest pair of points (2D) within a set of points. I'm using a divide and conquer method which is explained here Closest Pair of Points Algorithm.
...
- 11
4
votes
1
answer
1k
views
Karatsuba's multiplication
I am working my way through an algorithms course online, and the assignment is to implement Karatsuba's multiplication algorithm. I am also trying to practice C++, so I wanted to implement it in that ...
- 165
7
votes
3
answers
2k
views
Finding the majority element in an array
A list is said to have a “majority element” if more than half of its
entries are identical. In this classical problem the goal consists of
determining whether a list a of length n has a majority ...
6
votes
4
answers
2k
views
Writing my first binary search by myself
Is there any way in which I can improve my code? I don't know if it is 100% right, and if it can be tweaked in order to be more efficient. That's why I'm posting here.
I'm open to any suggestions :)
<...
3
votes
1
answer
169
views
Divide and Conquer Password Bruteforcer
My program brute-forces a password. The password is a string composed of a key and a four digit numeric code. The key is known so we are basically brute-forcing between 0000 through to 9999
An example ...
- 247
3
votes
2
answers
176
views
Max Contiguous Subarray: Divide and Conquer
I am conversant with Kadane's Algorithm. This is just an exercise in understanding divide and conquer as a technique.
Find the maximum sum over all subarrays of a ...
- 183
4
votes
1
answer
219
views
Maximum sub-array sum
My code finds the maximum subarray sum and the starting and ending index of that subarray.
...
- 41
8
votes
2
answers
12k
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 ...
- 2,619
5
votes
0
answers
186
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 ...
- 405
2
votes
1
answer
796
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
1
answer
691
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.
...
6
votes
1
answer
4k
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) :
...
- 131