Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

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

1 2 3 4 5 14
15 30 50 per page