Skip to main content

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).

3,715 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
37 votes
0 answers
1k views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
Rodrigo's user avatar
  • 1,031
17 votes
2 answers
557 views

Is there a numeral system that makes both addition and multiplication easy?

Decimal positional notation, the system for writing numbers we all use every single day, makes addition very easy by transforming it from a computation to a repeated operation on individual digits (...
user avatar
16 votes
0 answers
460 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
Leandro Zatesko's user avatar
15 votes
0 answers
269 views

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

I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following: Given an even ...
GSofer's user avatar
  • 4,333
14 votes
0 answers
168 views

Random domino tilings: Is this distribution well-defined, and how can it be sampled from?

I'd like to ask questions about a "random domino tiling of the plane". However, it's not quite obvious how to go about precisely specifying what this means. My first instinct was to do ...
RavenclawPrefect's user avatar
13 votes
0 answers
2k views

Is there a Sokoban level with such conditions

First of all, let me explain what Sokoban is. It is a logic game created in Japan and it literally means "warehouse keeper". It is a type of transport puzzle, in which the player pushes boxes or ...
user avatar
11 votes
0 answers
607 views

Solving general (dis)entanglement puzzles

What is the state of the art in (modelling and) solving a general (dis)entanglement puzzle? The following picture shows a nice example: There is a project called "The Untangler", which seems to be ...
Daniel Gerigk's user avatar
10 votes
0 answers
426 views

Peaks in the circle chaos game

The chaos game is a random walk that steps halfway between your current position and a set of predefined points. If the points are on an equilateral triangle, the resulting set is Sierpinski's ...
Hooked's user avatar
  • 6,687
10 votes
0 answers
257 views

The practical usage of Arnold Matrix Trace Theorem

I would like to ask about the Arnold's Matrix Trace theorem: $$\textrm{tr}\big(A^{p^k}\big)\equiv\textrm{tr}\big(A^{p^{k-1}}\big)\ (\!\!\bmod {p^k}).$$ This theorem looks fantastic to me. But is ...
Gevorg Hmayakyan's user avatar
10 votes
1 answer
601 views

Determining sign(det(A)) for nearly-singular matrix A

Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a ...
user1071136's user avatar
9 votes
0 answers
2k views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N \...
Ahmed Nassar's user avatar
9 votes
0 answers
462 views

Does this calculation have a name, or a generic formulation?

Background Informatiom I would appreciate help in identifying or explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: Sample from the distribution of each of $i$ parameters, $\...
David LeBauer's user avatar
8 votes
2 answers
220 views

Subspaces with common images

Let $X$ and $Y$ be finite dimensional vector spaces over $\mathbb{C}$, and let $S,T:X\to Y$ be linear transformations. Is there a method for determining all subspaces $V\subseteq X$ such that $S(V)=T(...
Noam Kolodner's user avatar
8 votes
0 answers
276 views

Count permutations with given longest increasing subsequence

Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
Benjamin Wang's user avatar
8 votes
0 answers
176 views

Algorithms to Compute Dimension of Lie Algebra

I am looking for fast algorithms to solve the following problem: Let $\{b_1, b_2, \dots, b_m\}\subseteq M_{n}(\mathbb{C})$ be an independent set over $\mathbb{R}$. Find the dimension of the real lie ...
MathPanda's user avatar
8 votes
0 answers
317 views

Efficient algorithms to determine whether vertices form a deadlock

$\textbf{I. Problem Statements}$ Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations: (1)$[m] := \{1, 2, \dots, m\}$. (2)$e_i$ is the elementary vector with $...
Muses_China's user avatar
  • 1,006
8 votes
0 answers
312 views

Harmonic Numbers' Numerators Divisible by a Prime $p$

For a prime $p$, I am trying to determine the set of all $n$ for which the numerator of $H_n$ is divisible by $p$, with $H_n$ being the $n$'th harmonic number. After going through a lot of literature, ...
MC From Scratch's user avatar
8 votes
0 answers
141 views

Is this kind of "Gerrymandering" NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
Frunobulax's user avatar
  • 6,639
8 votes
1 answer
710 views

Packing problem - how to fit things nicely with just the aspect ratio of the objects

Suppose you have a rectangle that is w units wide and h units tall (bounding rectangle). You also have an even ...
вʀaᴎᴅᴏƞ вєнᴎєƞ's user avatar
8 votes
0 answers
213 views

Coin weighing to find $k>3$ similar-weight sets

Fix $k>3.$ There are $n$ coins with positive real weights. You have a scale that, between two sets of coins, tells you which set is heavier, or if they are equal. Is it possible to perform at most $...
Dap's user avatar
  • 25.3k
8 votes
0 answers
1k views

Are there any solvers to Chance Constrained Programming Problems?

I'm trying to solve a chance constrained programming (CCP) problem $\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$ ...
StevenG's user avatar
  • 133
8 votes
0 answers
276 views

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
user avatar
8 votes
1 answer
127 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} 3&2&6&3&5&6&3&...
snocavotia's user avatar
7 votes
0 answers
86 views

Wiping a plane clean with a rectangle (chalkboard erasing alogrithm?)

Let's say I use some green chalk to draw and fill a continous shape on a chalkboard. Let's assume the shape has no holes in it. I then use some red chalk to cover the area around my blob for a ...
dZed's user avatar
  • 71
7 votes
0 answers
66 views

Computing $\mathrm{Fix}(\phi)$ for autormophisms $\phi$ of free groups

Let $F_A$ be the free group generated by the finite set $A$ and let $\phi\colon F_A \to F_A$ be a group-automorphism. It is known [1] that $$ \mathrm{Fix}(\phi) = \{g \in F_A : \phi(g) = g\} $$ is (...
RB1995's user avatar
  • 319
7 votes
0 answers
721 views

In optimal transport, what is the difference between the Hungarian and Sinkhorn algorithms?

Optimal assignment using the Hungarian algorithm was found to be improved for optimal transport using the Sinkhorn algorithm. Intuitively I cannot make out why. More fundamentally, how optimal ...
develarist's user avatar
  • 1,534
7 votes
0 answers
363 views

Fast arbitrary decomposition of a positive-definite matrix

Given a positive-definite $n\times n$ matrix $\mathbf{A}$, my goal is to present it as a product of the form $\mathbf{H^TH}$, where $\mathbf{H}$ is an arbitrary $n\times n$ matrix. Cholesky ...
Sergey Guminov's user avatar
7 votes
0 answers
1k views

Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
user989's user avatar
  • 81
7 votes
0 answers
830 views

Is Risch algorithm learnable by a human being?

I've discovered a few months ago about the Risch's algorithm. It seems to be the best thing we have to find antiderivatives. Some days ago, I've found lectures on the integration of elementary ...
Red Banana's user avatar
  • 24.1k
7 votes
0 answers
490 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
draks ...'s user avatar
  • 18.5k
7 votes
0 answers
414 views

What’s the best way to cut an apple?

Take the apple in one hand, and the knife in the other. In the first cut, the apple is divided in two pieces: a small one that drops into the plate and a big one that is still hold with the hand. This ...
jbaylina's user avatar
  • 171
7 votes
0 answers
1k views

Random binary invertible matrix

For implementation of McEliece cryptosystem, I'm trying to generate a random binary invertible matrix and its inverse. Because this is usually the most time-consuming part of generating a McEliece ...
exa's user avatar
  • 183
7 votes
0 answers
313 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
Sadeq Dousti's user avatar
  • 3,331
7 votes
0 answers
731 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
Jeff's user avatar
  • 101
6 votes
0 answers
354 views

Decrease list difference via swaps

There are four lists, each with $100$ numbers in $[0,1]$. You want to perform as few swaps between pairs of numbers as possible, so that the difference between the sums of numbers in any two lists ...
user57012's user avatar
6 votes
0 answers
121 views

Does there exist a constant c such that for all n>c, n is representable?

Given a positive integer $n$, we can always perform one of the two processes: (i) Take the number $n$ and add it to the sum of digits of $n$ (ii) Take the number $n$ and add it to the product of ...
Lulun's user avatar
  • 151
6 votes
0 answers
182 views

Finding small square roots modulo P

Let $P$ be a sufficiently large prime number. Let $x$ be a positive integer, we can write: $$ \begin{align*} x^2 = kP + a \end{align*} $$ where $0 \leq a < P$. Suppose furthermore that $\sqrt{P} &...
Thomas's user avatar
  • 932
6 votes
0 answers
348 views

Graph Theory: Every graph has a unique potential

Let $G$ be a simple, connected graph. Define the potential of a graph as $$V_S(G)=\sum_{i=1}^{g-1}\sum_{j=i+1}^{g}\frac{\delta_{i\in S}\delta_{j\in S}}{d(u_i,u_j)}$$ where $S\subseteq \{1,2,...,g\}$, $...
QC_QAOA's user avatar
  • 11.8k
6 votes
0 answers
251 views

Generate a random permutation of the first $n$ numbers on the fly

I have a large number of people coming to my shop and want to assign ids from $1$ to at-most $n$ to all of them. While I don't know in advance how many people will arrive, I'll simply stop accepting ...
Rohit Pandey's user avatar
  • 6,913
6 votes
0 answers
2k views

Convergence of the complex QR algorithm to Schur decomposition

I study the complex Schur decomposition of a complex matrix $A \in \mathbb{C}^{n \times n}$, that is: $$ A = U T U^H $$ where $T$ is upper-triangular (the eigenvalues of $A$ appear on its diagonal, ...
Triceratops's user avatar
6 votes
1 answer
141 views

Optimization Problem: Find a smallest $S$ subset of Vertex set $V$ of digraph D

Given a directed graph $D=(A,V)$ , find a smallest set $S\subseteq V$ which satisfies that for every vertex $v\in V$ there exists a vertex $s\in S$ such that there is a directed path from $s$ to $v$ ...
Segni's user avatar
  • 355
6 votes
0 answers
2k views

Converting convex hull from $V$-representation to $H$-representation

After looking at many articles and understanding various algorithms regarding finding extreme points and convex hull of a set of vectors in $\mathbb{R}^d$, I still have not figured out how to go from ...
FreeMind's user avatar
  • 2,513
6 votes
0 answers
253 views

Is there a proof for this modified Collatz-like problem?

The Collatz Conjecture is a famously unproven problem in mathematics, but I was thinking of a slight modification, and whether or not a proof of this different form is trivial. Here is a statement of ...
fields's user avatar
  • 61
6 votes
0 answers
848 views

Numerical stability of Winograd short convolution algorithm

Similar to how Strassen matrix multiplication is an asymptotically faster matrix-multiplication algorithm, there exists a similar idea for convolution by (short) filters called Winograd convolution [1,...
Iwillnotexist Idonotexist's user avatar
6 votes
0 answers
161 views

Different geometric figures from trapezoids

I have recently bought a very interesting a Brazilian kit to my kid to build mosaics: It is easy to see that I am able to generate equilateral triangles, hexagons, parallelograms, Rhombuses etc. ...
DanielTheRocketMan's user avatar
6 votes
0 answers
102 views

Find a region with maximum sum of top-K points

My problem is: we have $N$ points in a 2D space, each point has a positive weight. Given a query consisting of two real numbers $a,b$ and one integer $k$, find the position of a rectangle of size $a \...
Arnold's user avatar
  • 101
6 votes
0 answers
1k views

Implementing the Risch algorithm to integrate $\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}$

Following the work of Andreas Wurfl i am trying to implement the Risch algorithm on $\int{\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}dx}$ following his method for extensions that are purely logarithmic, we ...
ENAFMTH's user avatar
  • 453
6 votes
0 answers
2k views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
Oliver's user avatar
  • 161
6 votes
1 answer
1k views

Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
sil's user avatar
  • 171
6 votes
0 answers
390 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
TSP's user avatar
  • 133

1
2 3 4 5
75