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)

2
votes
0answers
66 views

“Alice and Bob” problem with matrices

Alice has a binary matrix $A$, and Bob has a binary matrix $B$. Both matrices are of size $n \times n$. Alice and Bob want to check if the matrices are equal except for exactly $1$ entry. Alice has to ...
2
votes
0answers
134 views

Flow reduction by removing a set of k edges

I am trying to find an algorithm which recieves as input: 1) a Flow network N(G,c,s,t) in which the capacity of an edge is either 0 or 1 (i.e. Exists or not). 2) a positive integer k The output ...
2
votes
0answers
34 views

Ordering binary matrices for reflection/rotation

I have a collection of $n\times n$ binary matrices and I would like to reduce it for symmetry ($D_4$ -- reflections and rotations). The naive method of testing each pair is very slow because the ...
2
votes
0answers
37 views

Combinations of Choices

I have a pretty hard problem to solve here, and I have no idea how to start. I have X kind of fruits and 5 colors (let's say Red, Green, Yellow, Blue and Purple). Each fruit can be available in ...
2
votes
0answers
23 views

Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example). I'm ignoring the decision problem, because I am doing two things that ...
2
votes
0answers
44 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
2
votes
0answers
82 views

Upper limit for adding N numbers in grid of N processors in parallel

We must show how N binary numbers, each consisting of N bits each, can be added in a linear grid of N+logN processors. Suppose that the binary digits can be inserted directly in each processor of the ...
2
votes
0answers
89 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
2
votes
0answers
68 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
2
votes
0answers
52 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
2
votes
0answers
20 views

Transforms with $O(N \log N)$ Complexity

Beside the Discrete Fourier and Walsh-Hadamard operators, are there any non-trivial, bijective operators that admit an evaluation algorithm of $O(N \log N)$ time complexity or better, whose inverses ...
2
votes
0answers
73 views

An algorithm for solving linear diophantine equations?

I am entering an interesting team based math contest called the purple comet, and quite a lot of questions on this contest involve Diophantine equations. For this contest, you are given a computer, ...
2
votes
0answers
43 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
2
votes
0answers
46 views

Performance estimation of shellSort

I'm trying to make a performance estimation for shell-sort algorithm. And I fail in it. My formula: equals to where dz is outer while-loop, dy is middle for-loop, and dx is inner for-loop ...
2
votes
0answers
155 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
2
votes
0answers
60 views

Expected error due to the tablemakers' dilemma

[note: to me, this does not seem like a question for m.se, but on mathoverflow it has been retroactively closed, with very little indication of why or what might be corrected... and waiting for ...
2
votes
0answers
106 views

What are the principle behind calculation of pi

It is possible that this is a duplicate, but I cannot find anything. I have always been wondering how to calculate pi. However, just using a given formula like the infinite series formulas does not ...
2
votes
0answers
36 views

Decide whether a function has an elementary indefinite integral without determining it!

Risch, who developed the algorithm in 1968, called it a decision procedure, because it is a method for deciding whether a function has an elementary function as an indefinite integral; and also, if ...
2
votes
0answers
253 views

Triangle Packing-Problem

Theory and Question We define a normalized triangle $T$ as an ordered list of six points s.t. $p \in [0,1)$ for all $p \in T$. Let $T = [x_0, y_0, x_1, y_1, x_2, y_2]$ be a normalized triangle. We ...
2
votes
0answers
66 views

Rank Of A Matrix Under Special Conditions

Let A be a $N*N$ matrix. Now A is defined in a special manner: Each row of A is defined by two integers L and R ($0\le L,R\le {N-1}$), such that all elements from the $L^{th}$ to the $R^{th}$ are all ...
2
votes
0answers
152 views

Megaminx parity

I have an old 12-colored Megaminx that I put all new stickers on because the old ones were falling off. This Megaminx was in more of a state of disrepair than I originally thought, though, and when I ...
2
votes
0answers
32 views

Non Approximation result

Say we have a constant approximation algorithm for the following objective: $$\min_x f(x) \;\;\;\;\;\; (1)$$ Now, we want to solve the following objective: $$ \max_x (N - f(x)) \;\;\;\;\;\; (2) ...
2
votes
0answers
162 views

Finding maximum differences in an array of real numbers .

This is an algorithm design question which often appears in exams in a course that I take in the university . Suppose I have an array $A\in\mathbb{R}$ of size $n$ . I am required to find the ...
2
votes
0answers
57 views

Graph Connectivity

I am given an initial connected graph $G$ with $n$ nodes and $m$ edges. At each step I remove an edge from $G$ and ask if $G$ is connected. Can the queries be answered in $\mathcal{O}(\log n)$ time ...
2
votes
0answers
59 views

String diversity

String diversity is the number of symbols that occur in the string at least once. Diversity of s will be denoted by d(s). For example , d("aaa")=1, d("abacaba")=3. Given a string s, consisting of ...
2
votes
0answers
133 views

Using an elliptic curve to create pseudo random number

I recently started learning about encryption. I read about how elliptic curves can be used to create pseudo random numbers (and how the nsa might have abused this fact to create a backdoor in ...
2
votes
0answers
51 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
2
votes
0answers
153 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
2
votes
0answers
50 views

Is there a known algorithm for approximating all the real and imaginary zeros of any well behaved equation of a single variable?

Does there currently exist a general algorithm (or set of algorithms used together) that will approximate all the zeros of any well behaved non-differential equation of a single variable which has a ...
2
votes
0answers
127 views

Lattice theory in mathematics and physics

I have undertaken a project examining lattice model and trying to construct algorithm that could work on all lattice (in physical sense, or crystal structure). I notice there is a branch in ...
2
votes
0answers
185 views

Limit definition for big O

so the def. says that $f(n) \in o(g(n))$ if for any $C > 0$ we have $C g(n) > f(n)$ for all $n\geq n_{0}$ i.e $$ \lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = 0 $$ in small o we the condition ...
2
votes
0answers
21 views

software to decide whether a 2-generator subgroup of PSL(2,R) is discrete/free

Gilman developed an algorithm with polynomial complexity that, given two elements in PSL(2,R), decides whether the group they generate is free/discrete or not. I was wondering whether anybody ever ...
2
votes
0answers
154 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
2
votes
0answers
31 views

Redistribution Algorithm

I've one thousand buckets of different sizes. Each bucket consists of red and blue balls of different weights. I know that $60$ percent of the total ball weight comes from the red balls and $40$ ...
2
votes
0answers
136 views

Bending of track in a racing game

I am trying to create a small racing game in which the track would be modeled using a BSpline curve for the path's center line and directional vectors to define the 'bending' of the track at each ...
2
votes
0answers
50 views

Voronoi's algorithm

Can someone give me an exact pseudo code of the Voronoi's algorithm for finding fundamental units of cubic fields? I searched the web but couldn't find it. It will be very grateful If someone can ...
2
votes
0answers
164 views

How to this calculate summation formula more quickly

Let $$ S = \sum_{p=1}^{10^{11}} \sum_{q=1}^{10^{11}} (p-1)(q-1) 2^{\gcd(p,q)} $$ then how to calculate $ S \bmod 10^8 $ more quickly? Thanks in advance.
2
votes
0answers
241 views

Simple Algorithm Running Time Analysis

A sorting algorithm takes $1$ second to sort $1,000$ items on your local machine. How long will it take to sort $10,000$ items if you believe that the algorithm takes time proportional to ...
2
votes
0answers
69 views

Improving Montgomery product

I am reading the paper "A Cryptographic Library for the Motorola DSP56000" (http://link.springer.com/content/pdf/10.1007%2F3-540-46877-3_21.pdf) which describes a trick to speed-up calculation of the ...
2
votes
0answers
310 views

How to calculate a PHI-ellipse defined by 3 points and its width/length ratio

in the field of technical analysis for stock markets, the usage of so-called Phi-Ellipses is getting popular. One important property of this ellipses is its constant length/width ratio (e.g. 1.618). ...
2
votes
0answers
61 views

Minimal set of algebraically independent numbers

Suppose we have a set of polynomials $f_1, f_2, \ldots, f_n \in \mathbb{Q}[x]$. Consider the set $$S := \{\alpha \in \mathbb{C} \; | \; f_i(\alpha) = 0 \text{ for some } i \}$$ of complex roots of ...
2
votes
0answers
42 views

About a sequence with a simple property.

I want to use 1-n to generate a sequence S whose length is 2*n. Each number from 1-n will appear exactly twice. The sequence should satisfy the following property: if S[i] = S[j] = k, i < j, j-i ...
2
votes
0answers
61 views

Difference Sets

suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
2
votes
0answers
48 views

Finding $k$ unknowns given the sum of their first $k$ powers

Motivation: The motivation for this question came from a Computer Science problem of finding duplicates in a list in constant time and constant space. If the list of numbers was $i_1, i_2, \ldots, ...
2
votes
0answers
184 views

monotonic smoothing fit to be implemented (in python or other language)

In a post that already exists, implementation-of-monotone-cubic-interpolation, there is a good method for fitting data which necessarily includes all of the given points. But, what if I need to ...
2
votes
0answers
150 views

Subtrees of a tree

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for example: If ...
2
votes
0answers
70 views

Computationally efficient means of determining distance in the Skorohod Topology?

I have two functions f and g in a computer. Domain 1...N. I'd like to compute their distance using the Skorohod Topology in an efficient manner. (I first ran across this metric many years ago in ...
2
votes
0answers
66 views

Testing combinatorial species for isomorphism

Given a system of species equations that specifies two species, is there an algorithm to test if they are isomorphic? Testing for isomorphism can be done by testing the equality of the coefficients ...
2
votes
0answers
37 views

Does Miller Rabin algorithm becomes faster if $a$ is choosen from the set $\mathbb{Z}_n^*-(\mathbb{Z}_n-\{0\})$ rather than randomly

In Miller-Rabin Primality Test for $n$ we first represent $n-1$ as $u\times2^k$ and then random choose some $a$ from the set $\{2 ,3 \cdots n-2\}$ and then we compute $b_0(=a^u),b_1(=b_0^2)\cdots ...
2
votes
0answers
166 views

Is Risch's algorithm powerful enough to determine any integral of a function have a closed form or not?

Is Risch's algorithm powerful enough to determine any integral of a function have a closed form or not? Is there a historic piece of reference that support your answer? ...