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
0
votes
0
answers
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 ...
0
votes
0
answers
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
0
votes
1
answer
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 ...
- 103
1
vote
2
answers
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 ...
-1
votes
0
answers
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
1
answer
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:
...
0
votes
0
answers
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 ...
6
votes
0
answers
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
0
votes
0
answers
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
0
answers
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 ...
0
votes
0
answers
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
0
answers
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 \\...
- 111
1
vote
0
answers
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 ...
0
votes
0
answers
11
views
Decreasing flow by $\sigma << |V|$ [duplicate]
Let $G=(V,E,c,s,t)$ a flow network where $\forall e \in E: c(e) \in \mathbb{N}$. Assume we have $n$ vertices and $m$ edges. Let $f$ a max flow in $G$. Let $e=(u,v) \in E$, and let $\sigma \in \mathbb{...
- 171
1
vote
2
answers
49
views
Finding two disjont longest possible vertical or horizontal lines in 2D matrix with non-usable cells
The problem is to find two disjont longest possible (but with equal length) horizontal or vertical lines in given 2D matrix, where some cells are excluded from use. The disjont means that any cell ...
- 113
3
votes
1
answer
111
views
Minimize sum of array after repeated replacement of numbers with their OR operation result
I participated in an algorithms contest recently, and couldn't find an answer to this problem.
The contest is over now, and am looking to see if someone might know how to solve this.
Question:
"...
- 330
0
votes
0
answers
25
views
implementing compression / compaction of t-digest
I am trying to implement t-digest. Everything is more or less straight forward, except one "little" thing - compression (compaction) of the centroids.
I ...
- 105
0
votes
0
answers
24
views
Solving a recurrence by substitution method
I am trying to solve a recurrence question using substitution method. The question looks like
But I am unable to solve it. Could you please help me to solve this question.
I assumed Let, T(m) <= ...
- 1
0
votes
0
answers
12
views
Determine height of recurrence tree
I want to solve a recurrence relation and also be able to determine the height of recurrence relation.
In case of questions that satisfy master theorem the answer in the below link seems to work fine
...
- 1
1
vote
1
answer
90
views
Why does problem F belong to PSPACE?
In the following graph, each node represents a computational problem. An arrow like A -> F indicates that there is a polynomial time Karp reduction from A to F. Observe that there could be more ...
- 13
0
votes
1
answer
30
views
Smallest sum not obtainable using a subset of elements in array greater than the minimum element
I am solving a variation of the missing coin sum problem, modified to be as follows:
You have n coins with positive integer values. What is the smallest
sum greater than the minimum coin in the array ...
- 133
4
votes
1
answer
56
views
Detecting/removing thin sections of polygons
Given a non-self-intersecting polygon made of straight segments how do you detect/trim sections of the polygon that are "thin"?
If an algorithm exists for this, then great! If not, then...
...
0
votes
1
answer
39
views
Balancing players into two teams
I'm trying to find an algorithm which would arrange ranked players into 2 teams automatically before the game starts in a balanced way.
The game has 2 teams, each team can have up to 5 players, and ...
- 103
0
votes
0
answers
50
views
Help with writing an algorithm
I'm not sure if this question fits the forum, and I should mention that I'm not a computer scientist at all—just a regular normal boy with very little coding knowledge.
But I wanted to ask if it's ...
- 1
2
votes
1
answer
171
views
NP-Hardness: Finding the Best Subtree for Hierarchical Matching in Elasticsearch
Given a graph G = (V, E) (a forest) stored in Elasticsearch and a set of requests R, where each request r in R can potentially match between 0 and V vertices in G, the task is to identify the "...
- 21
2
votes
3
answers
146
views
How to simplify $O(\log (n!))$?
I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
- 31
1
vote
1
answer
42
views
Find the number of sink nodes per source node efficiently
My task is to write a function that, given a source nodes of a graph, returns the number of sink nodes (nodes with no outgoing edges) it reaches. The only access I have is to retrieve the neighbors of ...
- 13
2
votes
1
answer
29
views
Shortest path to all nodes from a center point, repeats allowed
I'm trying to create an algorithm to figure out a path visiting every single node in a graph (undirected and unweighted) - similar to the traveling salesman problem, but I can visit a node multiple ...
- 21
2
votes
0
answers
27
views
Algorithm for maximizing the number of pairs removed from a sorted sequence under a dubling condition
Given a non-decreasing sequence of $n$ positive integers $a_1 \leq a_2 \leq \dots \leq a_n$, we are allowed to modify this sequence by performing the following operation: we select two elements $a_i, ...
- 21
0
votes
0
answers
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 ...
2
votes
4
answers
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 ...
0
votes
1
answer
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
0
answers
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....
- 171
3
votes
3
answers
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 ...
- 133
1
vote
0
answers
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 ...
- 11
1
vote
1
answer
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
0
votes
0
answers
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 ...
0
votes
1
answer
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
2
answers
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
1
answer
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
2
votes
1
answer
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 ...
- 29
1
vote
1
answer
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 ...
- 11
1
vote
0
answers
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
6
votes
0
answers
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
1
answer
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
3
votes
0
answers
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 ...
2
votes
0
answers
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
5
votes
3
answers
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
0
votes
1
answer
32
views
Which course is more beneficial for studying undergraduate computer science: Multivariable Calculus or Number Theory
I want to major in computer science for my undergraduate degree. I want to take one of the mathematics courses offered by Stanford ULO (https://ulo.stanford.edu/mathematics). I am unable to choose ...
2
votes
1
answer
34
views
Rule-Based Link Prediction for Social Network
Relevance to Site
I believe this question is suitable for the Computer Science Stack Exchange as it pertains to the implementation of a graph algorithm. According to this widely accepted answer, such ...
- 23