Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

6
votes
1answer
358 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
6
votes
0answers
81 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} ...
6
votes
0answers
177 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
6
votes
0answers
2k views

When does a Square Matrix have an LU Decomposition?

When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
6
votes
0answers
422 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
6
votes
1answer
226 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 ...
5
votes
2answers
415 views

Generate all binary numbers, a single bit flip a time

Is it possible to sequentially generate all $n$-bit configurations (say, the binary representation of a an $n$-digit number), a single bit flip a time, in such a way that no configuration is generated ...
5
votes
6answers
2k 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, ...
5
votes
3answers
899 views

programming brain teaser

Given a programming language where you could make as many variables up as possible and you could only perform these three operators find b-1. ...
5
votes
5answers
269 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 ...
5
votes
2answers
93 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
5
votes
3answers
6k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
5
votes
3answers
622 views

knapsack algorithm that looks too good to be true

I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset ...
5
votes
1answer
267 views

Do irrational number contain infinite/every patterns of sequences?

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
5
votes
2answers
332 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
5
votes
1answer
237 views

Is there an efficient algorithm to determine the parity of the longest path in a graph?

Finding the longest path in a graph is intractable problem. Th decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in ...
5
votes
2answers
135 views

Choosing between $n$ things using dice?

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die? For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
5
votes
2answers
688 views

Tranforming 2D outline into 3D plane

I am writing a program where I would like to allow the user to draw 4 connecting lines, such as: And convert this shape into a 3D plane. Is this possible? Is there an existing algorithm to do so? ...
5
votes
2answers
212 views

An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have. Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm ...
5
votes
2answers
396 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 ...
5
votes
2answers
421 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$$ ...
5
votes
2answers
3k 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 ...
5
votes
2answers
125 views

How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

The Wikipedia article for the Collatz conjecture states that: The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$. It gives ...
5
votes
7answers
3k views

Prime number generator, how to make

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes... The objective is: given a first prime, ...
5
votes
2answers
776 views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
5
votes
3answers
227 views

FFT for power of 3

Classic FFT works fine, when n is power of 2. How to generalize FFT procedure when n is power of 3? Is it possible to easily ...
5
votes
1answer
35 views

Under what circumstances does this procedure terminate?

This earlier question (essentially) asked why the following loop will terminate. (This is Java code, so assume you're working with signed, 32-bit integers:) ...
5
votes
2answers
127 views

Algorithmic approach to enumerating ideals in $\Bbb Z[x]/(m, f(x))$

I'm studying for my algebra quals this fall and keep encountering problems like the following: List all the ideals of $\mathbb{Z}[x]/(16, x^3)$. or List all the primes of ...
5
votes
1answer
1k 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 ...
5
votes
1answer
974 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 ...
5
votes
2answers
2k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
5
votes
3answers
180 views

Test whether an interval contains integer points

I want to make a non-complex (for algorithmic implementation) logical condition to test whether some real interval contains any integer points. Let $x$ be an interval with bounds $l, r$; Let ...
5
votes
4answers
694 views

How can I change the Conway's Game of Life so that, eventually, all cells die?

Darwinia features an intro which represents a modified version of Conway's Game of Life. You can see it in action here. The game developers added one more rule about the game: no cell may live ...
5
votes
2answers
517 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 ...
5
votes
1answer
388 views

Why does the method to find out log and cube roots work?

To find cube roots of any number with a simple calculator, the following method was given to us by our teacher, which is accurate to atleast one-tenths. 1)Take the number $X$, whose cube root needs ...
5
votes
1answer
222 views

Rabin and Shallit Algorithm

I want to implement Rabin and Shallit algorithm for representing a positive integer as a sum of three squares. Can anyone give me a rough sketch of the method? I searched through the internet but ...
5
votes
4answers
214 views

Looking for a significant example that highlights the suboptimality of the greedy algorithms

A week from now, I'll have to present my work to a bunch of coworkers who aren't used to the optimisation world and terminology. One of the main algorithms I implemented uses a greedy type algorithm ...
5
votes
2answers
343 views

Is there a branch of math studying music algorithms?

I have found 2-3 search engines for scientific studies, things like algorithms, thesis, piece of researches and stuff like that; I'm really surprised to see a lot of applications for the math ...
5
votes
1answer
194 views

Algorithm creating subsets with certain properties

I'm trying so solve following problem: Let's say, we have a set $A=\{1,2,3,...,49\}$. Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= ...
5
votes
3answers
703 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$, ...
5
votes
1answer
168 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
5
votes
3answers
122 views

Understanding this summation identity

I'm currently reading a book in which part of the solution to the problem involve this identity: $$\sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j-\sum_{j=1}^{i}j$$ Which I cannot derive myself. The only thing ...
5
votes
1answer
6k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
5
votes
2answers
419 views

Clustering algorithm to cluster objects based on their relation weight

I have $n$ words and their relatedness weight that gives me an $n\times n$ matrix. I'm going to use this for a search algorithm but the problem is I need to cluster the entered keywords based on their ...
5
votes
3answers
547 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 ...
5
votes
1answer
199 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.
5
votes
1answer
209 views

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed? We define $f(n)=m$ where the digits of $m$ and $n$ are reverse. Such as ...
5
votes
1answer
261 views

Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's ...
5
votes
2answers
329 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
5
votes
1answer
1k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...