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)

0
votes
1answer
25 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
119 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
28 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
27 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
16 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
28 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
35 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
12 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
22 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
30 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
56 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
28 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
15 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
14 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
40 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
21 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
21 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
36 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
28 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
145 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
44 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
42 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
31 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
17 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
40 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
49 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
36 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
47 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
71 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
29 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
50 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
71 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
322 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
40 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
32 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
114 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
28 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
66 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
27 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
52 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 ...
2
votes
1answer
37 views

Semi decision procedures for Peano arithmetic?

Is there an efficient semi-decision procedure (i.e. an algorithm that sometimes works and sometimes not) for -at least- elementary problems in peano arithmetic? I am not talking about weak fragments ...
0
votes
1answer
33 views

Algorithm to find positive definite matrix given conditions.

I want an algorithm that always find one solution for the given problem below: Given a positive n length vector, b, a n vector of 1 values, u: I want to determine B, matrix n * n, positive definite ...