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)

1
vote
3answers
205 views

Common algorithm with an order of Θ(2^n)

What would be a common algorithm with an order of Θ(2^n)? When I say "order", I mean time complexity analysis. I was thinking exponential growth but are there any that are more computer science ...
10
votes
3answers
925 views

Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
3
votes
2answers
194 views

How can I generate a random DFA with uniform distribution?

I need to generate a Deterministic Finite Automata (DFA), selected from all possible DFAs that satisfy the properties below. The DFA must be selected with uniform distribution. The DFA must have ...
0
votes
1answer
433 views

balanced 2-partition with equal cardinality (cardinality difference = 1 (max))

Given a set $S$ of $N$ numbers, my aim is to partition it into two sets ($S_1$ and $S_2$), so that (i) the difference $\sum S_1 - \sum S_2$ is minimized and (ii) the difference $|S_1| - |S_2|$ is ...
2
votes
2answers
2k views

Add nautical miles to latitude and longitude decimal notation

What is the easiest way to add a set number of nautical miles to a known latitude and longitude? I am writing a program in C# that takes a point of origin in decimal notation: 33.4483333, ...
2
votes
4answers
177 views

Is this a kind of Permutation?

I'm trying to design an algorithm to generate something that I don't know how exactly to call! Ok, I'm not a mathematician, I'm studying computer science and thought this would be a great moment to ...
1
vote
2answers
238 views

Algorithm for shifted center of mass calculation

Imagine that we have a set of points with defined x coordinate and mass for each of them: {($x_i$, $m_i$)}. Canonical center of mass is a point $x_0$ that divides points to the left ones and the ...
2
votes
2answers
144 views

How to find the lowest cost supplier-product mix?

I was given a Excel spreadsheet with this table: The user wants to find the lowest price mix amongst the various suppliers. The user wants to constrain the number of products that each supplier ...
0
votes
1answer
92 views

Iterative algorithm with O(n)

$T = \{t_1,t_2,\dots,t_n\} $. while $t_1,\dots,t_n \in \mathbb N$ with $t_i < t_j$ for $i < j$. For each $t_1,\dots,t_n$, there is another value - Price. for example, for $t_1$, the price is ...
1
vote
1answer
668 views

How to convert a recurrence relation to a non recursive function

How does one convert a recurrence relation to a non-recursive function? I am not sure about the substitution, recursion tree, and master method. Is there an easy way to do this?
1
vote
3answers
457 views

“Least” common multiple of A and B, greater than C

Least common multiple of $A$ and $B$ that is greater than $C$. Is there any algorithm to find it without prime factorization?
5
votes
4answers
173 views

Algorithm for randomly choosing learning cards

I'm programming a learning software. It works with question-/answercards. I´m searching for a algorithm that gives me a higher probability for cards that the user has answered wrong. My actual idea ...
2
votes
0answers
35 views

What is this method called of calculating corrections for calculated values from measured values?

I am dealing with a piece of software which calculates temperatures, and corrects these based on measurements (which may be in error) as follows:- The difference between the corresponding calculated ...
12
votes
1answer
4k views

Is it faster to multiply a matrix by its transpose than ordinary matrix multiplication?

I'm writing a program that multiples a matrix by its transpose, and was trying to find efficiency hacks I could exploit considering that the two matrices being multiplied are related. Any ideas?
41
votes
1answer
1k views

Sums of prime powers

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum? For concreteness, you ...
1
vote
2answers
116 views

Non-Standard Deviation

Given a list of integers, how to find the sum of the differences of all possible pairs of numbers ? For example if the number are $3,1,2$ then, answer should be $$\lvert 3-1 \rvert + \lvert 3 -2 ...
1
vote
3answers
309 views

Can you help me translate this programming algorithm into mathematical language? Has prior work been done on the “LFSR” problem already?

There is this programming/mathematical problem I have; it is the problem of generating a sequence of n unique random numbers, where the random number $n$ is element of of the set $S = \{0, 1, 2, ...
3
votes
1answer
186 views

Finding SVD efficiently for $AB^T$

I posted this on cs theory yesterday but did not get an answer and hence I am posting here. I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ ...
2
votes
1answer
264 views

Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that: $L(M) = ...
2
votes
1answer
729 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
672 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
308 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
229 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
116 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
324 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 ...
5
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
292 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 ...
23
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
129 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
1k 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
119 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
2k 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
306 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
424 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
240 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
782 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
746 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
86 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
122 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
73 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
613 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
51 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
7k 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 ...