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)

-1
votes
1answer
44 views

Calculating distance between two squares of a board

Given an $n\times n$ board, for example a chess board 8x8, with the squares ordered in a Little-Endian Rank-File Mapping. Is there a direct way to calculate the distance between two squares using ...
2
votes
0answers
15 views

Accelerated Gradient Descent V.S Nonlinear Conjugate Gradient Descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has ...
0
votes
1answer
21 views

How to find right child in a pyramid number?

A pyramid number: 0 1 2 3 4 5 6 7 8 9 So is there any equation like: ...
5
votes
1answer
115 views

How can I calculate the formula of this fractal-like structure?

I did the following fractal-like structure manually, and I was trying to convert it to a formula (or an algorithm including formulas) to compute some parts of the drawing, but I get lost due to the ...
1
vote
1answer
26 views

How to find maximal dimension abelian subalgebra in finite Lie Algebra?

Is there any well known algorithm how to find maximal dimension abelian subalgebra in finite dimension Lie Algebra? If there is a built-in routine in some computer algebra system, it is the most ...
0
votes
0answers
35 views

Exponentiation of Pascal's Triangle(in matrix form)

I want to find a pattern in subsequent exponentiations of the pascal triangle shown in the form below Matrix P[K+1][K+1]: $$ \begin{matrix} \binom{0}{0} & 0 & 0 & 0\cdots ...
1
vote
1answer
26 views

More efficient algorithm for matrix rearrangement (MatLab)

Say I have the following matrix: $$A = \begin{bmatrix}0.1 & 2 \\ 0.1 & 4 \\ 0.1 & 6 \\ 0.2 & 3 \\ 0.2 & 2 \\ 0.2 & 7 \\ 0.3 & 10 \\ 0.3 & 7 \\ 0.3 & 5 ...
0
votes
1answer
15 views

How to insert a knot in NURBS if it coincides with the first knot?

I want to insert a knot to the knot vector. Currently I use the algorithm from the NURBS book, but it has an assumption that U={0,...0,u_{k},u_{k+1}...,1,...1}, the first knot and the last knot repeat ...
1
vote
1answer
26 views

Solving for a Binary Matrix: A somewhat unusual method needs justification, and mabye interpretation.

Introduction: Define a "Bit Map" to be a matrix whose entries can only be $0$ or $1$. Then numbers above and beside each column and row indicates how many entries are "filled" with a one. For ...
1
vote
0answers
30 views

Coin distribution problem to optimize

There are $N$ users, with each user having a money request. There are $T$ coins, these coins are to be assigned to the user in such a way that its request is fulfilled. Assume each coin may have ...
0
votes
0answers
11 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
0
votes
1answer
12 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
0
votes
0answers
21 views

RSA number sequence encryption

Encrypt the following number sequence $3,9,27$ with key $m=33$ and $r=7$ It's about RSA encryption. How should I encrypt this? Should I find the key $s$ (inverse key) and what then? $r \cdot s + ...
0
votes
0answers
29 views

Degree-Constrained Shortest Path Problem

The following is my problem: Given an undirected graph G(V,E) with cost c(e) associated with every edge e∈E such that c(e)>0 and a vector d=(dv : v∈V) which denotes the maximum degree on each vertex ...
0
votes
0answers
49 views

Minimum spanning tree for a weighted square grid

I have a particular grid with weighted edges connecting each vertex: From this I'm looking for an easy method to obtain a Minimum Spanning Tree. I can easily check columns or rows and remove all ...
0
votes
1answer
20 views

How do we prove a method is optimal?

This is a very simple question, infact it's so simple that I have no idea how to solve it. We have an ordered list of $n$ words. The length of the $i$'th word is $W_i$. Our goal is to write all the ...
1
vote
1answer
25 views

List all sets of points in a plane that are enclosed by circles with given radius

My problem is: Given N points in a plane and a number R, list/enumerate all subsets of points, where points in each subset are enclosed by a circle with radius of R. Two subsets $S_i$ and $S_j$ should ...
0
votes
0answers
14 views

Anomalous diffusion dynamic exponent calculation

I'm trying to calculate this $\alpha$ (dynamic exponent, I think) from an equation from this wikipedia article. The equation (anomalous diffusion power law): $r^2 \propto t^\alpha$ The problem is ...
1
vote
0answers
13 views

anomaly detection algorithm problem

I've been trying to determine how to detect point-anomalies given window-anomalies. In more detail, I know for each 30-day window whether it contains an anomaly. For example, window 1 starts at ...
2
votes
1answer
37 views

Proving optimality of simple greedy algorithm

Professor Xavier (yeah, the one from X-Men) wants to drive from Reno to Newark. His gas tank, when full, holds enough gas to drive $n$ kilometers. The professor has a map showing the gas stations ...
2
votes
1answer
20 views

Problem with my simple algorithm to count repetitions

We have two arrays $A,B$ with sizes $n,m$ respectively. We know that $m \geq n$. We also know that no array contains the same number twice. Propose an algorithm that prints how many numbers appear in ...
0
votes
1answer
21 views

Calculate the asymptotic growth of a sum that contains log or binom

I'm looking for a basic explanation how to calculate the asymptotic growth of sums. Take for example this one: $\sum_{i=1}^{lg(n!)} 2^{n^2}$ or this one: $\sum_{i=0}^{n} {n\choose{i}}$ The ...
0
votes
1answer
42 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
1
vote
0answers
20 views

How to properly detect rows to be swapped in a Gaussian elimination?

I'm trying to describe an algorithm for solving solvable linear systems. The Gaussian elimination is pretty straightforward in terms of adding multiples of rows. However, consider the following ...
1
vote
0answers
15 views

Planar nearest neighbor search for many points.

I have two sets of points on the plane, A and B. For every point in A, I would like the k nearest points in B. The naive approach is for each point in A having a linear selection to choose the kth ...
2
votes
3answers
34 views

Prove correctness of simple greedy algorithm to find max

We have $2n$ values $x_1,x_2,x_3,\ldots,x_n$ and $y_1,y_2,y_3,\ldots,y_n$ such that the pair $(x_i,y_i)$ represents the location of a city $i$. Assume there is no straight line that goes through all ...
1
vote
0answers
26 views

Algorithm for high contrast

Using this algorithm I can increase contrast but applications like Paint.Net can increase contrast significantly. For example it can convert to (by setting contrast to 100 and brightness to 100, ...
1
vote
1answer
136 views

Graham scan with collinear points

I'm having some trouble understanding the Graham scan algorithm as described in Wikipedia. Particularly, I don't understand how to handle collinear points. Consider these points as a simple example: ...
0
votes
1answer
43 views

Biggest n that can be solved in one second

I have been given the following problem: What is the largest n for which one can solve in one second a problem that requires $(\log_2(n))^2$ elementary operations, where each elementary operation is ...
0
votes
2answers
39 views

Worst case binary search

Suppose you play a game with a computer program where you guess a number between 0 and 1 and the computer uses binary search to search for your number. My question is what is the best number to ...
1
vote
2answers
30 views

How to find the indexes given the element index in a vector?

I have a vector $\mathbf{x} = [x_{11}, x_{12}, \ldots, x_{1n}, x_{21}, x_{22}, \ldots, x_{2n}, \cdots, x_{m1}, x_{m2}, \ldots, x_{mn}]^T$ of size $m\cdot n$. My problem is this: Given an index ...
0
votes
1answer
13 views

Giving change - what denominations guarantees an optimal greedy algorithm?

I was thinking about how giving change is a greedy algorithm for the optimal result, where the optimal result is getting the lowest amount of bills and coins possible. The algorithm I am referring to ...
0
votes
0answers
37 views

How can I write an algorithm to solve this formula for closest point to a set of lines in 3d

I am trying to understand how I can write an algorithm to solve the formula written at the end of this answer, that is: $$ 0=\sum_{i=0}^m \vec c - \vec a_i - \vec d_i \frac {(\vec c-\vec ...
1
vote
0answers
48 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
1answer
34 views

Randomly Generating Combinations From Variable Weights

The Question I have a list A of n objects. Each object An has a variable percentage Pn. I want to create an algorithm that generates a new list B of k objects (k < n/2 and in most cases k is ...
0
votes
0answers
35 views

Algorithm to calculate line segments between two points bounded by multiple surfaces

Problem statement: As a specific case, let's say I have a volume composed of a series of concentric cylinders. Given a fixed point P (a,b,c), and another randomly sampled point Q (x0,y0,z0), I would ...
0
votes
1answer
70 views

Gosper Formula for inv $\pi$, properties.

I need to understand very good how the properties of this formula $\frac{4}{\pi} = \frac{5}{4} + \sum_{N \geq 1} \left[ 2^{-12N + 1} \times(42N + 5)\times {\binom {2N-1} {N}}^3 \right] $ Taken from ...
0
votes
0answers
27 views

Calculation of error limits on linear least squares coefficients

I am developing software to find a 'good' solution for the over-constrained problem $Ax=b$, where $A$ is a known matrix $A_{i,j}$, $i=1,\ldots, M$, $j = 1,\ldots,N$, $M > N$, $b$ is a known ...
1
vote
2answers
46 views

If we do not know a number's factors, what is the algorithm (if there is one) to write it as a difference of two squares?

For example, if we have a number like 29873412895, is there an algorithm that can find it as a difference of two squares? Or must you need the factors of the numbers? And what might be the algorithm? ...
1
vote
1answer
64 views

Is there a mathematical way to determine a solution for puzzle games?

Or more specifically, a mathematical way to determine HOW to solve a puzzle game. Take a look at this screenshot of a puzzle game "The Talos Principle." As you can see, the purpose of this ...
5
votes
3answers
315 views

Understanding isPrime function from Wikipedia, a function that determines if a number is prime

I know there are several questions on how to determine if a number is prime but none of them help me understand this particular implementation on Wikipedia, ...
0
votes
3answers
38 views

What algorithm will maximize utility when assigning of students to practicum locations

I have the following problem: Students from a class of 150 are beginning practicum training. Students have the option of either staying in an urban centre for their practicum, or optionally, they ...
1
vote
0answers
21 views

Iterative algorithms to approximate unknown multivariate convex real-valued functions by a set of linear upper/lower bounds

I am looking for iterative algorithms that can approximate a multivariate convex real-valued function $f(\vec{x})=y,\, \Bbb{R}^n\rightarrow \Bbb{R}$. The function is not known beforehand, but it is ...
1
vote
2answers
35 views

Determining which linear function is largest

I have a collection of linear functions of form $y_i= m_ix + b_i$ for positive integers $m,b,x$. I am trying to efficiently determine which equation (i.e. which $i$) corresponds to the largest $y_i$ ...
1
vote
2answers
113 views

Is there an algorithm for writing an integer as a difference of squares?

For example, if we have $36$, is there an algorithm to determine that it may equal $10^2-8^2$? What if we blow up the number to something like $492709612098$? Can it be written as the difference of ...
1
vote
0answers
28 views

Example of binary GCD for complex integers?

I know you can use bit shifting to speed up the GCD algorithm for a pair of integers. Is there a way to apply this idea to gaussian integers?
1
vote
1answer
25 views

Relevance scoring mechanism for multiple parameters

I have a program which build few attributes those decide relevance between two objects. attributes are $a_1, a_2, a_3$ Now what are different weighing or scoring mechanism to accumulate all three ...
3
votes
1answer
59 views

Finding the closest point to a set of lines in 2D

I would need to write an algorithm to find the closest point to a set of lines. These lines are infinite and are not parallel between each other. Closest point means that point where the sum of the ...
0
votes
1answer
23 views

How to compute sine function within certain precision

I know that there exists CORDIC algorithm, but CORDIC algorithm contains component $\arctan 2^{-i}$, which needs to be looked up. I do not know how this leads to the precision that is advertised by ...
0
votes
1answer
47 views

Subset Sum Problem (general)

I have a problem which turned to be similar to the Subset Sum Problem. The main differences between the Subset Sum Problem and my problem are: 1- The vector elements can be positive and negative (in ...