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

Questions tagged [algorithm-design]

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

3
votes
1answer
155 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
0
votes
0answers
30 views

Iterative Backtracking Method to Recursive Method

I have the following algorithm as a solution to a maze given the maze as a graph, the point of entry and the point of exit. I am attempting to transform this method into it's recursive equivalent. <...
1
vote
1answer
48 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 ...
0
votes
0answers
29 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
163 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
52 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
34 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
47 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
116 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
51 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
167 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
678 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
179 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 ...
3
votes
1answer
126 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
35 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
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://...
3
votes
2answers
434 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
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 ...
3
votes
1answer
49 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
356 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
197 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
126 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
95 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
398 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
273 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
129 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
452 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
263 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
441 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
114 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
698 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
75 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
111 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
109 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
222 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}...
4
votes
1answer
287 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
71 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
141 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
343 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
198 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
687 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
79 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
191 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 ...