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
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
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
667 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
206 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
202 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
383 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
275 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
1answer
851 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
661 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
295 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
150 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
697 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
261 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
4k 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
1k views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
6
votes
1answer
266 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
460 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
515 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
401 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
870 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
205 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
632 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
275 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
260 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
179 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
423 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
645 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
91 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
118 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
128 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
398 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
116 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
224 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
674 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 ...
6
votes
1answer
108 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
6
votes
1answer
4k views

Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$

Hello and thanks for taking the time to answer my question. The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I ...
6
votes
2answers
2k views

Prerequisite mathematics for studying data structures and algorithms

Forgive me if this seems trivial to you. But, I do need your advice. I am self-studying computer programming, now want to study Algorithms and Data Structures. All respected texts in A&DS talk in ...
6
votes
1answer
643 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
6
votes
2answers
2k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
6
votes
1answer
902 views

What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
6
votes
2answers
1k views

How/why does this noise function work?

How/why does this noise function work? ...
6
votes
2answers
640 views

Expected travel time for regularly departing trains

I'm going to ask a very simple practical question, but I believe it has some interesting mathematical properties. The simple variant is: trains depart every $x$ minutes and take $y$ minutes to arrive ...
6
votes
3answers
3k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?