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)

6
votes
4answers
209 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
560 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
1k views

What's the proof of correctness for Robert Floyd's algorithm for selecting a single, random combination of values?

I read about it in a SO answer: Algorithm to select a single, random combination of values? ...
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
4answers
490 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
6k 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
2answers
608 views

What is the best way to factor arbitrary polynomials

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but ...
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
690 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
208 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
1answer
127 views

Power towers of $2$ and $3$ - looking for a proof

Let $\uparrow$ denote the right-associative exponentiation operator: $a\uparrow b\uparrow c=a\uparrow(b\uparrow c)=a^{b^c}$ There is a sequence $A248907$ recently submitted to OEIS (see also ...
6
votes
2answers
205 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
276 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
102 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
889 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
2answers
683 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
300 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
499 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
152 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
713 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
265 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
2answers
5k views

Fastest prime generating algorithm

What is the fastest known algorithm that generates all distinct prime numbers less than n? Is it faster than Sieve of Atkin?
6
votes
1answer
275 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
470 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
519 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
407 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
892 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
78 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 ...
6
votes
2answers
206 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
6
votes
1answer
257 views

Approximating Increasing Sequence

This is a homework question which we are really struggling with: We'll define the distance between sequences $(a_i)_{i=1}^n,(b_i)_{i=1}^n$ by: ...
6
votes
2answers
645 views

Time complexity to calculate a digit in a decimal

As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
6
votes
1answer
276 views

Sieve of Atkin - algorithm for enumerating lattice points.

Recently, I've been working towards implementing the Sieve of Atkin with significantly better performance than the version found on Wikipedia. From reading the original paper ...
6
votes
1answer
269 views

Efficiently determining if a discrete log exists

Finding a discrete log in a finite cyclic group, like $(Z_N)^x$, seems hard and in some cases a solution may not even exist. Consider $N=15$ and the generator function $2^k=m \bmod 15$. This will ...
6
votes
1answer
183 views

How many operation are required to sort a array of numbers.

On StackOverflow, a simple question inspired me to create an equation for a answer. But it turn out that, it is kind of complicated (IMHO) mathematical problem, namely: Given an array of n ...
6
votes
2answers
432 views

Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app. I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within ...
6
votes
1answer
288 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
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 ...
6
votes
1answer
146 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 ...
6
votes
1answer
648 views

How many steps does it take the computer to solve a Sudoku puzzle?

We all know what Sudoku is. Given a Sudoku puzzle, one can use a simple recursive procedure to solve it using a computer. Before describing the algorithm, we make some definitions. A partial solution ...
6
votes
1answer
93 views

How to eliminate some edges of a lattice to get exactly k paths?

We have an $n$ by $n$ lattice. We want to find a way to eliminate some edges, so that there are exactly $k$ paths from $(1,1)$ to $(n,n)$ of length $2n-2$. (this means our paths should be NE). I don't ...
6
votes
1answer
136 views

Constrained Optimizatoin: The Frank-Wolfe Method

A general convex optimization problem is framed as such: $$\min f(x) : x \in \Omega$$ where $\Omega$ is convex. The Frank-Wolfe method seeks a feasible descent direction $d_k$ (i.e. $x_k + d_k \in ...
6
votes
1answer
156 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
2answers
399 views

What is mathematically significant about this algorithm?

In this question, a certain algorithm was presented: Start with a deck of $n$ cards. Take the top card off and set it on the table on top of any cards already there Move the new top card ...
6
votes
3answers
121 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
6
votes
2answers
226 views

Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
6
votes
3answers
756 views

Calculating Non-Integer Exponent

I just wanted to directly calculate the value of the number $2^{3.1}$ as I was wondering how a computer would do it. I've done some higher mathematics, but I'm very unsure of what I would do to solve ...