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)

5
votes
1answer
184 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
5
votes
1answer
324 views

Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's ...
5
votes
1answer
7k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
5
votes
2answers
991 views

How/why does this noise function work?

How/why does this noise function work? ...
4
votes
2answers
271 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
4
votes
2answers
6k views

How to solve this recurrence $T(n) = 2T(n/2) + n\log n$

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
4
votes
1answer
238 views

Reasoning the calculation of the Hilbert's distance

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data ...
4
votes
4answers
896 views

Calculation of Bessel Functions

I want to calculate the Bessel function, given by $$J_\alpha (\beta) = \sum_{m=0}^{\infty}\frac{(-1)^m}{m!\Gamma(m+\alpha +1)} \left(\frac{\beta}{2}\right)^{2m}$$ I know there are some tables that ...
4
votes
3answers
374 views

First Course in Linear algebra books that start with basic algebra?

I'm 30 years old, and the only math I can remember from college is basic algebra and some probabilities. Next month, I have a machine learning project I'd like to work on, but I'll need a solid ...
4
votes
5answers
11k views

Merge Sort time complexity analysis

How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?
4
votes
3answers
322 views

Is there an algorithm to find the roots of high-order polynomials?

It is not generally possible to determine the roots of a polynomial whose grade is bigger than 4 in terms of roots and basic operations. But I heard, that it is possible to give a criteria whether a ...
4
votes
3answers
116 views

Congruence of terms

There is concept of Term Rewriting. If one have rules for rewriting terms, one can obtain some term from another. For example, rule1: a -> f(b); rule2: b->t. Term A(f(t)) can be obtained from term ...
4
votes
1answer
556 views

How can I pack $45-45-90$ triangles inside an arbitrary shape ?

If I have an arbitrary shape, I would like to fill it only with $45-45-90$ triangles. The aim is to get a Tangram look, so it's related to this question. Starting with $45-45-90$ triangles would be ...
3
votes
1answer
97 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
3
votes
2answers
140 views

splitting polygon in 4 equal parts

I have a convex polygon and I want to divide into 4 equal parts using the two perpedicular splits. Like in a picture. I need s1 = s2 = s3 = s4; I need to get coordinates of point where the lines ...
3
votes
1answer
83 views

Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$

Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$. Given $n+1$ values ...
3
votes
3answers
601 views

How to find a “simple” fraction between two other fractions?

If we have two fractions $a = { a_1 \over a_2} $ and $c = {c_1 \over c_2}$ with $a<c$, how to find the fraction $b = { b_1 \over b_2 }$ , $a < b < c$ for which some measure of ...
3
votes
1answer
85 views

Authoritative measure for rating photos in a photo contest - practical issue

I am trying to find a good algorithm that would serve as an authoritative way to assess pictures provided for a photo contest. There is a bunch of photos that came for the contest. Each person from a ...
3
votes
2answers
2k views

How to construct magic squares of even order

Could someone kindly point me to references on constructing magic squares of even order? Does a compact formula/algorithm exist?
3
votes
3answers
2k views

“Closest pair of points” algorithm

I'm having a problem understanding why I just have to consider the next 7 points in the Closest pair of points - algorithm. Can someone explain it in greater detail?
2
votes
1answer
45 views

Weights - Objects into bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1 , a_2 , ··· , a_n$ into $k > 1$ bags. For each $i = 1 , 2 , ··· , n $, the weight of $a_i$ is $w_i$ ...
2
votes
0answers
58 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
2
votes
3answers
6k views

Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
2
votes
0answers
110 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
1answer
186 views

Sort vectors according to their distance between them

I have a collection of vectors, let`s say $n$ vectors. I am trying to find an easy way to SORT these vectors in that way that after sorting of vectors $(V_1,V_2,...,V_n)$ the first vector $V_1$ and ...
2
votes
1answer
151 views

It seems like a nim variant

Now this is a more of a computer science problem than a math problem but it is concerning game theory and it does seem a lot like nim (it's from an online judge), so i'm kinda stuck on this one i'd ...
2
votes
1answer
353 views

Polynomial complexity algorithm of partition problem with sets of equal size

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ). Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
2
votes
2answers
328 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
1answer
2k views

Block Diagonalizing an antisymmetric matrix

I was wondering how to block diagonalize a $10\times10$ antisymmetric matrix into block matrices along the diagonal. Can I just diagonalize each non-diagonal block? Thanks!
2
votes
0answers
457 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
3answers
554 views

How can I solve $8n^2 = 64n\,\log_2(n)$

I currently try to analyze the runtime behaviour of several algorithms. However, I want to know for which integral values $n$ the first algorithm is better ($f(n)$ is smaller) and for which the second ...
2
votes
3answers
964 views

Finding location of a point on 2D plane, given the distances to three other know points

I need to find location of the point $s_0$; the locations of other three points ($s_1$, $s_2$, $s_3$) are known. $d_i$ are known distances. Given: $x_1$, $x_2$, $x_3$, $y_1$, $y_2$, $y_3$, $d_1$, ...
2
votes
3answers
131 views

Finding a (small) prime great enough that there are at least m elements of order m

I'm hoping that someone can provide me with some results or point me in the right direction. I'm working with finite fields; really, I'm just doing arithmetic modulo a prime $p$. I'm taking elements ...
2
votes
1answer
113 views

Contour plotting algorithm compliant with breaks and discontinues

Good day, Does anybody know where I could find a recursive contour plotting algorithm which is compliant with breaks and discontinues in the objective function? Recursive subdivision should be done ...
2
votes
1answer
333 views

clarification on Chernoff's inequality

i'm studing probabilistic algorithms: the ones that - with a great gain in efficency - sometimes could return a false response. They return the true response with a probability of $\frac{3}{4}$. The ...
2
votes
2answers
136 views

Development of a specific hardware architecture for a particular algorithm

How does a technical and theoretical study of a project of implementing an algorithm on a specific hardware architecture? Function example: ...
1
vote
1answer
123 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
1
vote
1answer
46 views

Why does this algorithm to plot implicit equations work?

This may be an obvious question, but I can't seem to figure it out. I found an algorithm that receives an equation, and in order to plot its graph, for each pixel in the screen, it will replace the ...
1
vote
1answer
66 views

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
1
vote
1answer
67 views

Finding Required Permutation

I have numbers from $1$..$n$. I want to find number of permutation from all $n!$ permutation where the numbers have following arrangement. $L$ $G$ $L$ $G$ $L$ or $G$ $L$ $G$ $L$ $G$. Where L means ...
1
vote
2answers
133 views

GCD and LCM of three numbers

Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L? gcd(x, y, z) means the greatest common divisor ...
1
vote
1answer
53 views

Proof with $\Theta$

I am having a hard time proving the following statement: Suppose that the functions $f_1, f_2, g_1, g_2 : \mathbb{N} \rightarrow \mathbb{R}^{\ge 0}\ are \ such \ that \ f_1 \in \Theta (g_1) \ and ...
1
vote
2answers
260 views

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out :( There are T(0) = d and T(1) = e, Thanks in advance.
1
vote
3answers
190 views

Fermats Little Theorem

I need help in the use of Fermat’s Little Theorem, in order to calculate the remainder of $5^{120}$ when divided by 19. Thank you.
1
vote
2answers
69 views

How can we find a new sum of multiplications based on a previous one?

Suppose wehave two sequences: $$(a_0, a_1, a_2, \dots, a_{2^n-1})$$ $$(b_0, b_1, b_2, \dots, b_{2^n-1})$$ We also have the following sum: $$\sum_{k=0}^{2^n-1}{a_k \cdot b_k}$$ I'd like to know the ...
1
vote
2answers
241 views

A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$. I am inquisitive about how to approach this one?
0
votes
2answers
37 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
0answers
75 views

Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
0
votes
2answers
197 views

Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$

I want to Arrange the following growth rates in increasing order This order are following : $O (n (\log n)^2), O ((35)^n), O(35n^2 + 11), O(1), O(n \log n)$ Please give me idea how to arrange growth ...
0
votes
3answers
425 views

Subtracting two dates

I'm developing a software and I need to subtract two dates and then get a date again. I've been trying to solve this problem for a while and I have found some additional problems. One of these ...