Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

12
votes
0answers
150 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 ...
10
votes
0answers
98 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 ...
10
votes
0answers
199 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
9
votes
0answers
667 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
113 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 ...
7
votes
0answers
369 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
208 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
201 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
191 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 ...
7
votes
0answers
308 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
50 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
86 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} ...
6
votes
0answers
572 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
476 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
36 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
63 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
107 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
57 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
286 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
109 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
139 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
82 views

Minimum number of real multiplications to multiply two quaternions

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the ...
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
55 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 ...
4
votes
0answers
83 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
30 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
110 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
116 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
57 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
442 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
211 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
117 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
160 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
283 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
364 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
401 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
175 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
487 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
518 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
703 views

Project Euler Problem 338

I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
4
votes
0answers
314 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
273 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
15 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 ...
3
votes
0answers
38 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
26 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 ...
3
votes
0answers
32 views

Efficiently computing GCDs in $\mathbb{Z}[(1+\sqrt{-19})/2]$

The ring $\mathbb{Z}[(1+\sqrt{-19})/2]$ is a PID; hence any two elements have a GCD. How you would compute their GCD? In a Euclidean domain, you would use the Euclidean algorithm. But ...
3
votes
0answers
159 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
3
votes
0answers
46 views

Counting the number of partitions that are a distance d away from a fixed partition.

Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
3
votes
0answers
13 views

How should $k$ items be selected in $m$ trials so that the average size of the intersection of selected items is as small as possible?

Let $n$ be size of set of items and in $m$ trials $k$ items are selected from the set without replacement. In two different trials the same items can be selected. How should items be selected so that ...
3
votes
0answers
72 views

A Tricky Quetiones on Creative Algorithm in Graph

an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...