Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
13
votes
0answers
150 views
Can every number be written as a small sum of sums of squares?
In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, ...
11
votes
0answers
213 views
In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?
For example:
$M = 2, N = 2$, ans $= 6$
$M = 3, ...
6
votes
0answers
109 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 ...
6
votes
0answers
200 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$
...
5
votes
0answers
80 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 ...
5
votes
0answers
132 views
GAP semidirect product algorithm
Can anybody guide me towards, or possibly even explain here, the algorithm that GAP uses to compute the semidirectproduct of two permutation groups which outputs another permutation group?
EXAMPLE:
...
5
votes
0answers
106 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 ...
5
votes
0answers
364 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 ...
5
votes
0answers
81 views
$X^A \equiv B \pmod{2K + 1}$
I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.
Is there something special about the modulus being odd that allows us to ...
5
votes
0answers
243 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. ...
4
votes
0answers
55 views
Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?
The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all?
With the ...
4
votes
0answers
130 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
106 views
Is there a polynomial-time algorithm to find a prime larger than $n$?
Is there a polynomial-time algorithm to find a prime larger than $n$?
If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
4
votes
0answers
123 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
163 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
114 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
496 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
259 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:
...
3
votes
0answers
75 views
Difference between two sets of data points
I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
3
votes
0answers
120 views
Algorithm For Continued Fraction of $\pi$ without error.
Is there an algorithm that will output the numbers in the continued fraction of $\pi$ without error? If one uses the usual method of calculating continued fractions, an approximation of $\pi$ is ...
3
votes
0answers
81 views
Two closest points in Manhattan distance
I'm wondering about Manhattan distance. It is very specific, and (I don't know if it's a good word) simple. For example when we are given a set of $n$ points in this metric, then it is very easy to ...
3
votes
0answers
69 views
How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?
I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
3
votes
0answers
58 views
Reordering of a sequence of points
Given a finite sequence of points $\{\boldsymbol{\alpha}_k\}_{k=1}^m$, here $\boldsymbol{\alpha}_k\in \mathbb{R}^n$. My question is:
How to find a reordering of ...
3
votes
0answers
71 views
Why does Lenstra ECM work?
I came across Lenstra ECM algorithm and I wonder why it works.
Please refer for simplicity to Wikipedia section Why does the algorithm work
I NOT a math expert but I understood first part well enough ...
3
votes
0answers
175 views
Singly Connected Graphs
Hi I was wondering if someone could help answer a question for me. I was working on a problem from my algorithms class that asks for an algorithm to determine whether or not a graph is singly ...
3
votes
0answers
111 views
Simple game with coins - strategy
Let's play a game:
There are $n$ stacks of coins in a row. $i$-th stack consists of $d_i$ coins. Two players: $\text{Player1},\text{Player2}$ make moves alternately. Player in his turn can only take ...
3
votes
0answers
127 views
Checking whether a string is interleaving of two other strings
I am trying to develop an algorithm to check whether a string s3 is interleaving of another strings s1 and s2.
Say s1="abc" and s2="abe", then possible interleavings are ababce, ababec or abcabe.
I ...
3
votes
0answers
79 views
Serret's algorithm and Fermat's theorem on sums of two squares
Serret's algorithm(1848) proved Fermat's theorem on sums of two squares as follows:
$p\equiv1\pmod4, u^2+1=kp, 1\leqslant u<\frac{p}2$
$r_0=p, r_1=u$, then Euclidean Algorithm
$$r_0=q_1r_1+r_2$$
...
3
votes
0answers
296 views
Light Out Puzzle Solution
I am decided to solve the puzzle game named Lights out. So, i choose linear-algebra to solve my problem, so note that this link, i start my work as follow :
NOTE : Any light states can accept two ...
3
votes
0answers
136 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 ...
