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
vote
2answers
26 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
31 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
46 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
27 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
63 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
25 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
56 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
309 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
34 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
11 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
112 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
17 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
22 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
57 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
21 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
43 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
29 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
31 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 ...
0
votes
0answers
35 views

A probabilistic algorithm (something close to Discrete logarithm)

$p$ - is a prime number. $a\in Z_p^*$ is a creator of the group $Z_p ^*$. The definition of the Discrete logarithm of $c\in Z_p^*$ is: $$\log_a c=b\iff a^b=c \mod p $$ Assume we have an algorithm ...
0
votes
0answers
21 views

which algorithm can be used to solve $L_1$-like problem?

I have a problem like this, $$ \min |v|_1+\lambda\sum_{i=1}^{n}v_i'\cdot\log v_i'\\ s.t.~~ ~y=Av\\ \sum_{i=1}^n v_i'=1 \\ v'_i=\frac{|v_i|}{\sum_{i=1}^n|v_i|}~~~(i=1,\cdots,n)\\ $$ where $v,v'\in ...
0
votes
1answer
22 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
2
votes
1answer
39 views

Is there an algorithm to find minimum number of undefinable words in a dictionary?

Here's the problem. Every word in a dictionary is defined by a set of other words. For example "cat" may be defined as "small mammal with fur". Can we choose a set of 'base' or 'prime' words such that ...
1
vote
1answer
20 views

Why Petri Net tokens are not added?

Reading this article it says: A firing of an enabled transition removes one token from each input place and adds one token to each output place. Now if I have the following net, with all ...
0
votes
1answer
24 views

Probabilistic algorithm for $a$ that is not a quadratic residue

We have $Z_n$ ($n\in \mathbb N$). $a\in Z_n$ is a quadratic residue if exists $x\in Z_n$ s.t. $x^2 =a \pmod n$. If there is no such $x$ that make it so $a$ is not a quadratic residue. There is a ...
2
votes
0answers
31 views

multi-game round robin tournament algorithm

Each year I am part of a group that hosts a "Lawn Game Olympics." 6 different lawn games (bocce, ladder golf, washer toss etc...) and every year a different amount of teams shows up. The first year ...
2
votes
2answers
30 views

Sampling from the von-Mises Fisher distribution?

This topic has already been tackled on this website (here). But, unfortunately, no clear cut answers were given. In (Wood,1994), there is apparently a rejection algorithm for sampling from this ...
1
vote
1answer
38 views

How many sets of four points in an MxN grid have one point contained by three other points?

Given a 3x3 grid: 1 2 3 8 9 4 7 6 5 We find 126 distinct sets of 4 points $$\binom{9}{4}$$ There are 8 cases such that when the points are connected with a line in clockwise direction, one point ...
0
votes
1answer
10 views

Invent a polynomial algorithm to find max non-degenerate minor

There is a matrix $A$ with $n$ rows and $m$ columns. The task is to invent a polynomial algorithm to find non-degenerate minor of maximum size. If I got it right, we can reduce this to Gaussian ...
1
vote
1answer
44 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
0
votes
1answer
41 views

finding total number of subset pairs of a set that has equal xor??

I recently came across a problem where i need to find the total number of subset pairs which has equal xor value for a given set. Like for following example: ...
0
votes
0answers
3 views

PageRank metaphor as suspended unlimited capacity pools

What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function $f:G \to R^n$ where $n$ is the number of nodes in the ...
3
votes
0answers
65 views

Problem using the Fourier transform and convolution to compute an integral

I'm trying to write a subroutine (in Fortran) to compute integrals of the form $$I=\int_{-L}^{L} f(x)g(y-x) \:\mathrm{d}x, $$ using the convolution theorem and fast Fourier transforms. In my routine, ...
1
vote
0answers
8 views

I need help with a complex weighted algorithm

I need help with a formula/algorithm I just cant work out what I am doing or find anything on the internet. I am not very good at mathematics I have not done it high since school so I understand if ...
1
vote
3answers
60 views

Exact concept of Monte Carlo Method [closed]

I am a programmer and just came across the section where in Monte Carlo was discussed. I would like to know the exact concept of Monte Carlo simulation. In net i have read about it that it is the ...
1
vote
2answers
40 views

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$, where $S_n$ is a symmetric group and $a$ and $b$ have same cycle type? Question 2: Is there any command in ...
1
vote
1answer
32 views

Courses, books or other resources specifically written to teach and help understand algorithmic language?

The algorithm course/book I'm taking (based on the book Algorithm Design by Jon Kleinberg and Éva Tardos) assumes we understand the language of algorithmic problems and solutions. However, it is not ...
0
votes
0answers
20 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
1
vote
0answers
20 views

Algorithm to generate Rhombic sphere tiling

I want to make a function for generate generic Rhombic triacontahedron and any level of detail of rhombic sphere tiling I want to know that can we use rhombic face to tile sphere in more detail than ...
0
votes
1answer
16 views

Set of edges is MST?

Given a Graph $G = (V,E)$ and given a subset $ T \subset E$. I would like to test, whether T is already a MST of G or not in constant time. Note: If $T^{MST}$ is the MST of G, then we know that $T ...
1
vote
1answer
30 views

Find if there is a matrix that her sum of each column and row representing two vectors

We have two vectors: $(a_1,...,a_n),(b_1,...,b_m)$. We want to know if there is a matrix $M_{nm}$ that all its elements are from $\left\{0,1\right\}$ with this condition: The sum of all the elements ...
1
vote
0answers
60 views

Efficient elevator strategy

Suppose an institution building has 12 floors and there are a total of 8 lifts. Now lets say a situation arises at peak times where almost all the lifts are crowded and people randomly enter any lift, ...
18
votes
2answers
711 views

Puzzle: Cracking the safe [duplicate]

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
2
votes
1answer
37 views

What is the worst-case running time of this algorithm?

What's the worst case running time? while flip_coin() == heads: continue; In other words, I flip a fair coin until I get tails. Of course we knows the expected ...
-1
votes
1answer
58 views

Inverse modulo without brute force [closed]

I have this piece of code and I want to know 'x' before the loop without brute force. Is there a way to do an inverse modulo or something? ...
0
votes
0answers
16 views

How to compute the logarithm of a computable number

Let's say you have a computable number $x>0$. $\ln(x)$ is computable as well. Given the computability of $x$, what is a computation for $\ln(x)$. I am using the definition where $a$ is computable ...
3
votes
0answers
21 views

Finding a cycle in a directed graph, however…

Say we have some directed graph, G. Every now and then, I can add either: a single arc from an existing vertex to another existing vertex (but no self-loops), add one new vertex with an arc to an ...