The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
46 views

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

Whilst I was reading CLRS I came across this: When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends ...
-1
votes
0answers
45 views

Recursive Algorithm design for finding the permutation of a string

Recently I am reading about induction and found that recursion and induction are the sides of the same coin. For example induction states that: $$ R_{n} = R_{n-1} + n$$ i.e. the nth solution can be ...
6
votes
1answer
68 views

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

I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of ...
4
votes
1answer
40 views

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

The usual bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & ...
1
vote
1answer
106 views

How to improve the binomial algorithm?

Good evening! I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form: $$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose ...
3
votes
1answer
168 views

Hash-Table in Practice

I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number ...
-2
votes
3answers
54 views

Find pairs in an array that when multiplied to each other gives you sum x

So this is the pseudo code I came up with but the run time is very slow. Is there a way to write this code to get it in terms of O(n)? First for loop (starts at 0) grabs the first value of the array ...
2
votes
1answer
97 views

Could my algorithm be considered Divide-and-Conquer?

So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n. I recognize that my version ...
22
votes
4answers
3k views

What is dynamic programming about?

Sorry in advance if this question sounds dumb... As far as I know, building an algorithm using dynamic programming works this way: express the problem as a recurrence relation; implement the ...
5
votes
2answers
195 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
40 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
122 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
104 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
401 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
63 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
183 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
953 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 ...
55
votes
4answers
14k 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
120 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 ...
10
votes
2answers
4k 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 ...
11
votes
1answer
277 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$ ...
13
votes
1answer
189 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 ...