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)

7
votes
0answers
313 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$ ...
7
votes
1answer
239 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
6answers
3k views

Calculate $\pi$ to an accuracy of 5 decimal places?

In this message at point 18 I saw following programming question: Given that $\pi$ can be estimated using the function $4(1 – 1/3 + 1/5 – 1/7 + \ldots)$ with more terms giving greater accuracy, ...
6
votes
5answers
207 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
6
votes
5answers
303 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
6
votes
3answers
3k views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
6
votes
2answers
2k views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
6
votes
4answers
2k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...
6
votes
3answers
2k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
6
votes
3answers
6k views

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
6
votes
3answers
23k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
6
votes
1answer
564 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
6
votes
2answers
1k views

Lights Out Variant: Flipping the whole row and column.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so: 1 0 0 00 0 0 00 1 0 0 0 0 1 0 When you selected a ...
6
votes
2answers
555 views

Algorithm fot planarity test in graphs

I am implementing a graph library and I want to include some basic graph algorithms in it. I have read about planar graphs and I decided to include in my library a function that checks if a graph is ...
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 ...
6
votes
5answers
13k 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 ...
6
votes
5answers
298 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
6
votes
4answers
216 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
6
votes
2answers
639 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
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 ...
6
votes
4answers
506 views

Algorithm for constructing primes

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$? There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking ...
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
2answers
7k views

Continuous coloring of a Mandelbrot fractal

I've recently started making a small fractal app in Javascript using the famous Mandelbrot bulb $(z = z^2 + c)$. I've been trying to find the best method of coloring the points on the complex plane, ...
6
votes
4answers
151 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
6
votes
1answer
3k views

XOR properties in set of numbers

Say I have n positive numbers A1,A2...An and Ak is minimum among them. And d is a number ...
6
votes
4answers
2k views

The longest sum of consecutive primes that add to a prime less than 1,000,000

In Project Euler problem $50,$ the goal is to find the longest sum of consecutive primes that add to a prime less than $1,000,000. $ I have an efficient algorithm to generate a set of primes ...
6
votes
3answers
1k views

Inverse of symmetric matrix $M = A A^\top$

I have a matrix, generated by the product of a non-square matrix with its own transpose: $$M = A A^\top.$$ I need the inverse of $M$, assuming $\det(M) \neq 0$. Given the nature of the matrix $M$, ...
6
votes
3answers
737 views

A balanced latin rectangle (more rows than columns)

In psychology we sometimes use balanced latin squares for the order of our tests to counterbalance first-order carry-over effects (fatigue, learning, etc.) . For our current study we want to pretest ...
6
votes
1answer
216 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
6
votes
2answers
127 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
6
votes
2answers
210 views

Number of sudokus with no consecutive arithmetic progression of length 3 in any row or column.

How many such Sudokus are there? Any reference to papers, books, articles or any insight into the problem will be greatly appreciated. I've tried several search engines, scholarly and not, with no ...
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
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: ...
6
votes
1answer
278 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
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?
6
votes
2answers
104 views

Puzzle about voting

I came across about this puzzle which I'm not sure how to go about. Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same ...
6
votes
1answer
959 views

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
6
votes
3answers
784 views

$3 \times 3 $ Magic Square of Squares

On picture below is three-by-three magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the ...
6
votes
3answers
304 views

Efficiently testing if sigma(n) = m

I'm trying to write a function that efficiently solves this problem: Given positive integers m and n, determine whether $\sigma(n)=m$. Of course I'm looking for a faster technique than "factor n, ...
6
votes
1answer
500 views

Count expressions with 1s and 2s

Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * ...
6
votes
1answer
2k views

What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no ...
6
votes
1answer
156 views

Graph theory algorithm

I've got an interesting graph-theory problem. I am given a tree $T$ with $n$ nodes and a set of edges. $T$ is, of course, undirected. Each edge has weight that indicates how many times (at least) it ...
6
votes
1answer
756 views

any idea what fractal algorithm might generate this shape?

I Found this image around, and i'm curious what algorithm generates this kind of shape In particular, i'm curious how the flow lines are generated, since usually the Mandelbrot iteration just ...
6
votes
3answers
290 views

Is there an efficient algorithm to find a length maximizing combination?

The problem is the following Given $v_1, \, v_2, \, \ldots, \, v_n \in \mathbb R^m$; find $\epsilon_1, \, \epsilon_2, \, \ldots, \, \epsilon_n \in \{0,1\}$ such that $$\left\vert \sum_{i=1}^n ...
6
votes
1answer
286 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?
6
votes
2answers
483 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
6
votes
2answers
524 views

Is the factorization problem harder than RSA factorization ($n = pq$)?

Let $n \in \mathbb{N}$ be a composite number, and $n = pq$ where $p,q$ are distinct primes. Let $F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ (*) be an algorithm which takes as an input $x ...
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 ...
6
votes
5answers
923 views

Least wasteful use of stamps to achieve a given postage

You have sheets of 42-cent stamps and 29-cent stamps, but you need at least $3.20 to mail a package. What is the least amount you can make with the 42- and 29-cent stamps that is ...
6
votes
4answers
80 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...