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)

2
votes
1answer
794 views

Floyd's algorithm for the shortest paths…challenging

If anyone has some insight on how to do this it would be very much appreciated.
5
votes
2answers
734 views

FFT of waveform with non-constant timestep

I have a waveform which I would like to take the fourier transform of. However, the simulator which generated the waveform uses an adaptive algorithm to determine the timestep for each calculation. ...
7
votes
0answers
312 views

Does this calculation have a name, or a generic formulation?

Background I would appreciate help in identifying / explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: sample from the distribution of each of $i$ parameters, $\phi_i$ ...
0
votes
1answer
232 views

Is there a generalization of Strassen algorithm?

Let $A$ and $B$ be $n \times n$ matrices. Strassen's algorithm for multiplication works on a partitioning of $A$ and $B$ into $2^2$ submatrices each. Is there any generalization of Strassen's ...
2
votes
1answer
118 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
370 views

Counting digits in an arithmetic sequence

Given $a, d, n, x$. Suggest me a suitable algorithm to compute the number of times the digit $x$ appearing in the arithmetic sequence $a, a + d, a + 2 \times d, \cdots, a + n \times d$. For ...
6
votes
2answers
3k views

How do you check if a sequence of numbers is truly random? [duplicate]

Suppose a source produces an indefinite sequence of positive integers. How can you check whether the numbers are generated truly randomly?
1
vote
3answers
1k views

Center of gravity of a self intersecting irregular polygon

I am trying to calculate the center of gravity of a polygon. My problem is that I need to be able to calculate the center of gravity for both regular and irregular polygons and even self intersecting ...
1
vote
0answers
308 views

Partition of graph into independent sets of consecutive vertices

Sorry for my English. Here is the question: $G=(v,e)$, undirected graph, $V=\{v_1,v_2,\ldots,v_n\}$. the vertices are organized in sequence from the smaller one to the biggest $v_1,\ldots,v_n$. We ...
25
votes
2answers
2k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
2
votes
4answers
2k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
4
votes
1answer
134 views

algorithm to dynamically monitor quantile(s)

I want to estimate the quantile of some data. The data are so huge that they can not be accommodated in the memory. And data are not static, new data keep coming. Does anyone know any algorithm to ...
3
votes
2answers
2k views

How do I write this proof more formally?

So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree. My Proof: If the graph has unique edge weights, we can ...
0
votes
1answer
121 views

Minimize $\sum f(p_i)$ for given $\prod p_i$

A signal which is a function of a set of periodic signals with periods $p_1,\dotsc, p_n$ will have a period $P$ which is the least common multiple of all $p_i$. (If $p_i$ are relatively prime, which ...
11
votes
4answers
3k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
4
votes
1answer
307 views

Is there any mathematical trick?

Given two natural numbers I am supposed to reverse each of them and then sum them up and reverse the sum to get the final answer. For example if the numbers are $4358$ and $754$ then the answer ...
1
vote
2answers
483 views

Running 'Encrypted Code' on a Computer

Alice released a new version of her software for removing red-eye from pictures. However, she wants to protect her secret algorithm from disassemblers and such while still letting her customers remove ...
1
vote
1answer
260 views

Efficient calculation of polynomial product

I have 2 polynomials $p_1(x_1,\ldots,x_n)$ and $p_2(x_1,\ldots,x_n)$, of which I have to compute the product, with a special property: The exponent of each variable is always either $0$ or $1$, where ...
1
vote
1answer
70 views

Reversibly Combining Very Large

How can I reversibly combing two very large numbers, such as 9,828,485,546,536,174,656,640,115,183 and 43,044,700,185? I need them to be combined into a single number, and the order of the numbers ...
3
votes
2answers
806 views

Proving the bound on a recurrence relation

I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$ My attempted solution: \begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 ...
5
votes
4answers
772 views

How can I change the Conway's Game of Life so that, eventually, all cells die?

Darwinia features an intro which represents a modified version of Conway's Game of Life. You can see it in action here. The game developers added one more rule about the game: no cell may live ...
3
votes
1answer
90 views

Given a set of 2D points (x,y) (cloud of points), find the points that, when connected, will contain all other points

Given a set of 2D points I have to find the points that when connected will form a polygon that contains all the points in the set. A quick example: imagine you have a set ...
1
vote
1answer
124 views

Integer solutions of nonhomogeneous linear inequalities

I am trying to solve a problem which I have reduced down to find out one of integer solutions to a number of nonhomogeneous linear inequalities. Can this be done efficiently ? If so: how?; if not: ...
1
vote
1answer
2k views

Solving systems of linear congruences (modular equations)

This is a task from an old programming contest the task is as follows, A list of system of linear equations is given in the inputs.If the system is solvable we have to output the solution in the form ...
2
votes
1answer
2k views

Question on Solving a Double Summation

$$ \sum_{i=0}^{n-2}\left(\sum_{j=i+1}^{n-1} i\right) $$ Formulas in my book give me equations to memorize and solve simple questions like $$ \sum_{i=0}^{n} i $$ ... However, For the question on top, ...
1
vote
6answers
1k views

Why is the number of possible subsequences $2^n$?

If anyone here is familiar with the Lowest Common Subsequence problem, they probably know that the number of posibble subsequences in a sequence is $2^n$; $n$ being the length of the sequence. ...
2
votes
1answer
74 views

Calculating the “most balanced” scenarios of a game?

Figured you math dudes (and dudettes) could knock this one out of the park! I've got a website that stores users' game scenario results. Each scenario record can have one of three possible results: ...
1
vote
1answer
671 views

Independent Set decision problem in P

If P=NP, is there a polynomial-time algorithm $A$ that can decide the $\text{Independent Set}$ decision problem? That is, with an undirected graph $G = (V, E)$ and a positive integer $k$, does $G$ ...
2
votes
1answer
157 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
1answer
52 views

Maximum distance in cycle interval

Perhaps this is a very basic question, but I can't find a fast solution. I have a cyclic interval [0,n] (distance from n to 0 is 1). I need a function that for a given value x returns the point in ...
9
votes
2answers
8k views

Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then. The way I ...
5
votes
1answer
2k views

How to check if a integer is a power of some integer?

Given a integer $n$, we want to know if $n=m^k$ for some $m$ and $k>1$. What is the fastest method? (Suppose the factors of $n$ are not given). The best method I can think of is to try to ...
2
votes
1answer
327 views

How to prove that this sequence converges?

I created a certain algorithm and now I try to prove it's convergence. Here is the essence of the algorithm: Given are finite sets $A_i$, positive constants $\alpha_a$, and a sequence $ ...
2
votes
2answers
355 views

Algorithm complexity in for loop

I have an algorithm and I would like to know how many times each line is called. There I wrote which lines I understand and some lines is left. ...
2
votes
2answers
347 views

Finding GCD of all permutations of a decimal number [duplicate]

Possible Duplicate: Computing GCD of all permutations (of the digits) of a given number. How can we find the greatest common divisor (GCD) of all numbers that can be obtained by permuting ...
3
votes
1answer
102 views

An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$ Each $P_i$ is a polynomial of at most three variables ...
9
votes
2answers
708 views

Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
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 ...
2
votes
1answer
1k views

How to evenly distribute squares in a rectangular area?

Hi i need to figure out how can i add given number of squares in a rectangle i want to create this. http://i.stack.imgur.com/MHoda.jpg The whole scenario is to create a function that take a number ...
2
votes
1answer
110 views

Exp function in an averaging algorithm

I was looking at some source code that was described as 'maintaining a moving average over the previous 10 minutes', and noticed it uses the exponential function. Now its been a while since my ...
1
vote
2answers
1k views

What is an efficient algorithm to compute modular exponentiation of stacked exponents?

Given $a^{b^c}\mod p = x$, where $a,b,c$ are real positive integers and $p$ is a prime, what is the most efficient algorithm to compute $x$ (ideally in polynomial time)?
1
vote
1answer
1k views

Fastest way to compute HCF of 2 numbers

I want a very quick non recursive method for finding the HCF (Highest Common Factor) of 2 very large numbers
6
votes
1answer
418 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
3
votes
2answers
5k views

What's the fastest way to take powers of a square matrix?

So I know that you can use the Strassen Algorithm to multiply two matrices in seven operations, but what about multiplying two matrices that are exactly the same. Is there a faster way to go about ...
6
votes
3answers
3k views

Calculate variance from a stream of sample values

I'd like to calculate a standard deviation for a very large (but known) number of sample values, with the highest accuracy possible. The number of samples is larger than can be efficiently stored in ...
2
votes
1answer
343 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
3answers
900 views

Converting recursive function to closed form

My professor gave us a puzzle problem that we discussed in class that I could elaborate on if requested. But I interpreted the puzzle and formed a recursive function to model it which is as follows: ...
3
votes
3answers
2k views

maximum number of collinear points?

I know this is a very standard question widely popular in the Internet and the Mathworld. I myself have solved the above problem is N^2 Log N avoiding floating arithmetic.However, can anyone give me a ...
0
votes
5answers
505 views

How to evaluate $\displaystyle\sum_{i=1}^{n/2}1$

I am trying to measure complexity of the following code segment int sum = 0; for (int i = 1; i <= n/2; i++) { sum++; } As far as I understand it can be ...
0
votes
1answer
846 views

Logarithm base 2 and factorials

I'm learning about $\log_2$ for an algorithms class and theres a problem in the book that is confusing me. It asks: Find a formula for $\log_2(n!)$ using Stirling's approximation for $n!$, for large ...