# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

11,593 questions
Filter by
Sorted by
Tagged with
14 views

### Tricky Algorithm for Filling a Matrix

I have a list of products ordered in priority, I need to put them in a fridge . The fridge have a set of shelves and each shelf has a set of facings. So we can represent the fridge with a matrix. The ...
13 views

### Subgraphs of DAG minimizing overlap

Given a DAG, it has a number of 'source' nodes - nodes whose in-degree is zero. Each source node has a set of nodes reachable from it. I would like to partition the source nodes into $k$ disjoint ...
• 111
32 views

### Optimization of resources allocation

Simplified problem: Let's say we sell chicken. There are an order for today for 10 pieces from KFC that requires chicken to be good for at least 1 month and an order for tomorrow for 5 pieces from ...
1 vote
54 views

### Can one theoretically prove one version of algorithm is more efficient without running the code?

When I am learning through my CS courses, a question that aroused in my head , that is: How to theoretically/mathematically show that an algorithm is more efficient than the other? Preferably even ...
34 views

### Champions League 36 team algorithm

Does anybody know exactly how the algorithm works that made the new draw for Champions League? Wikipedia says: The 36 teams were manually drawn and then automated software digitally drew their eight ...
• 259
1 vote
58 views

### When is an algorithm "equal" to another?

I have two algorithms $P, Q$ for solving the same problem (a decision problem on sequences in $R^n$) and I want to decide if they differ in any meaningful way. The following describes the constraints: ...
14 views

### Best algorithm for sportstrainer-software

What is the best algorithm for my case? I have one tennis-trainer, which has same weekly timeslots available for his students. His timeslots are x hour a day. Say mo-fr 6-9 PM saturday and sunday 10 ...
109 views

### Is it possible to efficiently maintain a directed graph where nodes unreachable from the root are deleted?

I have an infinite set of possible nodes $V$ and a "root node" $r \in V$. I would like to maintain a directed graph with the invariant that all nodes in the graph are reachable from $r$. ...
• 185
37 views

### Efficient Algorithm to Count Permutations of Boss Fights with Divisibility Constraints in an RPG Game

I'm trying to find an efficient algorithm to calculate the amount of permutations for this problem. I've only slightly simplified the problem to be easier to read. But the original problem, is Problem ...
• 330
1 vote
32 views

### Longest non-decreasing contiguous subsequence with at most one substitution

Is there any algorithm that can count the length of the longest non-decreasing contiguous subsequence with at most one substitution? For example, given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the ...
32 views

### Stable roommate problem (Stability in Seating Arrangements)

The Seating Arrangement Problem (SOP) is a specific variant of the Stable Roommates Problem (SRP) that I have defined. In the SRP, pairs of individuals are seated at two-person tables, whereas in the ...
1 vote
29 views

### For a matrix in a row-echelon form, what's a good algorithm to find the free variables?

Suppose I have a reduced row echelon form of a matrix for linear equations. The pivots from the corresponding Gaussian elimination are available. For example, in  \begin{pmatrix} 1 & 0 & 0 \\...
1 vote
49 views

### An Interesting Puzzle on the Sequence of Positive Integers

There are $n$ positive integers on the blackboard. Each time two numbers are erased, and the absolute value of their difference is written on the blackboard. Finally, there is only one number left on ...
11 views

• 21
18 views

### Optimization with a minimal, unreliable dataset

I'm attempting to make an optimization algorithm for machine alignment that uses piezoelectric motors to work. Essentially, I gather the net movement of my motors on two axes and the resulting ...
566 views

### What does the perfect chess algorithm look like?

Say we have an infinitely powerful computer playing chess. This computer can tell which moves lead to a win/draw/loss with best play. Obviously we want to pick a winning move if available, or a ...
23 views

### Algorithm to compute the Kruskal’s Tree function

Im talking about the tree function, the famous function whose value TREE(3) is enormous. I know it is computable. Given that the function definition is rather simple, does there exist an algorithm of ...
1 vote
49 views

### Version of SSSP

Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function. Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes....
114 views

### Proof of correctness for optimal solution for sorted two-sum

I have been solving the problem of two sum with a sorted array, which can described as follows: Given a sorted array arr sorted in non-decreasing order and a ...
1 vote
80 views

### Reorder a Binary Heap to have the smallest elements in one half in linear time

Is there a known algorithm that can reorder a binary heap of size $N$ so that after the reordering we still have a valid binary heap the first half of the input ($\frac{N}{2}$ elements) are all ...
1 vote
63 views

### Accessing out of bounds indexes on an array in C

I am trying to figure out how to apply the Sobel edge detection for a BMP image, which is a 2D array of BYTE values. When multiplying a pixel by the GX or GY kernel, if the pixel is on the edge of the ...
• 31
53 views

### Proof of O(m log* n) time complexity of Union-Find - Is wikipedia proof wrong?

On wikipedia (https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Proof_of_O(m_log*_n)_time_complexity_of_Union-Find), they prove that the amortized time for any m Find or Union operations on a ...
44 views

### Computing the number of digits in power tower

Consider the sequence $a_1=1,a_2=2^1,a_3=3^{2^1},\cdots,a_{n+1}=n^{a_n}.$ Is it possible to algorithmically find out the number of digits of $a_n$ without actually computing it? For a single power ...
• 130
1 vote
75 views

### Transform any string into the shortest coherent/unique numeric identifiant

Is there some algorithm that can transform any string input (of any length) into a shortest possible coherent/unique numeric identifiant. By "coherent", I mean that the same input will ...
• 111
1 vote
29 views

### Independent Vertex Cover

We know that finding minimum size vertex cover is hard (NP-hard). Same hold for connected vertex cover. But what about finding minimum size independent vertex cover?
• 138
65 views

### Algorithms that are better than brute force

Is there a mathematical explanation for why problems have algorithms that are better than brute force? It feels like we have to take advantage of some type of order that could help us identify ...
1 vote
37 views

### Best Search Algorithim

In Microsoft Power Bi there are formulas that can be used in visualizations called measures. These measures can be used within the formulas of other measures. As a result, a measure can have a complex ...
1 vote
98 views

### Fast data structure for disjoint intervals

Over the years I've worked on a few applications that needed to model time intervals that are disjoint. For example, there's some kind of equipment available and time slots are booked out. For a data ...
• 61
105 views

### Polynomial time algorithms for graphs and cycles

For a given undirected graph $G$ , let $c(G)$ denote the length of the longest cycle in $G$ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
• 61
1 vote
31 views

### Livout analysis of control flow graph of a program

I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc ...
• 111
54 views

### Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
50 views

### Decomposing a general polygon into simple ones

This is a question about splitting a very general kind of polygon into a list of simple polygons. Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit ...
• 161
2k views

### Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
• 151