Questions tagged [algorithms]
Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).
11,772 questions
-3
votes
0
answers
63
views
Is it valid to compare solving vs checking NP problems using average time per logical step?
I’ve been exploring a measurement approach for NP and NP-complete problems based on average time per logical step.
I define:
...
2
votes
1
answer
41
views
Construct AM–GM Proofs of Muirhead Inequalities (From Majorization to Explicit Weighted AM–GM Chains)
Motivation
I am experimenting with symbolic implementations of algorithms that, given a majorization relation between two exponent vectors, automatically generate Olympiad-style inequality proofs ...
- 6,087
1
vote
1
answer
139
views
Random points in a sphere
I have to randomly put $N$ points in a sphere of radius $R$ in a way that the distance of every point from the other points is greater than or equal to $r_0$. Is there an algorithm to solve this ...
- 10.8k
8
votes
3
answers
298
views
Why is there no Euclidean Algorithm for the least common multiple (lcm)?
The greatest common divisor (gcd) of two integers $a$ and $b$ can be computed with the Euclidean Algorithm.
With the gcd known, one can compute the least common multiple (lcm) via the formula $\mathrm{...
- 741
0
votes
1
answer
59
views
Find square of format A+n*B [duplicate]
Is there any better way than a brute force scan to find a square (or possible the smallest square) of format $A+n*B$, where $A$ and $B$ are some fixed constant integers? (I know that that is ...
- 101
4
votes
1
answer
277
views
Winnability of an urn-ball game with restricted two-urn moves
My question is about a certain combinatorial game. The game works as follows. We have $n$ urns, each of which contains $m$ balls, where $m$ and $n$ are positive and satisfy $m < n$. A move consists ...
- 728
0
votes
0
answers
23
views
Max–min assignment on a DAG when nodes have candidate values with compatibility constraints
I have a DAG where every node has a (usually small) set of candidate integers. A candidate a is compatible with b if (a | b) or (b | a). For every root I want to choose one candidate per node to ...
- 81
3
votes
2
answers
404
views
Coloring a graph with K-colors
Given a graph, I wish to try and color it with the minimum number of colors (0,1...k).
Each 2 connected vertices must have different colors.
I proposed the following algorithm - Initialize an array of ...
- 33
0
votes
0
answers
32
views
Determiniing max roundness of number in an array
I'm trying to solve the following Codeforces question (https://codeforces.com/contest/837/problem/D), and I feel like I have a solution that's very close but is probably still over the time constraint....
2
votes
0
answers
43
views
Minimum number of sign flips for prefix sum positivity
Problem: (from the Indian ZIO exam, $2021$, problem $2$)
We are given a list of integers of length $n$. What is the minimum number of elements whose sign you need to flip such that every prefix sum ...
- 33
0
votes
0
answers
10
views
Fast Algorithms for Generating Simplicial $n$-Spheres on $k$ Vertices
As stated in title, I wonder know if there exists any algorithms for generating simplicial $n$-spheres on $k$ vertices.
The motivation for seeking such algorithms comes from my goal to compute the ...
- 377
1
vote
0
answers
35
views
Constructive method for expressing arbitrary matrix permutations using cyclic row/column shifts
I am unsure which category this question best fits into, so I apologize in advance if this is not the ideal place to ask.
It is known (see for example:
Do cyclic permutations of rows and column ...
- 11
0
votes
0
answers
38
views
Complexit of LSB extraction in Discrete Log Problem w.r.t. a prime number
Consider the discrete Log Problem w.r.t. prime $p$. Given $b, p, r$ find $x$ where: $b^x\bmod p=r$.
Q: What is the complexity of calculating the Least Significant Bit of $x$ in the worst case?
Note: ...
- 325
1
vote
1
answer
80
views
Find for two given Similar Matrices $A,B$ a matrix $S$ conjugating them, ie satisfying $A=SBS^{-1}$ constructively
Let $K$ be any field. Two square matrices $A,B \in \text{Mat}_n(K)$ are called similar (denote it my $\sim$) iff there exists a $S \in \text{GL}_n(K)$ such that $A=SBS^{-1}$, so in this form an ...
- 10.1k
1
vote
1
answer
72
views
What is a worst case graph for this streaming algorithm?
Consider the following streaming algorithm for maximum matching in a weighted graph.
...
- 779