48
I can not help but think: this is divide & conquer, plain and simple!
M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input. It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations. ...
29
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. Memoization is a relatively simple idea, but the best ideas often are!
Dynamic programming gives you a structured way to think about the running time of your ...
22
EDIT (March 2014) I should say that I have since worked more on algorithms for MapReduce-type models of computation, and I feel like I was being overly negative. The Divide-Compress-Conquer technique I talk about below is surprisingly versatile, and can be the basis of algorithms which I think are non-trivial and interesting.
Let me offer an answer that ...
11
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 best be seen in comparison to other schemata of recursive approaches.
Let's pretend our inputs are arrays $A[1..n]$ for the sake of highlighting the concepts.
...
11
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 solve $f(x)=0$, where your search space is $\mathbb{R}$, most algorithms work under several assumptions on $f$, e.g. continuity (there is no algorithm which can ...
9
Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is ...
8
If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function
does not have side effects and
does only depend on its parameters (i.e. not on some state). ...
8
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 is (at least) two-fold. We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the ...
8
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 check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $...
7
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 values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the ...
6
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 this recursion, you end up doing $O(2^n)$ calls to $Fib(\cdot)$, since the recursion tree is a binary tree with height $n$.
Instead, you want to calculate $Fib(2)$...
6
I fully agree with you. From a conceptual perspective, there is nothing really new: Map/Reduce was originally known in Parallel Computing as a data-flow programming model. However, from a practical point of view, Map/Reduce as proposed by Google and with the subsequent open-source implementations has also fueled Cloud Computing and is now quite popular for ...
6
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 a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued ...
5
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 neighboring elements. Finding the two neighboring elements can be done in $O(\lg n)$ time.
You'll also need to be able to append to the end of the sequence and ...
5
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 case of $d$ constraints (in your case, $d = n$) many natural algorithms give a $d+1$-approximation.
5
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 highest average score now? Do you need to sort the array?
4
Since $k$ is constant, we can store the count of each element in the range $0..m$ for $0\leq m \lt n$ in $0..n$ in $O(nk) = O(n)$ time and space. The primary observation is that you can make a two-dimensional array count[pos][elem] = occurences of 'elem' in the indices 0..pos in $O(nk)$ time, then query ranges by finding the difference in $i,j$ indices in ...
4
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 position $n$. What is the value of $A[n]$?
What can you say about $\ln(x)$ in relation to $n$?
Can you find the correct $n$ quickly? Does it help that $A$ is sorted?
3
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 problem to linear programming, to a max-flow problem, or to another well-studied problem. This is using reductions for solving problems.
Any particular textbook ...
3
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 equivalence classes, such that the candidate solutions in each class are indistinguishable in some sense.
Let me take as an example the problem of finding the number of ...
3
I think you've hit the nail on the head with your comment.
It's not true that in any functional language maps can be parallelized - the language must be pure. (I believe Haskell is the only vaguely mainstream purely functional language. Lisp, OCaml and Scala are all non-pure.)
We've known about the benefits of pure code since even before timesharing, when ...
3
I would like to generalize this into a more common scenario. This I believe makes sense since the particulars of subsumption architecture are perhaps not a primary aspect in the question (and the same problems occur in non-robotic fields as well).
In general software archtitecture there is a bi-directional approach, or multi-paradigm approach, as in the ...
3
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 this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each ...
3
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) &= 1 - P(\text{all are } Y)\\
& = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\[0.5em]
& \...
3
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 looks like the following.
algorithm quicksort(A, lo, hi):
if lo < hi then
p ← pivot(A, lo, hi)
left, right ← three-way-partition(A, p, lo, ...
2
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 value of $k$ and compute $k\log(k)$ in less than $k\log(k)$ steps: sending a signal back and forth toward the other end while incrementing a binary counter gives ...
2
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 accomplished by this algorithm doesn't need D&C. So, the answer is "probably".
Long version
One scenario where it would make sense to use D&C in ...
2
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 used without having to keep dictionaries in sync; all you need for
decoding is the encoded file and the algorithm.
If you fix a dictionary, this is going to ...
2
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 incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient ...
2
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 worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:
$v_{2k},v_{2k+1}$
$\vdots$
$v_2, ...
Only top voted, non community-wiki answers of a minimum length are eligible
