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
3answers
7k views

How do you determine if a point sits inside a polygon?

Given the coordinates of a point $(x, y)$, what is a procedure for determining if it lies within a polygon whose vertices are $(x_1, y_1), (x_2, y_2), \ldots , (x_n,y_n)$?
7
votes
3answers
270 views

Transform polygons into one another?

I am aware that there must be no standard way to achieve this, but I don't know what has been done so far. I feel like I'm missing keywords to investigate further. I have any two 2D polygons $a$ and ...
7
votes
2answers
4k 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?
7
votes
3answers
85 views

Infinite sequence of $3$ numbers with nonrepeated parts.

I am thinking about this problem. Can we construct infinite sequence with $3$ numbers so that no repeated parts exist in it? There should not be subsequence with $2k$ numbers so that its left and ...
7
votes
3answers
622 views

Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
7
votes
1answer
1k 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 ...
7
votes
1answer
389 views

Algorithm for scrolling through different orbits in a permutation group

Given an $n\in\mathbb{N}$, and a permutation $\pi\in S_{n}$, denote the centralizer of $\pi$ by $C_{\pi}$. Now we can look on the conjugation action of $C_{\pi}$ on $S_{n}$ and then divide $S_{n}$ to ...
7
votes
1answer
303 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?
7
votes
1answer
539 views

Algorithm to solve gridlock (traffic jam)

Is there an algorithm for solving a gridlock (traffic jam)? Given a gridlock situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that ...
7
votes
3answers
368 views

Algorithm for multiplying numbers

Background Today I had to explain to some kid how to multiply numbers with multiple digits in them. Then I recalled, that some other day I answered this question describing one of the numerous ...
7
votes
1answer
96 views

Finding $x^n$ patterns

I noticed the other day while computing consecutive powers of $2$ that for $n \geq 1$, the numbers in the ones place of the values of $2^n$ repeat every 4 terms $(2, 4, 8, 6,\ldots)$. In the tens ...
7
votes
1answer
134 views

Put a mouse to the last cell

We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty. At each step, we can do one of two operations: $\mathbf{P}$: Put only in the first cell $C_1$ 2 mice. $\mathbf{M}$: Move ...
7
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 ...
7
votes
1answer
308 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. ...
7
votes
1answer
6k 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 ...
7
votes
2answers
539 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 ...
7
votes
1answer
500 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 ...
7
votes
3answers
289 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
7
votes
1answer
244 views

Tuning the birthday paradox

I have limited access to a collection $X_1,\ldots,X_m$ of sets of positive integers. Each $X_i$ is "moderately large" (a brief survey has found them to contain about $10^6$ elements in each set), but ...
7
votes
1answer
148 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 ...
7
votes
2answers
638 views

Buckets of Balls, Will one fill if I add another Ball?

I was refereed here by stackoverflow.com. With some searching I found this: another balls and bins question, but its not quite what I am looking for. Rather the inverse. IE the expected number of ...
7
votes
1answer
173 views

Accelerating approximations for arccos

I have recently built a method to accelerate drastically the accuracy of the following approximation of $\arccos(x)$ : $f_n(x)=2^n\sqrt{2-2g^{n-1}(x)}$ where $g(x)=\frac{1}2\sqrt{2+2x}$ and ...
7
votes
3answers
2k 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 ...
7
votes
2answers
229 views

Who is the oldest? (in a non-revealing way)

How can a group of people figure out who is the oldest, without revealing any other information? Revealing all the ages to a trusted third party is not allowed. Preferably I'm looking for solutions ...
7
votes
2answers
215 views

Density of black cells in rule 110

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell. Simulation of first 120000 ...
7
votes
1answer
90 views

Find the diameter of a set faster than $O(|M|^2)$

$M$ is a finite set of points in a metric space. I want to calculate the diameter of the set, i.e. the greatest distance between two points. Is there a smarter way to do this than to calculate the ...
7
votes
1answer
626 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
7
votes
1answer
203 views

How to study results of Diophantine equation?

I finally managed to learn a bit of number theory and Diophantine equation(with the help of Arturo Magidin's great answer in what type of math is this?). But I'm wondering what's the next step after? ...
7
votes
2answers
531 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
7
votes
0answers
519 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
7
votes
1answer
110 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
7
votes
1answer
985 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
7
votes
0answers
398 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
7
votes
0answers
240 views

What’s the best way to cut an apple?

Take the apple in one hand, and the knife in the other. In the first cut, the apple is divided in two pieces: a small one that drops into the plate and a big one that is still hold with the hand. This ...
7
votes
0answers
244 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 ...
7
votes
0answers
323 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$ ...
6
votes
7answers
9k views

How do I compute binomial coefficients efficiently?

I'm trying to reproduce [Excel's COMBIN function][1] in C#. The number of combinations is as follows, where number = n and number_chosen = k: $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ I can't use ...
6
votes
5answers
336 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
2answers
3k 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
10answers
13k views

Is there an algorithm to find all subsets of a set?

I'm trying to find a way to find all subsets of a set. Is there an algorithm to calculate this?
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
3k 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
2answers
2k 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
898 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
4answers
432 views

First Course in Linear algebra books that start with basic algebra?

I'm 30 years old, and the only math I can remember from college is basic algebra and some probabilities. Next month, I have a machine learning project I'd like to work on, but I'll need a solid ...
6
votes
2answers
6k 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
309 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
233 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
809 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
2answers
749 views

Determining the equality of two real numbers

Can the equality of two real numbers always be determined? Let us say that we have derived an expression for a real number X. We also have obtained an (entirely different) expression for a real ...