The algorithm-design tag has no wiki summary.
20
votes
4answers
756 views
What is the novelty in MapReduce?
A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1]
The name is ...
12
votes
1answer
158 views
Efficiently selecting the median and elements to its left and right
Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.
Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.
A Software Company wants to hire ...
9
votes
2answers
399 views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
6
votes
1answer
112 views
Preprocess an array for counting an element in a slice (reduction to RMQ?)
Given an array $a_1,\ldots,a_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ ...
4
votes
1answer
59 views
How partitioning in map-reduce work?
Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the ...
3
votes
1answer
85 views
Can bottom-up architectures be effectively programmed in top-down paradigms?
The subsumption architecture, proposed by Rodney Brooks in 1986, is a "bottom-up" approach, in which robots are designed using simple hierarchical models. These models build upon and subsume the ...
0
votes
0answers
40 views
Shortest path in unipathic graph [duplicate]
Possible Duplicate:
Find shortest paths in a weighed unipathic graph
A directed graph $G = (V,E)$ is unipathic if for any two vertices $u,v \in V$ there is at most one simple path from ...
-1
votes
1answer
50 views
How to repeat a mapreduce process? [closed]
How can I repeat the map and reduce process and feed the output of reduce into map function (in the next round)?
My second question is how to define a global variable with is accessible among all map ...
