The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
25 views

CPU influence in speed of a task with inefficient Algorithm [on hold]

If CPU power doubles how much will iecrease time for solving a problem? If the relationship between time and number of steps that the algorithm does be: T = 2^n i.e: A PC with 2GHz processor takes 4 ...
0
votes
2answers
58 views

Schedule two trains whose tracks overlap so they don't crash

I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve. Recently I was asked this question and did not even know what algorithmic technique to ...
1
vote
1answer
36 views

Do compression tables exist and where are they used?

Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, ...
6
votes
1answer
106 views

Kernels in parameterized complexity

Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say: The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that: $(x,k) ...
-3
votes
1answer
84 views

Hates Pepole Nice Algorithm [closed]

Some people in n groups, hates from each others. the hates relation are symmetric. (a hates b, b hates a, also). suppose we know list of all people that hates from ...
4
votes
1answer
257 views

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

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
1
vote
1answer
59 views

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

Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells ...
5
votes
2answers
181 views

Decomposing an Algorithm into Local Transformations/Perturbations

Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local ...
4
votes
1answer
687 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 ...
44
votes
4answers
13k 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 ...
3
votes
1answer
117 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 ...
9
votes
2answers
3k 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 ...
10
votes
1answer
253 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$ ...
12
votes
1answer
178 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 ...