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
176 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
119 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
724 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
125 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
213 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
89 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} ...
7
votes
0answers
376 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
220 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
311 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
55 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
581 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
6
votes
0answers
498 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
132 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
37 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
73 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
76 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
118 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
78 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
341 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
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
140 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
34 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
102 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, ...
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
114 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
132 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
62 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
516 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 ...
4
votes
0answers
79 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
240 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
162 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
309 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
411 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
421 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
181 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
553 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
543 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
284 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
61 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
72 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
31 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
24 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
66 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
22 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 ...
3
votes
0answers
53 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
0answers
50 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 ...
3
votes
0answers
34 views

Check if a point is inside a rotated 2D NACA 0012 airfoil

I've already checked the rotated rectangle problem but this is (I think!) a little more complicated. I have a CFD calculation of a 2D NACA 0012 airfoil and I need to test if a point is inside the ...