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)

7
votes
1answer
379 views

Algorithm for scrolling through different orbits in a permutation group

Given an $n\in\mathbb{N}$, and a permutation $\pi\in S_{n}$, denote the centralizer of $\pi$ by $C_{\pi}$. Now we can look on the conjugation action of $C_{\pi}$ on $S_{n}$ and then divide $S_{n}$ to ...
6
votes
1answer
105 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
6
votes
1answer
948 views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
6
votes
1answer
230 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
6
votes
2answers
1k views

How/why does this noise function work?

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

Extended Euclidean algorithm with negative numbers

I feel very sorry for asking probably simple and stupid questions on such a site, but a reasonable justification may be that smart answers to stupid questions will vaporize stupidity in the end and ...
6
votes
1answer
1k views

Algorithm for computing square root of a perfect square integer?

My question is the following: Is there a polytime non-numerical algorithm for computing square root of perfect square integers? The more elementary the algorithm is, the better! EDIT: ...
5
votes
1answer
223 views

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed? We define $f(n)=m$ where the digits of $m$ and $n$ are reverse. Such as ...
5
votes
1answer
185 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
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
1answer
1k views

Why is sorting pancakes NP hard?

An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with ...
4
votes
2answers
274 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
251 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
924 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
376 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
12k 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
334 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
563 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
100 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
3
votes
2answers
162 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
93 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
611 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
87 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
0answers
124 views

Minimum Sum that cannot be obtained from the 1…n with some missing numbers

Given positive integers from $1$ to $N$ where $N$ can go upto $10^9$. Some $K$ integers from these given integers are missing. $K$ can be at max $10^5$ elements. I need to find the minimum sum that ...
2
votes
1answer
48 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
60 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
7k 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
116 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
195 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
153 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
368 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
344 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
2answers
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
458 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
573 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
991 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
137 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
124 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
55 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
70 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
2answers
76 views

Does anyone know of any open source software for drawing/calculating the area of intersection of different shapes?

I would like to be able to draw any number of different shapes and determine the area of their intersections. I'm looking for free, open source software. I thought about trying to code something up ...
1
vote
1answer
68 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
139 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 ...