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)

0
votes
1answer
175 views

Cells counting problem

There is a 3D grid with cells for which we define its value (0 or 1) as F(i,j,k)=F(i-1,j,k) XOR F(i,j-1,k) XOR F(i,j,k-1), base cases are ...
6
votes
2answers
4k views

Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?

This definition is extracted from "Introduction to Algorithm, 2nd Edition". The iterated logarithm function We use the notation $\lg^* n$ (read "log star of $n$") to denote the iterated ...
4
votes
4answers
179 views

How to prove this approximation of logarithm of factorial

In other words, how to prove this equation $$\lg{n!} = \Theta(n\lg{n})$$
1
vote
2answers
2k views

algorithm explanation for card trick

I have been studying algorithms for a project im developing, and found this card trick, can any matemathical guru help me understand the algorithm behind?? card trick thanks a lot!
1
vote
1answer
834 views

How to describe an algorithm with mathematical notation?

I often have to create new computer science algorithm. The problem come when I have to describe them in a scientific way. I don't know where I should look for to learn how to describe my algorithms ...
1
vote
2answers
90 views

Valued permutation

Here is original problem. Problem: there are 2 parallel arrays of positive floating point numbers A (Ai < 1000) and ...
1
vote
0answers
520 views

Applications of Convergence of a series in Algorithms

We were introduced to testing the convergence of a series & calculating the point of convergence in the first maths of college curriculum. I wish to explore its usage in computer algorithms. ...
2
votes
1answer
190 views

What's wrong with my writing in Prem algorithm?

Solved by fixing program I discover lead coefficient should include other variables now it stop infinite loop but result not correct i am near the answer $yz^6+2y^2z^4+5y^3$ the difference is my ...
6
votes
1answer
3k views

Split a set of numbers into 2 sets, where the sum of each set is as close to one another as possible

Given a set of numbers, I'd like to split this set into 2 sets, where the sum of each set is as close to equal as possible. How would I go about doing this in a programmatic way? Thanks in advance ...
5
votes
2answers
1k views

non time constructible functions

A function $T: \mathbb N \rightarrow \mathbb N$ is time constructible if $T(n) \geq n$ and there is a $TM$ $M$ that computes the function $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ in ...
1
vote
0answers
195 views

Minimize submatrix having the same number of distinct columns as given matrix

Let M be an n by m matrix. For a subset S of {1,...,n} let M(S) be the submatrix of M with row indices in S. I would like to find an S of smallest size such that M(S) has the same number of distinct ...
7
votes
1answer
143 views

Bounds on the gaps in a variant of polylog-smooth numbers.

Sorry for the long intro. I think the explanation motivates the question and puts it in context. But if you want to skip the story, then just move on to the grey boxes; they should contain enough ...
2
votes
1answer
223 views

Maximal mapping of a convex set to the unit disk

EDIT: To make my question more precise i think we can narrow it down to this. Say you have a simple polygon that includes the origin, that is completely contained in the unit disk, we can 'blow up' ...
7
votes
1answer
236 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 ...
4
votes
5answers
14k views

Merge Sort time complexity analysis

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

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for ...
0
votes
1answer
1k views

Determine whether or not a point lies within a rotated rectangle

I need some maths help for a 2D game I am programming. In this game I have a rectangle, specified by its centers' X and Y coordinates, and its width and height. I then rotate this rectangle via ...
1
vote
0answers
234 views

Intersection and union of 2 variable intervals with integers and indexes

I have a set of indexes of integer $\mathbb{I} =\{i_0, i_1, ..., i_n\}$, and an environment $f: \mathbb{I} \rightarrow \mathbb{Z} \times \mathbb{Z}$ which assigns a pair of integer to each index. For ...
1
vote
2answers
2k views

Easy approximation of the incomplete beta function $\text{B}_x(a,b)$

I need to calculate $\text{B}_x(a,b)$ on the cheap, without too many coefficients and loops. For the complete $\text{B}(a,b)$, I can use $\Gamma(a)\Gamma(b)/\Gamma(a+b)$, and Stirling's approximation ...
1
vote
0answers
1k views

Teach me a simple, efficient division algorithm

I want to implement arbitrary-precision arithmetic in JavaScript for non-negative integer numbers. Long division isn't efficient if instead of the usual 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) there ...
0
votes
3answers
82 views

Splitting a multiplication into multiple smaller steps, reaching the same result

Suppose I have a number, x, which should be doubled every second. If one had a function which is called exactly once every second, the solution would be simple: All you would have to do was ...
1
vote
2answers
2k views

Jacobian matrix

Please help me to determine the Jacobian matrix of $n$ functions with $n$ parameters with C++. I know MATLAB has the possibility to determine the Jacobian matrix by using ...
4
votes
1answer
147 views

Deterministic algorithm for matching variables by only using restricted comparison

The problem can be stated as the following: Given a sequence of numbers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ such that $\{b_i\}_{i=1}^{n}$ is a permutation of $\{a_i\}_{i=1}^{n}$, find an ...
9
votes
4answers
819 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
3
votes
2answers
462 views

Algorithm for bipartite graph

I need an algorithm for finding in a bipartite graph a matching saturating all vertices of maximum degree. How do I come up with such an algorithm?
12
votes
4answers
2k views

Can an algorithm be faster than O(1)?

This week we had a bright interviewee who claimed that array has constant search time and map has even faster than that search time. Now to me if some algorithm has O(1) time complexity the only way ...
6
votes
1answer
282 views

Can we evaluate the any single decimal digit of pi even we skip the digit before it?

Can we evaluate any single decimal digit of pi even we skip to evaluate the digit before it?
3
votes
0answers
265 views

Taking Square Roots of Matrices over Z/nZ

Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? If the matrix is diagonalizable, then does diagonalizing and taking the square roots work? ...
8
votes
3answers
408 views

Understanding AKS

new user here. Where does a layman go to get a basic understanding of AKS primality testing. I am not talking about the optimal choice of "r" (which I am told is the hardcore number theoretic part of ...
3
votes
5answers
529 views

Best algorithm for calculating lists of neighbours

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
2
votes
1answer
3k views

Can Cox-de Boor recursion formula apply to B-splines with multiple knots?

We know that Cox-de Boor recursion formula can be used to compute the B-spline basis function. $$ N_l^n(u)=\frac{u-u_{l-1}}{u_{l+n-1}-u_{l-1}}N^{n-1}_l(u)+ ...
3
votes
3answers
3k views

Probability Calculations on Highway

I read this Google Interview Question. Q:If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default ...
2
votes
3answers
132 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 ...
1
vote
2answers
2k views

Bellman-Ford algorithm: why V-1 number of relaxation iterations?

Why does Bellman-Ford algorithm perform V-1 number of relaxation iterations? I feel that it is correct when going through examples. But how do we explain it for the general case? I have gone through ...
3
votes
1answer
218 views

Generating elements of the free group of rank two up to conjugacy

I've tried to google how to generate words in two generators up to conjugacy (this means I only want one representative for each conjugacy class). Sadly, I come up with articles that have, in the ...
0
votes
2answers
273 views

An exponential function between zero and one

Alrighty, math noob here, so be nice :P. We're building an app and need an exponential function that exists between zero and one, and, depending on the importance we give it, will fluctuate between ...
0
votes
1answer
118 views

Lattice Reduction of two matrix

I have two matrices A, B with same number of rows. I want lattice reduction on B. During this reduction, I change rows of A accordingly. That is if i-th row and j-th row in B interchanges, swap i-th ...
6
votes
1answer
150 views

Finding the closest match in a “golden” sequence of points

I am not a mathematician, and corrections are welcome (including tags). Background: For the last few days, i have been interested in the problem of placing points along a line segment (of length ...
2
votes
1answer
64 views

Any algorithms that can ensure category diversity in a social ranking system?

I'm building a system similar to Reddit, where users "like" items. "Likes" would be used to determine ranking of items. There's also an "aging" factor, where more recent "likes" count more than ...
4
votes
5answers
12k views

Determining if an arbitrary point lies inside a triangle defined by three points?

Is there an algorithm available to determine if a point P lies inside a triangle ABC defined as three points A, B, and C? (The three line segments of the triangle can be determined as well as the ...
0
votes
2answers
2k views

Computer Algorithm Running Time Calculation

I have the following pseudocode to figure out the approximate running time of. Anyone able to help but please explain each step and reason. thanks in advance ...
1
vote
1answer
334 views

Number of operations in grade school algorithm for multiplying 577 and 423

Given 577 x 423 with grade school algorithm you calculate 577 x 3 = 1731 577 x 2 = 1154 577 x 4 = 2308 These are 3 multiplications of a number by a single digit. Then, you go on and add 1731 + ...
2
votes
1answer
234 views

Function for base-stock level

This problem is work related not school related. I am developing a simple inventory management system to solve a digital supply chain problem and I need help with an algorithm to control the ...
2
votes
1answer
392 views

Smallest subsequence with desired sum of complexity n and n logn

Given a sequence of integers ( +ve and/or -ve) $A_1, A_2, \ldots, A_n$, I need to find the smallest subsequence $A_i,\ldots, A_j$ whose sum is at least M. How would the algorithm for the same go if I ...
0
votes
2answers
127 views

Calculating Running Time 101

I need to learn how to prove/disprove each of the following. Anyone able to do it in very simple way for a NON -mathematician to easily understand? ( NB -- NOT HOMEWORK) a) $$n^2 + n + 1 = \Theta ...
0
votes
2answers
966 views

Partition Problem, verifying solution in polynomial time

I add a look at the partition problem, this problem is know as the Easiest hard problem since it is NP-complete and seems pretty easy. From wikipedia on NP-complete: In computational complexity ...
1
vote
2answers
94 views

What graph theoretic methods which can identify groups?

Given a social graph, for instance, from Twitter, I want to identify groups. Here I define groups as any highly connected (although not necessarily complete) subgraph. What algorithms or methods ...
3
votes
2answers
195 views

Algorithm to check if a polynomial is positive in a given interval

I'm writing a program where I have a 3-dimensional polynomial (3 variables) of which I have to check if it is positive in a given product of 3 intervals (a volume). I found a paper which solved this ...
3
votes
2answers
458 views

Algorithm to determine if a Diophantine Equation has an infinite number of solutions

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether ...
3
votes
0answers
235 views

Approximation of a real number as a linear combination of two reals with coprime integral coefficients

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, give me an algorithm that will provide coprime integers $a$ ...