# Questions tagged [algorithm-design]

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

63 questions
Filter by
Sorted by
Tagged with
16k 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!  The name is ...
4k 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 ...
203 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 ...
13k 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 ...
216 views

### 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) ...
439 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$ ...
125 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 ...
228 views

100 views

### Can a greedy algorithm have more than one subproblems to solve after making greedy choice?

For example: s = <s1 s2 s3> is my problem, I make greedy choice s2 and solve s1 and <...
37 views

### Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?

I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit ...
50 views

### Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
265 views

### Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score

Question: Suppose you are a given a csv with N lines of the form StudentID, score. Multiple lines can have same student-ID. Find the student with maximum average score I can't think of any way to ...
120 views

### Finding one of 2/3 of all array elements in constant expected time

How do I go about designing a constant time algorithm which satisfies the following I/O requirements: Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the ...
97 views

### Beginner help with Arrays & Complexity

My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right. So for example [...
2k views

### 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 ...
50 views

### 4 Neurons to Decide 10 Digits

I am trying to solve this algorithm exercises (http://neuralnetworksanddeeplearning.com/chap1.html#exercise_513527) in Michael Nielson's online book: Neural Networks and Deep Learning (http://...
315 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 2}x^{n-2}...
50 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, ...
91 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 ...
33 views

### design cache system using queuing theory

If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS & a cache size will have a count). How can one use queuing theory to ...
190 views

### Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
72 views

### How to create an algorithm when given the invariant

I am given the following invariant: Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array. I am supposed to ...
21 views

### A comparison operation for lists, based on P(a > b)

Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from ...
147 views

### Why does counting sort copy the input elements?

When I was reading about counting sort in Introduction to Algorithms for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the ...
85 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 ...
216 views