# Tag Info

Accepted

### What is dynamic programming about?

Dynamic programming gives you a way to think about algorithm design. This is often very helpful. Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code. ...
• 143k

### What is dynamic programming about?

Your understanding of dynamic programming is correct (afaik), and your question is justified. I think the additional design space we get from the kind of recurrences we call "dynamic programming" can ...
• 71.1k
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.2k
Accepted

### Kernels in parameterized complexity

Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter. The goal of kernelization ...
• 13.3k
Accepted

### Finding an element in a sorted array with at most three queries to larger elements

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$ If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can ...
• 251
Accepted

### Hash-Table in Practice

SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the ...
• 270k

### What is dynamic programming about?

Dynamic Programming allows you to trade memory for computation time. Consider the classic example, Fibonacci. Fibonacci is defined by the recurrence $Fib(n)=Fib(n-1)+Fib(n-2)$. If you solve using ...
• 608

### What is dynamic programming about?

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of ...
• 577
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 ...
• 270k

### 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 ...
• 270k
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 ...
• 34.8k
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 ...
• 143k

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

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

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

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

### Do compression tables exist and where are they used?

The big advantage of Lempel-Ziv-style compression is that it creates its own dictionary on the fly and tailors it to the data. Therefore, they are general-purpose compression algorithms which can be ...
• 71.1k
Accepted

### How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps

A naive solution could be that each general first launch a binary counter in its row and counts the current time until $k\log(k)$ steps and then run the FSSP. To do this you just need to detect the ...
• 156
Accepted

### Why isnt node checked for nil value in start when transplanting binary tree

If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to ...
• 270k

### How to improve the binomial algorithm?

The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which ...
• 270k

### Could my algorithm be considered Divide-and-Conquer?

TL;DR Divide and concur doesn't have any rigorous definition. So any argument you make for or against will be just an emotional argument. The situation is made worse by the fact that the task ...
• 1,358

### 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 ...

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

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

### 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 ...
• 6,998

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

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