Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

0
votes
0answers
21 views

Designing an algorithm for drawing circles on a webpage

Say I have a webpage with infinite scroll. The content of the webpage is just circles. The circles are all different sizes. I want to fit as many circles as possible in the available space (which will ...
0
votes
0answers
28 views

Trouble Convincing Myself Algorithm Correctness

I'm having a tough time convincing myself right when coming up for some solutions to medium/hard leetcode.com problems. Take the following question for example. ...
0
votes
0answers
115 views

Forward/Backward Recursion

What is meant by Forward, Backward Recursion? When are they used? Plus, are they (specifically) related to dynamic programming? Also, is there any relationship between them and tail/non-tail ...
2
votes
1answer
46 views

Avoiding correlated values and reduced collision resistance in multiple hash states

I need to design a hash function that fits this criteria: Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system) Produces an n-bit hash digest, ...
2
votes
0answers
31 views

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 ...
1
vote
1answer
45 views

Develop a winning strategy for a game

Okay so I've been going crazy about this problem I was given. It is as follows: Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed ...
1
vote
3answers
115 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 ...
1
vote
1answer
50 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 ...
1
vote
0answers
130 views

Non-deterministic Turing Machine recognizing a context-free Language

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS ...
4
votes
1answer
675 views

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 ...
0
votes
0answers
146 views

Implementing supplies in Coin change problem

I started an algorithm course in C two months ago, for the last weeks I've been trying to solve this problem , i ran out of time but I cannot find an acceptable solution. Basically It's a coin change ...
0
votes
0answers
26 views

Need help improving running time for a scheduling algorithm

The problem is as follows: You have a set S of shifts that are guaranteed to cover a full day. What is the minimum number of shifts needed such that someone is always working. I don't care about ...
0
votes
0answers
19 views

How was the division by restoring method algorithm designed?

I am just curious to know how did the computer scientists design the division by restoring method algorithm? How did they get the idea of designing this algorithm and found out that division can be ...
3
votes
1answer
104 views

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 ...
3
votes
0answers
32 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 ...
1
vote
1answer
49 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://...
3
votes
2answers
322 views

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 ...
1
vote
1answer
20 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 ...
3
votes
1answer
42 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-...
1
vote
3answers
252 views

Finding longest balanced parentheses using $n$ smaller strings

Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the ...
14
votes
2answers
192 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) ...
-2
votes
1answer
124 views

improve the running time

How can I use divide and conquer to improve the running time of this algorithm? input: A sorted array of length n output: the # of elements such that abs(A[i]) <= k
0
votes
0answers
17 views

Without sound synthesis, what is a good way of making a program that plays guitar notes from an array of stored sounds?

Without sound synthesis, what is a good way of making a program that plays guitar notes from an array of stored sounds? What I have in mind is to make note as a function of vibration speed such as N (...
1
vote
3answers
93 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 [...
1
vote
0answers
291 views

Designing bidirectional search algorithm

Write down the algorithm for bidirectional search, in pseudo-code. Assume that each search will be a breadth-first search, and that the forward and backward searches takes turns expanding a node at a ...
4
votes
1answer
192 views

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 ...
-2
votes
1answer
67 views

finding a & b in an array that a+b = x, for a given integer x [closed]

I want to get an algorithm with $\theta(nlogn)$ time complexity that search for two elements in an array of integers, which their sum is equal to $x$ such that x is an integer and $n$ is array size.
1
vote
1answer
90 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 ...
0
votes
2answers
342 views

Find all rational roots of a polynomial equation

I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest ...
1
vote
2answers
262 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 ...
2
votes
2answers
399 views

Algorithm and proof for combining a list of node connections into groups of nodes efficiently

My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a ...
3
votes
3answers
110 views

Why is reduction mostly associated with proving hardness?

Reduction is a powerful problem solving technique that is helpful in solving problems in terms of the solution to other problems, it can also be used for complexity analysis. Why does most of the ...
0
votes
1answer
1k views

Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
1
vote
0answers
582 views

Josephus Problem - A faster Solution

I came through Josephus problem a little while ago. Problem is stated as follows : "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
1
vote
1answer
73 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 ...
8
votes
1answer
102 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
98 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
187 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}...
3
votes
1answer
266 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
70 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
136 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 ...
30
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
318 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
48 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, ...
7
votes
1answer
195 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
116 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
653 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
78 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
189 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 change/...
4
votes
1answer
1k 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 ...