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,564
questions
3
votes
0
answers
347
views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
1
vote
1
answer
134
views
computing $c_5$ in "Primality testing with Gaussian periods"
As far as I know, the April 2011 version of #143 on this page has not been improved upon.
On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$.
...
31
votes
5
answers
6k
views
What is a good method to find random points on the n-sphere when n is large?
As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at ...
1
vote
1
answer
226
views
What algorithms do you know for beltway reconstruction?
I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...
5
votes
3
answers
2k
views
Square root algorithm
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
2
votes
1
answer
194
views
Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?
Here is the problem:
I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements).
So I have one element $X$. I want to know if I can get $X$ making the sum of ...
2
votes
1
answer
371
views
Algorithm for representing a polynomial as a composition of lower degree polynomials
Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials (...
7
votes
1
answer
722
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
7
votes
2
answers
513
views
Recovering a Weighted Graph from Shortest Path Distances
I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), \...
17
votes
5
answers
967
views
Mathematics of privacy?
I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...
3
votes
1
answer
287
views
Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?
As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain.
And rational prime 257 is split completely in R.
Suppose prime ideal P of R is an arbitrary ideal lying ...
7
votes
1
answer
3k
views
Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?
Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...
1
vote
1
answer
225
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
4
votes
1
answer
801
views
Checking if a binary vector lies in the affine span of given binary vectors
Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...
4
votes
1
answer
366
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
12
votes
2
answers
564
views
Ideal Membership without Certificate?
I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...
0
votes
1
answer
371
views
What is the Bahadur-Anderson Algorithm?
What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?
1
vote
3
answers
265
views
Strategic vertex labeling
We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...
5
votes
2
answers
1k
views
Solve for $A$ and $B$ in $AXB=Y$
Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$.
Let $X$ be $n \times n$ matrix with entries in $R$.
Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...
4
votes
0
answers
637
views
Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids
Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...
27
votes
1
answer
651
views
Decidability of equality of expressions built using 1,+,-,*,/,^
Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
7
votes
0
answers
179
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
3
votes
3
answers
4k
views
L-systems and Sierpinski Triangle
I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).
I'm interested to know how could one arrange the rules of ...
3
votes
1
answer
495
views
Fastest Digit Extraction for Any Irrational Number
I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for speed)...
0
votes
1
answer
527
views
Giving a general term of a recursive function, and upper bound for it
Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.
Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise
Let $b_{t+1}...
2
votes
3
answers
384
views
existence of equivalence checking algorithm
Set D : Set of decision algorithms
X∈D if and only if
X is an Turing machine algorithm with finite length
takes one input i, binary number
X(i)=0 or X(i)=1 or X(i) runs forever
...
3
votes
1
answer
191
views
Separation of Anti-Hole Inequality
Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...
6
votes
2
answers
1k
views
Approximate number of primes below a given integer?
The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...
0
votes
2
answers
118
views
Fitting algebraic expression to a number [algorithm]
I know that it may turn out useless, but this is precisely the reason why I'm asking.
Does any one know of an existing piece of code that would find me the best approximation to a given irrational ...
3
votes
1
answer
209
views
Using Fourier Transform to speed up calculation of forces following an inverse square law
Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...
2
votes
1
answer
819
views
At what point does Miller-Rabin become faster than trial division?
I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...
0
votes
0
answers
544
views
max*min/(max+min) vs max*min/(max-min)
While working on a genetic algorithm, I needed to devise a fitness function for each chromosome. Each chromosome has 2 attributes: maximum accuracy and minimum accuracy.
The fitness should increase ...
0
votes
0
answers
168
views
Maximal Zero Sums Partition
You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
2
answers
129
views
Maximize 2-tuple efficiently
Hello I am lookin for an algorithm that efficiently finds all Tuples ${(x,y)$$\varepsilon U|\forall (u,w) \epsilon U \rightarrow (x>=u \vee y>=w)$.
I could of course check all tuples against ...
4
votes
0
answers
757
views
(Co)limit computations for diagrams of Vector Spaces
Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...
2
votes
1
answer
215
views
Reducing the error of Algorithms by assigning variables formulas instead of values
Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:
1- Mark ...
1
vote
0
answers
192
views
Construction of regular hypergraphs
Is there any algorithm to generate $3$-uniform $k$-regular hypergraphs with $n$ vertices? Any help is appreciated.
1
vote
0
answers
257
views
Optimize a convex hull on a 2D histogram so the selected points match a target shape
I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...
2
votes
1
answer
2k
views
Removing cycles from an undirected connected bipartite graph in a special manner
Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We ...
10
votes
2
answers
754
views
When polynomial f(x^2) can be factored as g(x)·g(-x) ?
In relation to my question Expression for the sum of square roots of zeros of a polynomial
How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where $...
2
votes
1
answer
499
views
algorithmic almost equitable partitioning
Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
0
votes
0
answers
131
views
Find polynomial in finite field
We have $A$, $B \in GF(q^k)$
We want to find polynomial $h \in GF(q)[x]$ where
$h(A) = B$
What is the lowest degree of $h$?
How to find $h$ with the lowest degree and what is complexity of this ...
2
votes
0
answers
84
views
Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case
I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
2
votes
5
answers
3k
views
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details.
Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, chipe2,......
1
vote
1
answer
888
views
Find root in finite field
What efficient algorithms exist for the solving $x^N = a$ in GF(q)?
What are their complexities?
2
votes
0
answers
658
views
Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin
Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...
1
vote
1
answer
389
views
calculate function from its divizor
There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$.
There is algebraic function f on C.
We have div(f).
How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + yg_2(...
6
votes
2
answers
2k
views
Find minimum-area ellipse which encloses two ellipses
I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...
2
votes
0
answers
190
views
Choosing a base where a given digit of a given number appears the most times
Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)
3
votes
2
answers
1k
views
Enclosing a set of ellipses within one ellipse
Is there an algorithm that takes in a set of ellipses and gives back an ellipse that encloses the original set of ellipses?