# Tag Info

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.4k
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 ...
• 39k

### A general algorithm for greedy algorithms

There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with ...
• 277k

### Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score

You are on a good path, but seem to be confused for no reason. After step 2 you have created an array with average scores. This is a worst case O(N) size array. What is the complexity of finding the ...
• 506
Accepted

### Data structure for efficient searching, when insertions and removals are only one-sided

Store the elements as a sequence, sorted by increasing timestamp. Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two ...
• 159k
Accepted

### How to give an approximation algorithm for this unusual bin packing problem?

Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the ...
• 277k

### Find all rational roots of a polynomial equation

If you only want to find all rational roots, you can simply use the rational root theorem. This theorem states that, given a polynomial $a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1x+a_0$, for any rational ...
• 8,248
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 ...
• 13.4k

### 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,511

### Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive?

Perhaps this is too broad a question for a coherent answer, so let me first try to say something about line segment intersection, at least. The main reason the sweep-line algorithm is efficient is ...
• 8,248

### Beginner help with Arrays & Complexity

Let's try to solve a simpler problem first: Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left. Now ...

### Why is reduction mostly associated with proving hardness?

Actually, people do commonly use reductions for both purposes: both for proving lower bounds, and for designing algorithms to handle a certain problem. For instance, it's very common to reduce a ...
• 159k
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 ...
• 159k

### 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 ...
• 22.1k

### Algorithm and proof for combining a list of node connections into groups of nodes efficiently

You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges. The performance of the algorithm you described is much ...
• 13.2k

### Why is reduction mostly associated with proving hardness?

The need to define reduction formally arises only when defining classes of hard problems. Consider polynomial time reducibility as an example. The same notion is used for both "positive" and "negative"...
• 277k

### Why is reduction mostly associated with proving hardness?

I've seen reduction used implicitly. A good example is the problem of finding a maximum spanning tree. In that case, you reduce the problem to the minimum spanning tree problem by multiplying all edge ...
• 61

### Counting permutations whose elements are not exactly their index ± M

Is it possible you remembered the specific details wrong or misinterpreted the question? In your description, element $a$ in position $b$ is restricted to $a-b \ne \pm M$. But if they just meant the ...
• 327

### Counting permutations whose elements are not exactly their index ± M

The first thing I would ask when given this question would be Do you want a polynomial time algorithm? and then I'd hope the answer is 'no'. I suspect that this problem is NP-hard, for the ...
• 8,248

### improve the running time

You have a sorted array of n elements. If the first element is > k then no elements have absolute value ≤ k. (Why ?) If the last element is < -k then no elements have absolute value ≤ k. (Why ?) ...
• 30k

### Beginner help with Arrays & Complexity

Just some hints that will tell you how to solve it efficiently: If you know where the first zero is, then you know what numbers to write down at all positions before and up to that zero. For example,...
• 30k

### Find all rational roots of a polynomial equation

The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The ...
• 5,951
Accepted

### Why does counting sort copy the input elements?

They do not need to do it this way, but they might have found it more elegant. Their idea is not: Put every element j in ...
• 72.4k
Accepted

### 4 Neurons to Decide 10 Digits

You could use 4 neurons to produce a 4-bit output, which then represents the digit in binary. A digit in the range 0-9 can be expressed in binary as a 4-bit number. However, classification accuracy ...
• 159k
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,...
• 159k
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 ...
• 277k
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 ...
• 277k

### 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
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-...
• 39k