11
votes
Accepted
Deformation of algorithms
There is no general way to do this. The "space of algorithms" is not a nice one, with a natural metric or other nice properties, unlike e.g. the real numbers. Note that even in the case of trying to ...
- 13.6k
7
votes
Accepted
Implementation of QuickSort to handle duplicates
The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot.
In pseudocode, the algorithm ...
- 39.2k
4
votes
Accepted
"Searching and sorting" algorithm to find the natural logarithim of a number?
Suppose you have an array $A = [e^0, e^1, e^2, \dots]$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $x$.
You find this value at ...
- 14k
4
votes
Accepted
The awkward status of Mersenne Twister
Substantive reasons: Some PRNGs intended for statistical simulations are faster than cryptographic PRNGs. Yes, cryptographic PRNGs are pretty fast, but some statistical ones are even faster, and are ...
D.W.♦
- 169k
4
votes
The awkward status of Mersenne Twister
On top of what D.W. said, scientific reproducibility is absolutely a real concern. I personally know a researcher who spent a couple of days ensuring that their PRNG was bit-for-bit accurate to an ...
- 25k
3
votes
Finding one of 2/3 of all array elements in constant expected time
One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:
$$\begin{align}
P(\text{at least }1\; X) &...
- 4,543
2
votes
Accepted
Avoiding correlated values and reduced collision resistance in multiple hash states
MurmurHash2_x86_64 (aka MurmurHash64B) works as follows: it computes a 32-bit value $h_1$ based on bytes 0-3, 8-11, 16-19, 24-27, etc. of the input; it computes a 32-bit value $h_2$ based on bytes 4-7,...
D.W.♦
- 169k
2
votes
Accepted
Longest substrings of common length with the same parity
Here is an $O(n\log^2 n)$ solution.
The first step is to reduce to an easier problem:
Given $x_1,\ldots,x_n \in \{0,1\}$, determine, for all $0 \leq i \leq n$ and $b \in \{0,1\}$, whether there is ...
- 281k
2
votes
Accepted
Given an array of size n, create a sub array with given conditions using dynamic programming
In other words, the procedure produces two subsequences of the given array such that
the only shared element between the two is their first elements
one of them is non-decreasing.
one of them is non-...
- 39.2k
2
votes
Lexicographic permutation list
You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is ...
- 31
2
votes
Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?
The answer—as with many such applied numerical problems—is, "sure, but you have to decide which of the published heuristics you want to use". Your real problem will be the embarrassment of riches as ...
- 3,583
2
votes
Multi-Path Length Minimization
You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.
Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to ...
- 5,519
2
votes
Accepted
Finding max value algorithm with subset comparison
Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:
If one of the sets is bigger than the other, we say that its sum is larger.
If the two sets ...
- 281k
2
votes
Accepted
Finding lost bottle (algorithm problem)
This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it.
You ...
- 2,552
2
votes
Accepted
Queue for two types using 2 queues?
Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first.
I'd go with ...
- 416
2
votes
How to design algorithm
You start with simple algorithms, implement them successfully, and then you learn how to do more and more complex things. You need experience, and some built-in cleverness. Without both you will fail.
...
- 32.6k
2
votes
3-colouring with a bounded amount of colors
If the graph has $k$ vertices, any color cannot be used more than $k$ times, so I'm not sure I see the problem here.
If the limitation is an input of the problem, then the problem becomes harder, not ...
- 18.5k
2
votes
Accepted
How can I find 2 median values of an array which is an union of 2 arrays in O(log n)?
The general idea of the algorithm is pretty straightforward, it basically boils down to the dichotomic search idea by cutting your problem in half at each step. But the parity of the length of the ...
- 146
2
votes
Greedy solution for minimum weight where all tasks are allocated
Imagine one of your customers is a company with ten departments. They are huge, so the weight and the time for their job are huge. If you split their order into ten departments then each has one tenth ...
- 32.6k
1
vote
Accepted
An algorithm to evaluate the strength of Quiz Participants
I suspect this is primarily a statistics and data modelling question, rather than a question about computer science.
If you have a model $f$ for predicting the score of a team from the strengths of ...
D.W.♦
- 169k
1
vote
Fast algorithm for computing minimal closure of a set of sets under intersection?
There is no polynomial-time algorithm. The output can potentially be exponentially large, so any algorithm will have inputs on which it must take exponential time. For instance, if $s_i=\{1,2,\cdots,...
D.W.♦
- 169k
1
vote
Fingerprint functions for set equality checks?
A Bloom filter has this property. Use the Bloom filter itself as the fingerprint. The merge operation can be implemented as bitwise OR.
For multisets, see https://crypto.stackexchange.com/q/54544/...
D.W.♦
- 169k
1
vote
Beginning Algorithm Design and Proving
If you really want to study algorithms, start by looking at a few courses on algorithms at reputable universities, check what textbooks they offer, and start reading one of those textbooks. Or, pick ...
D.W.♦
- 169k
1
vote
What are the reasons for solution assumptions behind the longest subsequence problem?
Congratulation for solving a popular problem independently with a perspective that is rarely seen.
The choice between "ending at $i$" and "starting at $i$" can be dismissed as ...
- 39.2k
1
vote
no of times partion is called in quick sort, assuming array is always halved
The number of times the partition algorithm is called does not actually depend on where the array is partitioned (asymptotically).
To count the number of partitions you just need to count the number ...
- 6,297
1
vote
Accepted
Algorithm for sorting within windows
What you require is the lexicographic ordering. Let me describe this.
Suppose the speeches have two attributes. The first one is "speaker's name" and the second one is the "length"....
- 6,297
1
vote
Accepted
Partition the indices of 2d array to minimize sum of sub-matrices
First we note that with $\mathcal{O}(n^2)$ precomputation, where we store the 'prefix sums', we can find the sum of all the elements in a given square subgrid in $\mathcal{O}(1)$ time.
Now, let $DP[i]...
- 460
1
vote
Accepted
Maximum number of similar groups of a given size that can be made from a given array
The function
$$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) =
\begin{cases}
1; &\text{if there is a solution of size $k$,}\\
0; &\text{otherwise}
\end{cases}
$$
is monoton, since if there is no ...
- 4,964
1
vote
design cache system using queuing theory
You first need to establish the access speed of the cache, depending on the cache size (usually larger cache -> slower speed, because of physics). You also need to determine the energy consumption of ...
- 32.6k
1
vote
Accepted
Greedy algorithm for even item distribution
It looks like a greedy algorithm cannot do it alone.
Here is an approach based on binary search.
Suppose we have a subroutine to determine that if it is possible to have a chocolate supply of $s$ ...
- 39.2k
Only top scored, non community-wiki answers of a minimum length are eligible