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)

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
139 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
56 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
102 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
35 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
225 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
65 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
126 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
31 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
150 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
117 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
140 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
48 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
124 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
159 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
136 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
28 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
121 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
48 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
202 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
281 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
162 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
145 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
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
163 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? ...
2
votes
0answers
138 views

L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in this picture). I'm interested to know how can one arrange the rules of an ...
2
votes
0answers
99 views

Clarification of variable values in Arithmetic Coding algorithm

I have been trying to follow this video to implement my own Arithmetic Coding algorithm in Java. I am having a bit of trouble figuring out what some of the variables in the video should be. For ...
2
votes
0answers
81 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
2
votes
0answers
247 views

COLAMD matrix reordering algorithm

Background I'm dealing with some variable size square sparse matrices resulting from a FEM analysis, and my next step is optimizing the system solving in terms of speed. This is a visualization of ...
2
votes
0answers
53 views

What kind of numerical methods are best applicable to this?

I'm wondering: what would be the best numerical method for solving a nonlinear integral equation of the form $$f(x) = a(x) + \int_{-A}^{A} K(x, t, f(t)) dt$$ where $f$ is the unknown function, a ...
2
votes
0answers
234 views

Proof of the optimality of A* algorithm

In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105. However, I cannot ...
2
votes
0answers
214 views

all eigenvalues of a large sparse symmetric matrix

my question is similar to how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors however i wish to be more concrete and ask if one can, on a standard PC (e.g. a ...
2
votes
0answers
100 views

The Edge Set Grown in Kruskal's Algorithm

Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let ...
2
votes
0answers
52 views

What is the pagerank of the given nodes?

Given nodes $A,B$ and $C$. with $A \rightarrow A$, $A\rightarrow B$, $B \rightarrow B$, $C \rightarrow A$, $C \rightarrow C$ where the arrows represent outgoing links from left and incoming links to ...
2
votes
0answers
28 views

Broken disk head

Broken disk head: We would like to read 1 byte = sequence of 8 bits from a disk, starting from bit 0. Our disk head reads 1 bit at a time. Disk head can only move forward, but after reaching bit 7 ...
2
votes
0answers
127 views

Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it, which contains all edges leading into it on all paths from a ...
2
votes
0answers
152 views

Effective model for calculating momentum or growth rate for a time series

I have a series of numbers tracking the performance of an entity on any given day. It's nothing but a simple integer for each date. For example, here's a series for Entity "X" ...
2
votes
0answers
47 views

Finding number of smaller elements for each element in an array

I am stuck in this problem. Can anyone help me. Thanks. Consider an array 'A' of 1st n natural numbers randomly permuted. Consider an array B formed from array A as given below B(k) = number of ...
2
votes
0answers
176 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...