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
115 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
106 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
46 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
163 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
189 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
66 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
239 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
59 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
59 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
47 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
143 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
142 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
62 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
36 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
151 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
123 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
93 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
78 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
50 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
215 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
186 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
96 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
126 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
145 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
165 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 ...
2
votes
0answers
81 views

Iterative method for solving linear equations that generate narrower and narrower bound on the solution

I know that there are many methods that solve linear equations $Ax = b$ iteratively. But I'm curious if there's one that in each iteration tells us a bound on the solution. Specifically, assume $Ax^* ...
2
votes
0answers
319 views

Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $$||f-G_m(f,D)||>Cm^{-1/2}|f|_{H}$$ ...
2
votes
0answers
381 views

Logistic regression algorithm in Casio and Texas Instruments calculators

When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form $$f(x) = \frac{c}{1+ae^{-bx}} $$ The problem I have (when teaching in a class where both types of ...
2
votes
0answers
166 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
2
votes
0answers
327 views

Incremental algorithm for variance of geometric mean

For our application, I'm trying to find a memory-efficient, incremental algorithm to maintain variance of geometric mean. This "online algorithm" on Wikipedia seems excellent, ...
2
votes
0answers
96 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
2
votes
0answers
75 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
2
votes
0answers
55 views

Algorithms for the Antikythera Mechanism

I am working on a little computer program, and i was wondering if any one knew of any collections of all the calculations done and their associated mathematical algorithms? The algorithms dont have ...
2
votes
0answers
38 views

How to pick correct sign on matrices such that their sum is a nonnegative matrix?

Given a set of matrix $M_i$, by picking a sign coefficient $S_i\in\{-1,1\}$ How can I effectively find a combination that the sum $M^*= \sum_{i=1}^N S_iM_i$ is a nonnegative matrix. i.e. ...
2
votes
0answers
76 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
2
votes
0answers
172 views

google page rank algorithm with range of values

According to the wikipedia article, the iterative google page rank algorithm is defined as follows: Can this be modified to include a range of values, not just binary, and would it look something ...
2
votes
0answers
342 views

Mathematics in the “ The Art of Computer Programming”

I don't know of this the right place to ask this type of question and hence I apologize (in advance) for any inconvenience. Here is my question: I have studied Concrete Mathematics by Knuth, Graham ...
2
votes
0answers
100 views

Why is there no alpha-approximation algorithms for k-center problem where $\alpha<2$?

On page 39 of Design of Approximation Algorithms, the author argues this case with the dominating set problem. I can't understand it. A dominating set problem is a special case of the $k$-center ...
2
votes
0answers
458 views

Counting couples having least common multiple less than a number

Let f(n) be the number of couples (x,y) with x and y positive integers, $x\leq y$ and the least common multiple of x and y equal to n. Let g be the summatory function of f, i.e.: $g(n) = ...
2
votes
0answers
75 views

Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...
2
votes
0answers
709 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
2
votes
0answers
73 views

Petri net analysis (attainability)

how to analyse safe petri net for attainability? (i need algorithm) I have an oriented multigraph $\mathbb{G}$. $A$ - adjacency matrix. $m$ - the count of input elements. $n$ - the count of ...
2
votes
0answers
103 views

Maximum Flow in Dynamic graphs

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in $G$ now new node added/deleted with related ...
2
votes
0answers
585 views

Computing the Minimum Number of Squares Needed to Sum to $n$

I am aware of Lagrange's Four-Square Theorem, which states that every positive integer can be written as the sum of at most four squares. Clearly some integers require fewer squares. Does there ...
2
votes
0answers
142 views

Find most densely located $K$ points among $N$ ($N \gt K$) points in two dimension

Suppose I have $N$ points in two dimensional space. I want to know which $K$ of them ($K \lt N$) are located most densely (so that area of Convex Hull of points or sum of squares within cluster is ...
2
votes
0answers
83 views

Is there a use for this technique?

I remember reading once about the following algorithm: Consider a lattice grid and $N$ houses situated at grid points, in which live the town elders. They want to choose a lattice point location ...