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)

2
votes
1answer
193 views

how to generate all possible equations with a set of number and operators?

i got a maths problem, for given that a set of character {1,2,3,4,5,6,7,8,9,+,-,*,/}. and then by using the set of characters to randomly generate 10(or let say N) characters in an array, i.e. ...
2
votes
1answer
156 views

Are there any sets other than the usual in which we can apply Sturm's axioms?

As we all know, Sturm's axioms have completely solved the problem for finding the number of roots in an arbitrary interval $[a,b]$, using the derivative and forms a Sturm set. Now my question ...
1
vote
2answers
198 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
1
vote
2answers
259 views

Most Efficient Method to Find Roots of Polynomial [duplicate]

I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
1
vote
2answers
83 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
2answers
4k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
1
vote
1answer
202 views

Finding the topological genus of a triangulated surface

Given is a surface represented through a triangle mesh (as commonly used in computer graphics, with vertices, edges and faces). The surface is known to be "watertight", i.e. no missing faces. Is ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
0
votes
2answers
935 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 ...
-9
votes
2answers
183 views

Prove that this recurrence relation algorithm generates all positive rational numbers, and does so without repetition and in reduced form [closed]

For $n\ge 1$, generate a sequence $\{a_n\}$ such that for any even $n = 2k$: $$ a_n = a_k$$ And for any odd $n=2k+1$: $$ a_n = a_k + a_{k+1}$$ With initial conditions $a_1 = a_2 = 1$ Now, generate a ...
10
votes
2answers
130 views

Non-revealing maximum

How can a group of people find out their maximum age without revealing any other information to each other? (Is there a book or web site about such non-revealing algorithms?) Preferably I'm looking ...
10
votes
1answer
406 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 ...
8
votes
1answer
3k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
8
votes
1answer
2k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
7
votes
0answers
369 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
7
votes
1answer
8k 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'? ...
7
votes
1answer
381 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 ...
7
votes
1answer
234 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
1answer
123 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
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 ...
6
votes
1answer
1k 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
2answers
1k views

How/why does this noise function work?

How/why does this noise function work? ...
6
votes
2answers
5k 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
1k views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
5
votes
1answer
227 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
188 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 ...
4
votes
2answers
285 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
1answer
270 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
990 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
5answers
13k 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
346 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
119 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
571 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
126 views

Knuth's algorithm for Mastermind question

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm). I ...
3
votes
1answer
108 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
3
votes
2answers
193 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
102 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
2answers
180 views

Sum of multiplication of all combination of m element from an array of n elements

Suppose I have an array {1, 2, 3, 4} and m = 3. I need to find: ...
3
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!
3
votes
3answers
648 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
4k views

Can QR decomposition be used for matrix inversion?

Is there any simple algorithm for matrix inversion (that can be implemented using C/C++)? Can QR decomposition be used for matrix inversion? How?
3
votes
1answer
91 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
3k 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?
2
votes
0answers
152 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
49 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
65 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
10k 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
129 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
2answers
5k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...