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

learn more… | top users | synonyms (1)

13
votes
0answers
198 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 ...
11
votes
0answers
121 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...
9
votes
0answers
734 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
8
votes
0answers
130 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
8
votes
0answers
215 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 ...
7
votes
0answers
378 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 ...
7
votes
0answers
224 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 ...
7
votes
0answers
313 views

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

Background I would appreciate help in identifying / explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: sample from the distribution of each of $i$ parameters, $\phi_i$ ...
6
votes
0answers
56 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 ...
6
votes
0answers
503 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 ...
5
votes
0answers
21 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. ...
5
votes
0answers
135 views

Apartness of reals and algorithm exctraction

I am trying to wrap my head around the notion of apartness in constructive mathematics and it turns out I lack understanding miserably. I would like to use as elementary notions as possible, in the ...
5
votes
0answers
39 views

Computing N cofactors

I have an $N\times N$ matrix of small size (say $N=20$). Is there a way to evaluate the $N$ cofactors of the elements of the first row, faster than in the obvious way as $N$ independent determinant ...
5
votes
0answers
76 views

Algorithm for finding “fact families”

My friend's 3rd grader encountered the following question regarding "fact families" on her math homework: I was in 3rd grade sometime in the 1980s, so I don't believe I ever encountered this term ...
5
votes
0answers
80 views

A summation involving the ceiling function

I'm trying to find a better method of calculating the sum $$\sum_{k=1}^N\lceil ak\rceil^2$$ where $a$ is an irrational number. So far, my only idea is to somehow use a best rational approximation. ...
5
votes
0answers
119 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 ...
5
votes
0answers
81 views

Decoding of Gabidulin code

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
5
votes
0answers
110 views

Is there a way to figure out the minimum number of participants or maximum number of rounds in my tournament style?

I just finished hosting a Euchre tournament at work that was meant to get people to meet other people in the company. This is the third time I've hosted this type of tournament. The first two times, ...
5
votes
0answers
352 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 ...
5
votes
0answers
549 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
5
votes
0answers
114 views

Nice puzzle: Creating a binary word using weights and scales

You are given $N$ weights where for each $i \in \{1,2,...,n\}$, the $i$-th weight weighs $i$ pounds. You are given an $N$-binary-word that's formed by $L$'s and $R$'s and scales. You need to provide ...
5
votes
0answers
141 views

$k$-covering of the set of all possible n-length words

Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$. We call a ...
4
votes
0answers
37 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
4
votes
0answers
23 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
4
votes
0answers
31 views

Minimum number of vertex moves to un-intersect a polygon with itself

In my game, I have n points that form a self-intersecting polygon. The points can be moved by dragging them. How can I form a non-intersecting polygon this way, in ...
4
votes
0answers
115 views

Binary Palindrome

Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of ...
4
votes
0answers
137 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
4
votes
0answers
64 views

Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
4
votes
0answers
81 views

How to quickly approximate the eigenvectors of a symmetric matrix

Given a symmetric $n \times n$ matrix $A$, is there any algorithm that can quickly approximate all of its eigenvectors? By "quickly", I mean with time complexity less than $\mathcal{O}(n^3)$.
4
votes
0answers
245 views

Test for equivalence of algebraic expressions

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
4
votes
0answers
122 views

What is the name of this algorithm for calculating the lowest common multiple?

I have implemented a quite slow algorithm to calculate the lowest common multiple of 20 different integer values. It is described here with an example : ...
4
votes
0answers
321 views

Algorithm for generating homeomorphically irreducible trees of size n

In this video they talk about generating all the homeomorphically irreducible trees of size 10. I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
4
votes
0answers
164 views

Use of graph theory to determine tensor contraction ordering

I am considering using a computer program to execute tensor contractions like the following: $\displaystyle \sum_{ij}^{o} \sum_{ab}^{v} \sum_{KL}^{X} B_{ia}^{K} B_{ia}^{L} B_{jb}^{K} B_{jb}^{L} $ ...
4
votes
0answers
315 views

Smooth numbers algorithm

I am trying to understand quadratic sieve algorithm and now I am thinking of the way to check if number is smooth over a factor base? For example, say I have number $n = 87463$. First,I find bound $B ...
4
votes
0answers
427 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
4
votes
0answers
428 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 ...
4
votes
0answers
185 views

Convex hull of balls

The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
4
votes
0answers
571 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
4
votes
0answers
546 views

Graph theory classic problem

Suppose there is a city,the city has N buildings. In fact, any building in this city is either A HOUSE or A RESTAURANT. The N buildings are conveniently numerated by integer numbers from 1 to N. To ...
4
votes
0answers
315 views

Bellman-Ford algorithm with changes

I got this question and I will be happy for a clue. Here is a similar algorithm to the Bellman-Ford algorithm: ...
4
votes
0answers
286 views

Optimal sorting algorithm with modified cost

First, this was one of the four problems we had to solve in a project last year and I couldn’t find a suitable algorithm so we handle in a brute force solution. Problem: The numbers are in a list ...
3
votes
0answers
34 views

How to create a new formula for a fractal-type image?

(If this is the wrong place to ask, then PLEASE tell me where to take the question instead of chewing me out over this.) I have been learning how to write out SVG by hand, and in the process made a ...
3
votes
0answers
33 views

Can I go from the LU factorization of a symmetric matrix to its Cholesky factorization, without starting over?

I mistakenly computed the LU factorization and then realized that the question is asking for a Cholesky factorization, i.e., finding a lower triangular matrix L such that the symmetric matrix A has ...
3
votes
0answers
37 views

What is the area covered by a Random walk in a 2D grid?

I am a biologist and applying for a job, for which I need to solve this question. It is an open book test, where the internet and any other resources are fair game. Here's the question - I'm stuck on ...
3
votes
0answers
63 views

Find a real number with even digits in a given base

A real number x ∈ (0,1) is called b-good if x converted to any base b >= 2 has all digits ...
3
votes
0answers
74 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 ...
3
votes
0answers
33 views

How to generate a function with multiple variables to fit experimental data?

I am researching methods to increase the accuracy of an algorithm that is currently used to analyse radiation patterns as they hit our sensor. (For the non-physicists, we will mainly see Alphas, ...
3
votes
0answers
27 views

Need to calculate number of valid domain names between two other domain names

A domain name can be 2 to 32 characters in length. The first character can be the characters 'a' through 'z' The last character can be the characters 'a' through 'z' or '0' through '9' The ...
3
votes
0answers
69 views

Problem using the Fourier transform and convolution to compute an integral

I'm trying to write a subroutine (in Fortran) to compute integrals of the form $$I=\int_{-L}^{L} f(x)g(y-x) \:\mathrm{d}x, $$ using the convolution theorem and fast Fourier transforms. In my routine, ...
3
votes
0answers
24 views

Finding a cycle in a directed graph, however…

Say we have some directed graph, G. Every now and then, I can add either: a single arc from an existing vertex to another existing vertex (but no self-loops), add one new vertex with an arc to an ...