# Questions tagged [algorithms]

Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.

1,581
questions

2
votes

1
answer

85
views

### On square root modulo $2^t-1$

Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?

1
vote

1
answer

45
views

### Does Monotone (linear) convergence of iterates imply monotone (linear) convergence of function values?

I am considering a proof that would require a certain connection between convergence of iterates and corresponding function values: Consider an algorithm with iterates $\left\{{\mathbf{x}}^k\right\}_{...

12
votes

3
answers

665
views

### When does $2$ arise when using the Euclidean algorithm to compute greatest common divisors?

When using the standard Euclidean algorithm to compute the greatest common divisor of a pair of relatively prime positive integers, the integer $2$ sometimes arises and sometimes does not. For example,...

2
votes

0
answers

95
views

### Another (unique) algorithm for the A329369

Let $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \leqslant k ...

3
votes

2
answers

300
views

### Algorithm to evaluate "connectedness" of a binary matrix

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...

1
vote

0
answers

81
views

### Non-vanishing of product of zero divisors in quotients modulo $n$

This might be of practical importance and even partial answer will help.
Let $n$ be odd squarefree integer with known factorization $n=\prod p_i$
with $N$ prime factors.
Later we are not asking about ...

0
votes

0
answers

168
views

### On the integer solutions of the equation $y^2 = x^3 + n$

Let $n$ be a nonzero integer. I am interested in the integer solutions $(x, y)$ to the equation $y^2 = x^3 + n$.
Let $S$ be the set of all integer solutions $(x, y)$ to this equation.
I am wondering ...

0
votes

1
answer

150
views

### How to determine if a set is a sumset

Let $G$ be a commutative group (assume whatever you want on $G$ if needed. I am mainly interested in $G = \mathbb{Z}/n\mathbb{Z}$).
Let $k$ be a fixed integer.
Let $(a_1, \dots, a_{k^2})$ be a list of ...

0
votes

0
answers

27
views

### Solving sparse bilinear systems with a relatively large number of variables

I'm trying to solve a bilinear system of equations over a finite field. (More specifically: I'm trying to find a single solution, if one exists.) The system consists of equations of the form
$$y^T A_i ...

0
votes

3
answers

95
views

### Calculating variance-minimal perfect matchings

Question:
are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?

0
votes

0
answers

10
views

### Enumerating the directed vertex-disjoint cycle covers of digraphs

A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...

0
votes

0
answers

68
views

### Touring a sequence of convex polygons with minimal energy

There is a known problem of touring a sequence of $n$ polygons: given a starting point $s$, an ending point $t$ and a sequence of polygons $P_1,\dots,P_k$ with a total of $n$ vertices, find points $...

3
votes

0
answers

125
views

### Fast and simple algorithm for the A329369

Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\cdots,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...

2
votes

0
answers

237
views

### Least number of circles required to cover a continuous function on $[a,b]$

I asked this question on MSE here.
Given a continuous function $f :[a,b]\to\mathbb{R}$, what is the least number of closed circles with fixed radius $r$ required to cover the graph of $f$?
It is ...

2
votes

1
answer

111
views

### On a efficient algorithm for factoring bivariate polynomials modulo composite modulus assuming the solution is unique

We found and implemented in sage efficient algorithm for factoring
bivariate polynomials modulo composite modulus assuming the solution is unique up to a constant factor.
More formally let $K=\mathbb{...

1
vote

1
answer

198
views

### Correctness of the algorithm for the A329369, A347205 and related sequences

Let $a(n)$ be A347205. It is enough for us to know that
$$
a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^jk), \\
a(0) = 1
$$
Let $b(n)$ be A329369. It is enough for us to know that
$$
b(2^m(2k+1)) = \sum\...

2
votes

0
answers

168
views

### NP-hardness of a string transformation problem with k templates

Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...

0
votes

0
answers

133
views

### Questions on integer matrix multiplication

Question 1:
Given two integer matrices $A$ and $B$, and let $C$ be $AB$.
$C$ can be very big in pratice, so what is the fastest way to compute the statistical data of $C$?
For example,
$$A=\begin{...

0
votes

0
answers

44
views

### Initial guess in shifted QR algorithm

I'm comparing timings of two implementations of algorithms for the computation of Gauss-Legendre nodes.
1 - The first is a Newton algorithm to find the roots of the Gauss-Legendre polynomials. Quite ...

2
votes

0
answers

191
views

### Finding specific coefficients of product of high-dimensional Fourier series faster than FFT

I need a fast algorithm to perform a specific Fourier-type computation in my physics research. Suppose I have the following two Fourier series in three dimensions
$$
a(t_1,t_2,t_3)=\sum_{j=-n}^{n}\...

4
votes

1
answer

237
views

### Fibonacci and matrix modular exponentiation

I'm interested in a few problems that are related enough that I decided to put them all in one question.
What are the fastest known algorithms for finding large Fibonacci numbers modulo $p^k$, and ...

1
vote

1
answer

52
views

### Complexity of maximum weight-sum matching for cycle graphs

I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...

1
vote

0
answers

37
views

### Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields

Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the ...

4
votes

1
answer

164
views

### Algorithms to count perfect matchings in near planar graphs

It is well known that counting perfect matchings is tractable in planar graphs (due to Kastelyn).
I am interested in classes of (for lack of a better word) "near" planar graphs (1-planar, ...

4
votes

0
answers

41
views

### Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...

2
votes

1
answer

262
views

### Generating all possible subsets in order of sum

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...

0
votes

0
answers

37
views

### Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points

Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...

0
votes

0
answers

68
views

### What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...

0
votes

0
answers

23
views

### Building hypercubes from the bottom up

let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices.
setting
$\mathbb{H}^0 := V$, i.e. ...

1
vote

0
answers

64
views

### Algorithm to generate configurations with kissing number 12

That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...

14
votes

3
answers

2k
views

### Guaranteed correct digits of elementary expressions

Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...

1
vote

0
answers

60
views

### A small lemma on cache resets (Bloom filters in particular)

Assume a fixed set of message $D$ and an associated distribution for selecting each message $d_i$ such that the total probability $\sum_{i \in D} d_i = 1$. We create a cache with $M$ bits and $k$ ...

2
votes

0
answers

94
views

### What is the complexity / name of word search problem in linear groups?

This is a question about a search problem associated with user6976's question. Suppose we are given a finite set of elements $S \subset \mathrm{GL}_n(\mathbb{Q})$ containing inverses of all its ...

1
vote

0
answers

94
views

### Algorithms to decompose a graded module over $R[x]$, where $R$ is a PID

There is a certain class of objects, which can be thought of either as modules over a ring $R[x]$ or as functors. A few equivalent definitions are given below. The question is what computer algorithms ...

0
votes

0
answers

48
views

### Weighted matroid intersection algorithm

From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen:
...

1
vote

1
answer

104
views

### Recurrence relation quicksort median-of-three

I am looking for a recurrence relation that describes the average number of comparisons of the quicksort algorithm considering an input array of size $n$. If the pivot element is picked randomly, the ...

37
votes

4
answers

2k
views

### Are these fast convergent series for $\log(2)$, $\log(3)$ and $\log(5)$ already known and proven?

Updated on Feb.16.2024
Fortunately for three of these series, Eqs. (1), (3) and (4), I have found a proof using classical methods which I placed in the Answers section below. (I doubt that there is a ...

0
votes

0
answers

23
views

### Online algorithms for MSTs from time series

Is it possible to construct the MST (minimum-weight spanning tree) for an potentially infinite sequence of points $\lbrace (i,Y[i]): i\in\mathbb{N}_0,\,c_{\text{min}} \le Y[i]\le c_{\text{max}}\rbrace$...

2
votes

1
answer

139
views

### Convexity of a function

Let: $F_{j+1,y}(s)$ be the cumulative distribution function of a binomial distribution with mean $y$, $j+1$ independent trials considered for $s$ successes. Is it possible to show in any way that:
$\...

1
vote

0
answers

169
views

### Fast algorithm for computing certain signal transformations

Let $f,g,h:\mathbb Z\to\mathbb C$ supported on $[-n,n]$. For $\tau\in \mathbb Z$, let $\operatorname{sh}_\tau f$ be the shift of $f$ by $\tau$ (i.e. $(\operatorname{sh}_\tau f)(t) = f(t-\tau)$). ...

4
votes

3
answers

301
views

### How to recover integer part from known fractional root part?

Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...

5
votes

0
answers

78
views

### Recovering a binary function on a lattice by studying its sum along closed walks

I recently posted this question on MSE. While it attracted interest, no answers were submitted, so I thought to try and post it here.
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While ...

5
votes

1
answer

196
views

### Bounds on how many Sidon sets required to cover an integer range from 0-N

If I have a range from 0-N (0,1,2,3...N) and I want to cover that set with some number of Sidon sets, is there a tighter bound than N for how many sets I would need.
For instance:
0,1,2,3
can be split ...

0
votes

0
answers

14
views

### Complexity of finding single source paths with capacity constraints and length constraints

Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...

1
vote

0
answers

86
views

### (Hyper)Graph canonical labeling - Optimizing for subgraphs [Nauty/Traces?]

To a hypergraph, we can apply the following transformations:
[Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these ...

0
votes

0
answers

155
views

### Solve NP-hard type problems with linear programming

I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...

1
vote

1
answer

200
views

### Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$

Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...

0
votes

0
answers

35
views

### Minimizing the number of grid squares to cover a polygon

Given an arbitrary polygon, and a grid square size x, I'd want to find a placement of the polygon such that it covers the minimum amount of cells in the grid.
The ...

2
votes

0
answers

483
views

### Are these finite semirings known?

I am trying to prove the properties below, and by doing this, I hope to find a way to speed up the computation of the below defined addition and multiplication. I am also interested if these finite ...

1
vote

0
answers

67
views

### Given a group $G$, is there any algorithm / method to check whether a group is sequenceable, or this problem is NP- hard?

The title of the question says it all: just recall that
A non-trivial finite group $G$ of order $n$ is said to be sequenceable if its elements can be arranged in a sequence $(b_1, b_2,\ldots , b_n)$ ...