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
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
48 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
316 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
39 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
23 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
60 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
48 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
33 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
32 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
36 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
23 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
25 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
41 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
22 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
40 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
38 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
41 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
46 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
51 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
66 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
67 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
43 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
34 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
24 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
17 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
33 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
62 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
741 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
42 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
17 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
22 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 ...
1
vote
2answers
60 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
0
votes
1answer
49 views

How to finish this proof by contradiction?

The Problem: You were planning to study real hard this quarter so you took out n books on algorithms. However you had better planning than execution and you have not read a single book and they are ...
1
vote
2answers
30 views

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
0
votes
3answers
57 views

Multiplying array elements

We are given a sorted array containing elements at indices $x_1,x_2,x_3,x_4,....x_n$. We have to find the product $\displaystyle\sum_{i,j,k}x_ix_jx_k$ where $j\geqslant i$ and $k\geqslant j$. For ...
0
votes
0answers
24 views

Determine complexity of algorithm

I have two pieces of code below. a) sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++ ; b) ...
0
votes
1answer
52 views

Fractional Knapsack- explanation

The following algorithm is given: ...
0
votes
1answer
60 views

Complexity of Least Common Multiple

I would like to know the complexity of computing the least common multiple of $n$ natural numbers. Does it depend on Euler's totient function?