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

learn more… | top users | synonyms (1)

5
votes
3answers
183 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
33 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
114 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
882 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
861 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
3answers
179 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
651 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
1answer
293 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
4answers
173 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
1answer
160 views

Do irrational number contain infinate/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
310 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
184 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
646 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
158 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
119 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
5k 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
3answers
489 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
194 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
2answers
499 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
184 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
234 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
1answer
1k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
5
votes
2answers
348 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
2answers
311 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
4answers
167 views

Algorithm for randomly choosing learning cards

I'm programming a learning software. It works with question-/answercards. I´m searching for a algorithm that gives me a higher probability for cards that the user has answered wrong. My actual idea ...
5
votes
1answer
178 views

solve $\ln(n!) = \Theta(n\ln(n))$ without stirling approximation

My homework was proving this equation which is simple using Stirling approximation. I was wondering if there is any other method to prove it - whithout Stirling - I can prove $\ln(n!) = O(n\ln(n))$ ...
5
votes
2answers
195 views

Generating seating plans- maximal number of orderings with different adjacencies

Background: So the school I work at has a policy that we try and sit the kids next to as many different other kids as possible throughout the academic year. This means rejigging the seating plan as ...
5
votes
2answers
280 views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is ...
5
votes
1answer
323 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
1answer
835 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: ...
5
votes
5answers
650 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 ...
5
votes
2answers
145 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
5
votes
2answers
93 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 ...
5
votes
3answers
316 views

Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms? Thanks.
5
votes
1answer
264 views

Random Primes between 4000000000 and 4294967291 (C++)

What is an efficient way to find a random prime between $4000000000$ and $4294967291 $ in C++? This is what I wrote, but it is ridiculous: ...
5
votes
1answer
209 views

How to find the value of positive integers $a$-through-$h$

If the equation $(x-a)(x-b)(x-c)(x-d)(x-e)(x-f)(x-g) = hx$ has seven positive integer roots, and $a,b,c,d,e,f,g,h$ are positive integers too, how can we find them?
5
votes
1answer
207 views

Remove every (k+1) th remaining element in kth pass of natural numbers

In the natural numbers series, we've to remove every 2nd element in the 1st pass. Then in the remaining elements, remove every 3rd element in the second pass. Then at Kth pass, remove every (k+1)th ...
5
votes
2answers
269 views

Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
5
votes
2answers
2k 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?
5
votes
1answer
2k views

how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors

How does one diagonalize a large sparse symmetric matrix to get the eigenvalues and the eigenvectors? The problem is the matrix could be very large (though it is sparse), at most 2500*2500. Is there ...
5
votes
1answer
174 views

Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
5
votes
1answer
114 views

Card drawing algorithm

I want to know whether there is an algorithm for randomly and securely drawing cards from a deck. I was thinking about a way to play deck-based games online with no trusted party and no way to cheat. ...
5
votes
1answer
127 views

finite field to rational fraction

Suppose I have a number $n\in\mathbb F_p$, i.e. an element of the finite field obtained by arithmetic modulo some (odd) prime $p$. I'm looking for a way to find a simple description of $n$ as a ...
5
votes
1answer
473 views

Generating geometrically-distributed variates over an interval given endpoints and expected value

I want to generate random variates from a truncated geometric distribution over the interval $[0, n)$ with specified expected value, $0 \le E < n$. The obvious way to do this seems to be to sample ...
5
votes
1answer
85 views

How to find the sparsest vector in a given subspace of $\mathbb{F}_2^n$

A subspace $C$ of $\mathbb{F}_2^n$ is given for some $n \geq 1$. The space $C$ is given by its basis. Is there a polynomial time algorithm to find the (nonzero) vector in $C$ of lowest hamming ...
5
votes
1answer
3k views

Detecting polygon self intersection

I'm looking for the algorithm that determines the fact that a polygon has self intersection or hasn't. I'm not needed in calculation of the intersection points coordinates or how many intersection ...
5
votes
2answers
339 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 ...
5
votes
1answer
2k 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 ...
5
votes
1answer
79 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
5
votes
2answers
164 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: ...