Questions tagged [algorithm-design]

Questions related to general, high level, techniques for the design of algorithms.

101 questions
73
votes
4 answers

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 reminiscent of map and reduce in functional…
Raphael
  • 73,461
  • 31
  • 185
  • 415
36
votes
4 answers

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 recurrence relation either via memoization or via a bottom…
hey hey
  • 463
  • 4
  • 5
14
votes
2 answers

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 if satisfied by a recursive algorithm would…
Anonymous
  • 141
  • 1
  • 1
  • 3
14
votes
1 answer

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 exactly three coders to develop an application. For…
Jack
  • 329
  • 1
  • 5
13
votes
2 answers

Counting permutations whose elements are not exactly their index ± M

I was recently asked this problem in an algorithmic interview and failed to solve it. Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number…
Gena
  • 151
  • 4
11
votes
1 answer

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$ and $j$"? The array should be preprocessed in…
andy
  • 263
  • 1
  • 5
9
votes
1 answer

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we…
Prashin Jeevaganth
  • 297
  • 1
  • 3
  • 9
8
votes
1 answer

Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive?

A well known algorithm in computational geometry is the sweep plane algorithm. I've been trying to find if there's a general version of the sweep plane algorithm in $\mathbb{R}^n$, I don't need to implement it but I need to study how the general…
user8469759
  • 753
  • 3
  • 19
8
votes
1 answer

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 magnitude larger than what is typically used.…
Wrzlprmft
  • 245
  • 1
  • 9
7
votes
1 answer

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) \in L \Leftrightarrow (x',k') \in L$ $|x'| \leq f(k)$…
Peter W
  • 181
  • 2
6
votes
2 answers

How to Match Socks

When I do my laundry I tend to make a pile of unmatched socks, putting new socks on the top of the pile and matching off pairs if two of the same sock are near the top of the stack. Since eventually socks will get buried deep in the pile I…
Sriotchilism O'Zaic
  • 471
  • 3
  • 18
5
votes
2 answers

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 change/perturbation in a confined neighborhood of the data…
Herng Yi
  • 101
  • 4
4
votes
0 answers

Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image you can see (more or less) what I mean: The objects…
alex
  • 209
  • 2
  • 5
4
votes
1 answer

Deformation of algorithms

Has there been any attempt at a general theory to describe how an algorithm can be "deformed" to solve the problem more efficiently? For example suppose we have an algorithm (say sorting a list of numbers) which solves the problem in $O(n^2)$. Can…
tom
  • 59
  • 2
4
votes
1 answer

A general algorithm for greedy algorithms

I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general greedy algorithm. When reading these sources, I…
Eduardo J. Sanchez
  • 163
  • 6
1
2 3 4 5 6 7